Tree traversal: Difference between revisions

Revision as of 23:19, 20 July 2005

Revision as of 22:44, 15 September 2005

Line 1:

{{Tree search algorithm}}

In [[computer science]], '''tree traversal''' is the process of visiting each node in a [[tree data structure]]. Tree traversal, also called '''walking the tree''', provides for sequential processing of each node in what is, by nature, a non-sequential data structure.

Such traversals are classified by the order in which the nodes are visited.

Line 5 ⟶ 6:

== 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 31:

== Examples ==

<table>

<tr><td>[[Image:binary_tree.png|A simple example binary tree]]</td>

Line 42 ⟶ 41:

== Functional traversal ==

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

Line 59 ⟶ 57:

== 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 [[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:

Line 81 ⟶ 78:

}

}

== External links ==

*[http://www.sitepoint.com/article/hierarchical-data-database Storing Hierarchical Data in a Database] with traversal examples in PHP

[[Category:Trees (structure)]]