Sign in to follow this  
Followers 0
E1M1

Need some logic help with recursive path finding function for binary tree

5 posts in this topic

Hi

Could anyone help me to write function that finds path to given element in binary tree? That function would have to pick item's 2 (left and right) subordinates, and then do same with these 2 subordinates. For example, B is subordinate for A but boss of D and E. D is subordinate for B and boss for G. tried to do it my self but it always returns 0. Function I wrote for it is FindPath.

Posted Image

For example path from A to D would be A,B,D. If you create array where A is [0], B is [1] , C is[2] and D is [3] then path from A to D would be [0],[1],[3].

Empty spaces in binary tree are filled with - in array. So Array for left tree is: ["A", "B", "C", "D", "E", "-", "F", "-", "G", "-", "-","-","-", "H", "-","-","-"]

I would like to use some help with my path finding function. It would be fine if just returned string contained array indexes (I could later just split string and get item indexes and from item indexes i can easyly get array item values).

;~             A
;~           /      \
;~         B        C
;~       /   \         \
;~     D        E        F
;~       \         /
;~         G        H

;~     a(
;~         b(
;~             e()
;~             d(
;~                 g()
;~             )
;~         )
;~         c(
;~             f(
;~                 h()
;~             )
;~         )
;~     )


;~ $tree = "a(b(e()d(g()))c(f(h())))"


Dim $tree2[17] = ["A", "B", "C", "D", "E", "-", "F", "-", "G", "-", "-","-","-", "H", "-","-","-"]
Func GoTrough()
    $i = 1
    $success = True
    $max = UBound($tree2) - 1
    $C = 0
    While $success
        $count = 2 ^ ($i - 1)
        For $n = 1 To $count
            If $C < $max Then
                ConsoleWrite($tree2[$C])
                $C += 1
            Else
                $success = False
            EndIf
        Next
        ConsoleWrite(@CRLF)
        Sleep(500)
        $i += 1
    WEnd
EndFunc   ;==>GoTrough

ConsoleWrite(FindPath(3,17)&@CRLF)

Func FindPath($elemID,$EndAt,$StartAt = 0,$Returned = "")
    If $StartAt > $EndAt Then Return
    $left = GetLetSubordinate($StartAt)
    $right = GetLetSubordinate($StartAt,1)
    If $left = $elemID or $right = $elemID then
        Return $Returned&$StartAt
    Else
        $left = FindPath($elemID,$EndAt,$left,$Returned)
        $right = FindPath($elemID,$EndAt,$right,$Returned)
        If $left = $elemID or $right = $elemID then Return $Returned&$StartAt
    EndIf
EndFunc

; $Right = 0 - Goes left
; $Right = 1 - Goes right
Func GetLetSubordinate($elemID,$Right = 0)
    $Line = GetElementLine($elemID)
    $LineStart = GetLineStart($Line)
    $NextLine = GetLineStart($Line +1)
    $ItemPosInLine = $elemID - $LineStart
    $SubordinateOffset = $ItemPosInLine*2
    return $SubordinateOffset+$NextLine+$Right
EndFunc


Func GetLineLen($iLine)
    Return 2 ^ ($iLine - 1)
EndFunc

Func GetElementLine($elemID)
    $line = 1
    $found = False
    $i = 1
    $total = 0
    While not $found
        $count = 2 ^ ($i - 1)
        $total += $count
        if $total > $elemID then
            Return $i
        EndIf
        $i += 1
    WEnd
EndFunc

Func GetLineStart($iLine)
    $total = 0
    For $i = 1 To $iLine -1
        $total += 2 ^ ($i - 1)
    Next
    Return $total
EndFunc

;~ Func ToG()
;~     $tree2[0]
;~     $tree2[1]
;~     $tree2[3]
;~     $tree2[8]
;~ EndFunc


;sucks
Dim $tree[1]
Dim $A[2]
Dim $B[2]
Dim $D[1]
Dim $E[1]
Dim $C[1]
Dim $F[1]
Dim $H[1]
Dim $G[1]


$tree[0] = $A
$A[0] = $B
$A[1] = $C
$B[0] = $D
$D[0] = $G
$B[1] = $E
$C[0] = $F
$F[0] = $H

#cs compact reee
    K
    /      \
    L        M
    /  \
    N    O
    / \
    P   Q

#ce

Dim $cTree[16] = ["K", "L", "M", "-", "-", "N", "O", "-", "-", "-", "-", "P", "Q", "-", "-"]

I got words subordinate and boss from dictionary. If you know better replacements let me know!


edited

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

Maybe the can help.

Edited by water

My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

Haven't used to see binary tree like that. That udf looked entirely different from mine. I hoped that someone would tell me what I do wrong in my func but.. thats ok.

Thanks for helping.

After looking into that udf I cant find function similar to my FindPath

Edited by E1M1

edited

Share this post


Link to post
Share on other sites

I don't understand your script (or maybe just don't have the time). Maybe the can give you some ideas.


My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

If you specify a tree in the following form

Dim $Tree[15] = ['A', 'B', 'C', 'D', 'E', '', 'F', '', 'G', '', '', '', '', 'H', '']

Then the index of the previous and following items relative to the current position can be calculated as follows

;~         A (Prev)
;~       /
;~     B (Current)
;~   /   \
;~ D       E
;~ (Next1) (Next2)

$Prev = 2 ^ (Ceiling(Log($Current + 2) / Log(2)) - 2) + Floor(($Current - 2 ^ (Ceiling(Log($Current + 2) / Log(2)) - 1) + 1) / 2) - 1

$Next1 = 2 ^ Ceiling(Log($Current + 2) / Log(2)) + 2 * ($Current - 2 ^ (Ceiling(Log($Current + 2) / Log(2)) - 1) + 1) - 1
$Next2 = $Next1 + 1

And two variants of your function.

;~         A
;~       /   \
;~     B       C
;~   /   \       \
;~ D       E       F
;~   \           /
;~     G       H

Dim $Tree[15] = ['A', 'B', 'C', 'D', 'E', '', 'F', '', 'G', '', '', '', '', 'H', '']

#cs

Func _Path(ByRef $aTree, $sItem, $iIndex = 0, $sPath = '')
    If Not $aTree[$iIndex] Then
        Return ''
    EndIf
    $sPath = StringRegExpReplace($sPath & '-' & $aTree[$iIndex], '\A-+', '')
    If $aTree[$iIndex] = $sItem Then
        Return $sPath
    EndIf
    $iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1
    If $iIndex < UBound($aTree) - 1 Then
        For $i = 0 To 1
            Local $Path = _Path($aTree, $sItem, $iIndex + $i, $sPath)
            If $Path Then
                Return $Path
            EndIf
        Next
    EndIf
    Return ''
EndFunc   ;==>_Path

ConsoleWrite(_Path($Tree, 'H') & @CR)

#ce

Func _Path(ByRef $aTree, $iItem, $iIndex = 0, $sPath = '')
    If Not $aTree[$iIndex] Then
        Return ''
    EndIf
    $sPath = StringRegExpReplace($sPath & '-' & $iIndex, '\A-+', '')
    If $iIndex = $iItem Then
        Return $sPath
    EndIf
    $iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1
    If $iIndex < UBound($aTree) - 1 Then
        For $i = 0 To 1
            Local $Path = _Path($aTree, $iItem, $iIndex + $i, $sPath)
            If $Path Then
                Return $Path
            EndIf
        Next
    EndIf
    Return ''
EndFunc   ;==>_Path

ConsoleWrite(_Path($Tree, 13) & @CR)
Edited by Yashied

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0