Tree traversal: Difference between revisions

Content deleted Content added

Revision as of 05:54, 12 January 2013 edit Pgan002 (talk \| contribs) Extended confirmed users 15,135 edits Moved "Infinite trees" section after "Inplementations" section ← Previous edit		Revision as of 06:05, 12 January 2013 edit undo Pgan002 (talk \| contribs) Extended confirmed users 15,135 edits "Preorder" -> "pre-order", etc. Next edit →
Line 1: {{refimprove\|date=May 2009}} {{graph search algorithm}} In [[computer science]], '''tree traversal''' refers to the process of visiting (examining and/or updating) each node in a [[tree (data structure)\|tree data structure]], exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a [[binary tree]], but they may be generalized to other trees as well. == Types== Compared to [[List of data structures#Linear data structures\|linear data structures]] like [[linked list]]s and one dimensional [[Array data structure\|arrays]], which have a canonical method of traversal (namely in linear order), tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Traversing a tree involves iterating (looping) over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred – stored in some way for later visiting. This is often done via a [[Stack (abstract data type)\|stack]] (LIFO) or [[Queue (abstract data type)\|queue]] (FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can naturally be described by [[recursion]] or, more subtly, [[corecursion]], in which case the deferred nodes are stored implicitly – in the case of recursion, in the [[call stack]]. The name given to a particular style of traversal comes from the order in which nodes are visited. Most simply, does one go down first (depth-first: first child, then grandchild before second child) or across first (breadth-first: first child, then second child before grandchildren)? Depth-first traversal is further classified by position of the root element with regard to the left and right nodes. Imagine that the left and right nodes are constant in space, then the root node could be placed to the left of the left node (pre-order), between the left and right node (in-order), or to the right of the right node (post-order). There is no equivalent variation in breadth-first traversal – given an ordering of children, "breadth-first" is unambiguous. For the purpose of illustration, it is assumed that left nodes always have priority over right nodes. This ordering can be reversed as long as the same ordering is assumed for all traversal methods. Depth-first traversal is easily implemented via a stack, including recursively (via the call stack), while breadth-first traversal is easily implemented via a queue, including corecursively. Beyond these basic traversals, various more complex or hybrid schemes are possible, such as [[depth-limited search]]s such as [[iterative deepening depth-first search]]. ===Depth-first=== {{see also\|Depth-first search}} ~~There are three types of depth-first traversal: preorder, inorder and postorder. For a binary tre, they are defined as operations recursively at each node, starting with the root node follows:~~ There are three types of depth-first traversal: pre-order, in-order and post-order. For a binary tre, they are defined as operations recursively at each node, starting with the root node follows: ~~'''Preorder''':<ref name="holtenotes">http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html</ref>:~~ '''Pre-order''':<ref name="holtenotes">http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html</ref>: # Visit the root. # Traverse the left subtree. # Traverse the right subtree. ~~'''Inorder''' ('''symmetric'''):<ref name="holtenotes"/>~~ '''In-order''' ('''symmetric'''):<ref name="holtenotes"/> # Traverse the left subtree. # Visit the root. # Traverse the right subtree. ~~'''Postorder''':<ref name="holtenotes"/>:~~ '''Post-order''':<ref name="holtenotes"/>: # Traverse the left subtree. # Traverse the right subtree. # Visit the root. The trace of a traversal is called a sequentialization of the tree. No one sequentialisation according to pre-, in- or postorder describes the underlying tree uniquely, but any combination of two types of sequentialisation does.<ref>[http://cs.stackexchange.com/questions/439/which-combinations-of-pre-post-and-in-order-sequentialisation-are-unique Which combinations of pre-, post- and in-order sequentialisation are unique?]</ref> The trace of a traversal is called a sequentialization of the tree. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely, but any combination of two types of sequentialisation does.<ref>[http://cs.stackexchange.com/questions/439/which-combinations-of-pre-post-and-in-order-sequentialisation-are-unique Which combinations of pre-, post- and in-order sequentialisation are unique?]</ref> ;Generic tree To traverse any tree in '''depth-first order''', perform the following operations recursively at each node: # Perform pre-order operation # for i=1 to n-1 do ## Visit child[i], if present ## Perform in-order operation # Visit child[n], if present # Perform post-order operation where n is the number of child nodes. Depending on the problem at hand, the pre-order, in-order or post-order operations may be void, or you may only want to visit a specific child node, so these operations are optional. Also, in practice more than one of pre-order, in-order and post-order operations may be required. For example, when inserting into a ternary tree, a pre-order operation is performed by comparing items. A post-order operation may be needed afterwards to re-balance the tree. ==== Uses ==== Inorder traversal is very commonly used on [[binary search tree]]s because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name). ~~Preorder Traversing a tree in while inserting the values into a new tree is common way of making a complete ''copy'' of a[[binary search tree]].~~ ~~Preorder traversals can also be used to get a prefix expression ([[Polish notation]]) from [[Parse tree\|expression trees]]: traverse the expression tree preorderly.~~ In-order traversal is very commonly used on [[binary search tree]]s because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name). Pre-order Traversing a tree in while inserting the values into a new tree is common way of making a complete ''copy'' of a[[binary search tree]]. Pre-order traversals can also be used to get a prefix expression ([[Polish notation]]) from [[Parse tree\|expression trees]]: traverse the expression tree pre-orderly. ===Breadth-first=== {{see also\|Breadth-first search}} Trees can also be traversed in '''level-order''', where we visit every node on a level before going to a lower level. ==Example== [[Binary tree]]: [[Image:Sorted binary tree.svg\|350px\|A sorted binary tree]] ;Depth-first * Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) * Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) * Inorder traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right) * Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) * Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) ;Breadth-first * Level-order traversal sequence: F, B, G, A, D, I, C, E, H ==Implementations== ===Depth-first traversal=== ~~====Preorder====~~ ====Pre-order==== '''preorder'''(node) '''if''' node == '''null then''' return visit(node) preorder(node.left) preorder(node.right) '''iterativePreorder'''(node) parentStack = '''empty stack''' '''while''' not parentStack.isEmpty() '''or''' node != '''null''' '''if''' node != '''null then''' parentStack.push(node) visit(node) node = node.left '''else''' node = parentStack.pop() node = node.right ~~====Inorder====~~ ====In-order==== '''inorder'''(node) '''if''' node == '''null then''' return inorder(node.left) visit(node) inorder(node.right) '''iterativeInorder'''(node) parentStack = '''empty stack''' '''while''' not parentStack.isEmpty() '''or''' node != '''null''' '''if''' node != '''null then''' parentStack.push(node) node = node.left '''else''' node = parentStack.pop() visit(node) node = node.right ~~====Postorder====~~ ====Post-order==== '''postorder'''(node) '''if''' node == '''null then''' return postorder(node.left) postorder(node.right) visit(node) '''iterativePostorder'''(node) '''if''' node == '''null then''' return nodeStack.push(node) prevNode = '''null''' '''while''' not nodeStack.isEmpty() currNode = nodeStack.peek() '''if''' prevNode == '''null or''' prevNode.left == currNode '''or''' prevNode.right == currNode '''if''' currNode.left != '''null''' nodeStack.push(currNode.left) '''else if''' currNode.right != '''null''' nodeStack.push(currNode.right) '''else if''' currNode.left == prevNode '''if''' currNode.right != '''null''' nodeStack.push(currNode.right) '''else''' visit(currNode) nodeStack.pop() prevNode = currNode All the above implementations require [[call stack]] space proportional to the height of the tree. In a poorly balanced tree, this can be considerable. We can remove the stack requirement by maintaining parent pointers in each node, or by [[#Threading and Morris inorder traversal\|threading the tree]] (next section). ~~====Threading and Morris inorder traversal====~~ A binary tree is [[threaded binary tree\|threaded]] by making every left child pointer point to the inorder predecessor of the node and every right child pointer point to the inorder successor of the node. All the above implementations require [[call stack]] space proportional to the height of the tree. In a poorly balanced tree, this can be considerable. We can remove the stack requirement by maintaining parent pointers in each node, or by [[#Threading and Morris in-order traversal\|threading the tree]] (next section). ====Threading and Morris in-order traversal==== A binary tree is [[threaded binary tree\|threaded]] by making every left child pointer point to the in-order predecessor of the node and every right child pointer point to the in-order successor of the node. Advantages: # Avoids recursion, which uses a call stack and consumes memory and time. # The node keeps a record of its parent. Disadvantages: # The tree is more complex. # It is more prone to errors when both the children are not present and both values of nodes point to their ancestors. ~~Morris traversal is an implementation of inorder traversal that uses threading:~~ ~~# Create links to the inorder successor~~ Morris traversal is an implementation of in-order traversal that uses threading: # Create links to the in-order successor # Print the data using these links # Revert the changes to restore original tree. ===Breadth-first traversal=== Also, listed below is pseudocode for a simple [[queue (data structure)\|queue]] based level order traversal, and will require space proportional to the maximum number of nodes at a given depth. This can be as much as the total number of nodes / 2. A more space-efficient approach for this type of traversal can be implemented using an [[iterative deepening depth-first search]]. '''levelorder'''(root) q = empty queue q.enqueue(root) '''while''' not q.empty '''do''' node := q.dequeue() visit(node) ~~'''if''' node.left ≠ '''null'''~~ '''if''' node.left ? '''null''' q.enqueue(node.left) ~~'''if''' node.right ≠ '''null'''~~ '''if''' node.right ? '''null''' q.enqueue(node.right) ==Infinite trees== While tree traversal is generally done for finite trees – finite number of nodes, hence finite depth and finite [[branching factor]] – it can also be done for infinite trees. This is of particular interest in [[functional programming]](particularly with [[lazy evaluation]]), as infinite data structures can often be easily defined and worked with, though they are not (strictly) evaluated, as this would take infinite time. More practically, some trees are, while finite, so large as to in practice be infinite, such as the [[game tree]] for [[chess]] or [[Go (game)\|go]], and thus analyzing them as if they were infinite is useful – infinite trees are the limiting case of very large trees. A basic requirement for traversal is to visit every node. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depth-first traversal will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed if in-order or post-order will never visit ''any'' nodes, as it has not reached a leaf (and in fact never will). By contrast, a breadth-first (level-order) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor. On the other hand, given a tree of depth 2, where the root node has infinitely many children, and each of these children has two children, a depth-first traversal will visit all nodes, as once it exhausts the grandchildren (children of children of one node), it will move on to the next (assuming it is not post-order, in which case it never reaches the root). By contrast, a breadth-first traversal will never reach the grandchildren, as it seeks to exhaust the children first. A more sophisticated analysis of running time can be given via infinite [[ordinal number]]s; for example, the breadth-first traversal of the depth 2 tree above will take ω·2 steps: ω for the first level, and then another ω for the second level. A more sophisticated analysis of running time can be given via infinite [[ordinal number]]s; for example, the breadth-first traversal of the depth 2 tree above will take ?·2 steps: ? for the first level, and then another ? for the second level. Thus, simple depth-first or breadth-first searches do not traverse every infinite tree, and are not efficient on very large trees. However, hybrid methods can traverse any (countably) infinite tree, essentially via a [[Diagonal argument (disambiguation)\|diagonal argument]] (diagonal – combination of vertical and horizontal – corresponds to hybrid –combination of depth and breadth). Concretely, given the infinitely branching tree of infinite depth, label the root node <math>(),</math> the children of the root node <math>(1), (2), \dots,</math> the grandchildren <math>(1,1), (1,2), \ldots, (2,1), (2,2), \ldots,</math> and so forth. The nodes are thus in a [[bijection\|one-to-one]] correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by [[lexicographic order]] within a given sum (only finitely many sequences sum to a given value, so all entries are reached – formally there are a finite number of [[Composition (number theory)\|compositions]] of a given natural number, specifically 2<sup>''n''−1</sup>compositions of ''n'' ≥ 1;), which gives a traversal. Explicitly: Concretely, given the infinitely branching tree of infinite depth, label the root node <math>(),</math> the children of the root node <math>(1), (2), \dots,</math> the grandchildren <math>(1,1), (1,2), \ldots, (2,1), (2,2), \ldots,</math> and so forth. The nodes are thus in a [[bijection\|one-to-one]] correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by [[lexicographic order]] within a given sum (only finitely many sequences sum to a given value, so all entries are reached – formally there are a finite number of [[Composition (number theory)\|compositions]] of a given natural number, specifically 2<sup>''n''-1</sup>compositions of ''n'' = 1;), which gives a traversal. Explicitly: 0: () 1: (1) 2: (1,1) (2) 3: (1,1,1) (1,2) (2,1) (3) 4: (1,1,1,1) (1,1,2) (1,2,1) (1,3) (2,1,1) (2,2) (3,1) (4) etc. This can be alternatively interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first traversal: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the 1st child to the 2nd child, 2nd child to third child, etc. Thus at each step one can either go down (append a (,1) to the end) or go right (add 1 to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus 1) corresponds to the distance from the root, which agrees with the 2<sup>''n''−1</sup> nodes at depth ''n''−1 in the infinite binary tree (2 corresponds to binary). This can be alternatively interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first traversal: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the 1st child to the 2nd child, 2nd child to third child, etc. Thus at each step one can either go down (append a (,1) to the end) or go right (add 1 to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus 1) corresponds to the distance from the root, which agrees with the 2<sup>''n''-1</sup> nodes at depth ''n''-1 in the infinite binary tree (2 corresponds to binary). == References == <references/> * Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition. * Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition. * http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran == External links == [http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BTree.html Animation Applet of Binary Tree Traversal] [http://www.SQLSummit.com/AdjacencyList.htm The Adjacency List Model for Processing Trees with SQL] [http://www.sitepoint.com/article/hierarchical-data-database Storing Hierarchical Data in a Database] with traversal examples in PHP [http://dev.mysql.com/tech-resources/articles/hierarchical-data.html Managing Hierarchical Data in MySQL] [http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html Working with Graphs in MySQL] [http://www.jslab.dk/articles/non.recursive.preorder.traversal Non-recursive traversal of DOM trees in JavaScript] [http://code.google.com/p/treetraversal/ Sample code for recursive and iterative tree traversal implemented in C.] [http://arachnode.net/blogs/programming_challenges/archive/2009/09/25/recursive-tree-traversal-orders.aspx Sample code for recursive tree traversal in C#.] [http://rosettacode.org/wiki/Tree_traversal See tree traversal implemented in various programming language] on [[Rosetta Code]] [http://www.perlmonks.org/?node_id=600456 Tree traversal without recursion] {{DEFAULTSORT:Tree Traversal}} [[Category:Trees (data structures)]] [[Category:Articles with example Haskell code]] [[Category:Articles with example Java code]] [[Category:Articles with example pseudocode]] [[Category:Graph algorithms]] [[Category:Recursion]] [[de:Binärbaum#Traversierung]] [[es:Recorrido de árboles]] ~~[[fa:پیمایش درخت]]~~ [[fa:?????? ????]] ~~[[ja:木構造 (データ構造)]]~~ [[ja:??? (?????)]] [[pl:Przechodzenie drzewa]] [[sv:Traversering]] ~~[[uk:Обхід дерева]]~~ [[viuk:~~Duyệt~~????? ~~cây~~??????]] ~~[[zh:树的遍历]]~~ [[vi:Duy?t cây]] [[zh:????]]