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

Recommended Posts

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

```;~             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 on other sites

Maybe the can help.

Edited by water

My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2022-02-19Â - Version 1.6.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2017-07-21 - Version 0.4.0.1) - Download - General Help & Support - Example Scripts
OutlookEX (2021-11-16 - Version 1.7.0.0) - Download - General Help & Support - Example Scripts - Wiki
Outlook Tools (2019-07-22 - Version 0.6.0.0) - Download - General Help & Support - Wiki
PowerPoint (2021-08-31 - Version 1.5.0.0) - Download - General Help & Support - Example Scripts - Wiki

Standard UDFs:
ExcelÂ - Example Scripts - Wiki
Word - Wiki

Tutorials:
WebDriver - Wiki

Â

Share on other sites

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 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 2022-02-19Â - Version 1.6.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2017-07-21 - Version 0.4.0.1) - Download - General Help & Support - Example Scripts
OutlookEX (2021-11-16 - Version 1.7.0.0) - Download - General Help & Support - Example Scripts - Wiki
Outlook Tools (2019-07-22 - Version 0.6.0.0) - Download - General Help & Support - Wiki
PowerPoint (2021-08-31 - Version 1.5.0.0) - Download - General Help & Support - Example Scripts - Wiki

Standard UDFs:
ExcelÂ - Example Scripts - Wiki
Word - Wiki

Tutorials:
WebDriver - Wiki

Â

Share on other sites

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

Create an account

Register a new account