Tree traversal: Difference between revisions

Revision as of 23:43, 12 March 2005

Revision as of 23:44, 12 March 2005

Line 62:

All of the above recursive algorithms use stack space proportional to the depth of the tree. If we store on each node a reference to its parent, then we can implement all of these traversals [[in-place algorithm|in-place]] using a simple iterative algorithm. The parent references occupy much more space, however; this is only really useful if the parent references are needed anyway, or stack space in particular is limited. For example, here is an iterative algorithm for in-order traversal:

visit(root) {

<pre>

next prev := '''null'''

visit(root) {

prev current := '''null'''root

current next := root'''null'''

next := '''null'''

'''while''' current &ne; '''null''' {

'''if''' prev == current.parent

prev := current

next := current.left

'''if''' next == '''null''' '''or''' prev == current.left

print current.value

prev := current

next := current.right

'''if''' next == '''null''' '''or''' prev == current.right

prev := current

next := current.parent

current := next

}

}

</pre>

[[Category:Computer science]]