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

[E1M1]

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.

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).

expandcollapse popup

;~             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!

[water]

Maybe the can help.

Edited October 26, 2011 by water

[E1M1]

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 October 26, 2011 by E1M1

[water]

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

[Yashied]

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.

expandcollapse popup

;~         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 October 26, 2011 by Yashied