A methode to traverse a tree (or the rest of a tree starting from a node with unkown position) depth-first without recursion and without mandatorily keeping track of the position of the current node; requires each node to have reference acess to its parent, first child and next sibling, therefore especially suitable for DOM trees.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | def TraverseNode(currentnode, currentdone, currentpath = None, processcallback = None):
if not currentdone:
if currentpath != None:
currentpath.append(currentnode.nodeName)
# perform whatever action with the currentnode here
if processcallback:
processcallback(currentnode)
firstchild = currentnode.firstChild
if firstchild != None:
return (firstchild, False)
if currentpath != None:
del currentpath[-1]
nextsibling = currentnode.nextSibling
if nextsibling != None:
return (nextsibling, False)
parent = node.parentNode
if (parent != None) and (currentpath != None):
# as long as parent exists, currentpath is not supposed to be []
del currentpath[-1]
return (parent, True)
def TraverseTree(startnode, startpath = []):
currentnode = startnode
currentdone = False
currentpath = startpath
while startnode != None:
(currentnode, currentdone) = TraverseNode(currentnode, currentdone, currentpath)
|
Tree traversal is most commonly implemented using recursion. While this certainly has its advantages, it is sometimes desireable to avoid due to memory efficiency or other reasons. Another common alternative for tree traversal is to track the current node, either by index - if the child nodes of a node are indexed - or by reference.
It is however also possible - as shown above - to traverse a tree depth-first without recursion and without tracking of the current node, provided the single nodes have reference access to their parent, their first child and their next silbling - all of which required by the DOM specification.
Among others, the methode above is useful to traverse the rest of a tree starting from any node without knowledge of its position in the tree. Even though it does includes the possibility of tracking the current path (as a list of str), it is entirely optional and will be skipped if TraverseTree is called with None as startpath.
