In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes 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. In Computer science, a binary tree is a tree data structure in which each node has at most two children.

Contents 1 Traversal methods 1.1 Example 1.2 Sample implementations 1.3 Level order traversal 1.4 Queue-based level order traversal 1.5 Uses 2 Functional traversal 3 Iterative traversing 4 See also 5 External links 6 References

Traversal methods

Compared to linear data structures like linked lists and one dimensional arrays, which have only one logical means of traversal, tree structures can be traversed in many different ways. This is a list of Data structures For a wider list of terms see List of terms relating to algorithms and data structures. In Computer science, a linked list is one of the fundamental Data structures and can be used to implement other data structures In Computer science an array is a Data structure consisting of a group of elements that are accessed by indexing. 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 define 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. Thus the process is most easily described through recursion. Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

1. Visit the node.
2. Traverse the left subtree.
3. Traverse the right subtree.

(This is also called Depth-first traversal. Depth-first search ( DFS) is an Algorithm for traversing or searching a tree, Tree structure, or graph. )

To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node, starting with the root node:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node, starting with the root node:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the node.

Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal. In Graph theory, breadth-first search ( BFS) is a Graph search algorithm that begins at the root node and explores all the neighboring nodes

Example

In this binary search tree, Preorder traversal sequence: F, B, A, D, C, E, G, I, H Inorder traversal sequence: A, B, C, D, E, F, G, H, I Note that the inorder traversal of this binary search tree yields an ordered list Postorder traversal sequence: A, C, E, D, B, H, I, G, F Level-order traversal sequence: F, B, G, A, D, I, C, E, H

Sample implementations

preorder(node)
  print node. In Computer science, a binary search tree ( BST) is a Binary tree Data structure which has the following properties each node value
  if node. left ≠ null then preorder(node. left)
  if node. right ≠ null then preorder(node. right)

inorder(node)
  if node. left  ≠ null then inorder(node. left)
  print node. value
  if node. right ≠ null then inorder(node. right)

postorder(node)
  if node. left  ≠ null then postorder(node. left)
  if node. right ≠ null then postorder(node. right)
  print node. value

All three recursive sample implementations will require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.

We can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree. A threaded Binary tree may be defined as follows A binary tree is threaded by making all right child pointers that would normally be null point to In the case of using threads, this will allow for greatly improved inorder traversal, although retrieving the parent node required for preorder and postorder traversal will be slower than a simple stack based algorithm.

To traverse a threaded tree inorder, we could do something like this:

inorder(node)
  while hasleftchild(node) do
    node = node. left
  do
    visit(node)
    if (hasrightchild(node)) then
      node = node. right
      while hasleftchild(node) do
        node = node. left
    else
      node = node. right
  while node ≠ null

Note that a threaded binary tree will provide a means of determining whether a pointer is a child, or a thread. See threaded binary trees for more information. A threaded Binary tree may be defined as follows A binary tree is threaded by making all right child pointers that would normally be null point to

Level order traversal

Level order traversal is a traversal method by which levels are visited successively starting with level 0 (the root node), and nodes are visited from left to right on each level.

This is commonly implemented using a queue data structure with the following steps (and using the tree below as an example):

Step 1: Push the root node onto the queue (node 2):

    New queue:           2- - - - - - - - - - 

Step 2:

Pop the node off the front of the queue (node 2).

Push that node's left child onto the queue (node 7).

Push that node's right child onto the queue (node 5).

Output that node's value (2).

    New queue:           7-5- - - - - - - - - 
    Output: 2

Step 3:

Pop the node off the front of the queue (node 7).

Push that node's left child onto the queue (node 2).

Push that node's right child onto the queue (node 6).

Output that node's value (7).

    New queue:           5-2-6- - - - - - - -
    Output: 2 7 

Step 4:

Pop the node off the front of the queue (node 5).

Push that node's left child onto the queue (NULL, so take no action).

Push that node's right child onto the queue (node 9).

Output that node's value (5).

    New queue:           2-6-9- - - - - - - -
    Output: 2 7 5

Step 5:

Pop the node off the front of the queue (node 2).

Push that node's left child onto the queue (NULL, so take no action).

Push that node's right child onto the queue (NULL, so take no action).

Output that node's value (2).

    New queue:           6-9- - - - - - - - - 
    Output: 2 7 5 2

Step 6:

Pop the node off the front of the queue (node 6).

Push that node's left child onto the queue (node 5).

Push that node's right child onto the queue (node 11).

Output that node's value (6).

    New queue:           9-5-11- - - - - - - - 
    Output: 2 7 5 2 6

Step 7:

Pop the node off the front of the queue (node 9).

Push that node's left child onto the queue (node 4).

Push that node's right child onto the queue (NULL, so take no action).

Output that node's value (9).

    New queue:           5-11-4- - - - - - - -
    Output: 2 7 5 2 6 9 

