Tree traversal: Difference between revisions

Revision as of 23:34, 12 March 2005

Revision as of 23:37, 12 March 2005

Line 3:

The following algorithms are described for a [[binary tree]], but they may be generalized to other trees.

== Traversal methods ==

Say we have a tree node structure which contains a value <code>value</code> and references <code>left</code> and <code>right</code> to its two children. Then we can write the following function:

Line 27 ⟶ 29:

If instead we visit the right subtree, then the current node, then the left subtree, this produces the opposite order as in-order traversal, sometimes called a '''reverse in-order''' or '''reverse-order''' traversal.

== Examples ==

<table>

Line 36 ⟶ 40:

</td></tr>

</table>

== Functional traversal ==

We could perform the same traversals in a functional language like [[Haskell programming language|Haskell]] using code like this:

Line 51 ⟶ 57:

inorder (Node left x right) = (inorder left) ++ [x] ++ (inorder right)

</pre>

== Iterative traversal ==

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 using only constant space 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:

<pre>

visit(root) {

prev := null

current := root

next := null

while current != null {

if prev == current.parent

prev := current

Line 72 ⟶ 80:

next := current.parent

current := next

}

}

</pre>

[[Category:Computer science]]

[[uk:&#1054;&#1073;&#1093;&#1110;&#1076; &#1076;&#1077;&#1088;&#1077;&#1074;&#1072;]]