Step 8: You will notice that because the remaining nodes in the queue have no children, nothing else will be added to the queue, so the nodes will just be popped off and output consecutively (5, 11, 4). This gives the following:

    Final output: 2 7 5 2 6 9 5 11 4

which is a level-order traversal of the tree.

Queue-based level order traversal

Also, listed below is pseudocode for a simple queue based level order traversal, and will require space proportional to the maximum number of nodes at a given depth. A queue (pronounced /kjuː/ is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only operations on the collection 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. Iterative deepening depth-first search (IDDFS is a State space search strategy in which a Depth-limited search is run repeatedly increasing the depth limit with

levelorder(root) 
  q = empty queue
  q. enqueue(root)
  while not q. empty do
    node := q. dequeue()
    visit(node)
    if node. left ≠ null
      q. enqueue(node. left)
    if node. right ≠ null
      q. enqueue(node. right)

Uses

Inorder traversal

It is particularly common to use an inorder traversal on a binary search tree because this will return values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name). In Computer science, a binary search tree ( BST) is a Binary tree Data structure which has the following properties each node

To see why this is the case, note that if n is a node in a binary search tree, then everything in n 's left subtree is less than n, and everything in n 's right subtree is greater than or equal to n. Thus, if we visit the left subtree in order, using a recursive call, and then visit n, and then visit the right subtree in order, we have visited the entire subtree rooted at n in order. We can assume the recursive calls correctly visit the subtrees in order using the mathematical principle of structural induction. Structural induction is a proof method that is used in Mathematical logic (e Traversing in reverse inorder similarly gives the values in decreasing order.

Preorder traversal

Traversing a tree in preorder while inserting the values into a new tree is common way of making a complete copy of a binary search tree. In Computer science, a binary search tree ( BST) is a Binary tree Data structure which has the following properties each node

One can also use preorder traversals to get a prefix expression (Polish notation) from expression trees: traverse the expression tree preorderly. Polish notation, also known as prefix notation, is a form of notation for Logic, Arithmetic, and Algebra. A parse tree or concrete syntax tree is an (ordered rooted tree that represents the syntactic structure of a string according to some To calculate the value of such an expression: scan from right to left, placing the elements in a stack. Each time we find an operator, we replace the two top symbols of the stack with the result of applying the operator to those elements. For instance, the expression ∗ + 234, which in infix notation is (2 + 3) ∗ 4, would be evaluated like this:

Using prefix traversal to evaluate an expression tree

Expression (remaining)	Stack
∗ + 234	<empty>
∗ + 23	4
∗ + 2	3 4
∗ +	2 3 4
∗	5 4
Answer	20

Functional traversal

We could perform the same traversals in a functional language like Haskell using code similar to this:

data Tree a = Nil | Node (Tree a) a (Tree a)

preorder Nil = []
preorder (Node left x right) = [x] ++ (preorder left) ++ (preorder right) 

postorder Nil = []
postorder (Node left x right) = (postorder left) ++ (postorder right) ++ [x]

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

Iterative traversing

All the above recursive algorithms require stack space proportional to the depth of the tree. Haskell is a standardized Purely functional Programming language with non-strict semantics, named after the Logician Haskell Curry Recursive traversal may be converted into an iterative one using various well-known methods.

A sample is shown here for postorder traversal:

nonrecursivepostorder (rootNode)
  nodeStack. push (rootNode)
  while (true)
    currNode = nodeStack. pop ()
    if ((currNode. left != null) and (currNode. left. visited == false))
      nodeStack. push (currNode. left)
    else 
      if ((currNode. right != null) and (currNode. right. visited == false))
        nodeStack. push (currNode. right)
      else
        print currNode. value
        currNode. visited := true
    if nodeStack. empty()
      break

In this case, for each node is required to keep an additional "visited" flag, other than usual informations (value, left-child-reference, right-child-reference).

See also

• Tree programming
• Polish notation
• Depth-first search
• Breadth-first search
• Threaded binary tree - linear traversal of binary tree

External links

• The Adjacency List Model for Processing Trees with SQL
• Storing Hierarchical Data in a Database with traversal examples in PHP
• Managing Hierarchical Data in MySQL
• Working with Graphs in MySQL
• N-ary Tree Traversal
• Animation Applet of Binary Tree Traversal

References

• Dale, Nell. Tree programming refers to the use of a Programming language to analyze data trees, in a way unique from conventional programming languages Polish notation, also known as prefix notation, is a form of notation for Logic, Arithmetic, and Algebra. Depth-first search ( DFS) is an Algorithm for traversing or searching a tree, Tree structure, or graph. In Graph theory, breadth-first search ( BFS) is a Graph search algorithm that begins at the root node and explores all the neighboring nodes A threaded Binary tree may be defined as follows A binary tree is threaded by making all right child pointers that would normally be null point to 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

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic