| Tree Search |
Article Index for Tree |
Website Links For Tree |
Information AboutTree Search |
| CATEGORIES ABOUT TREE TRAVERSAL | |
| trees structure | |
| articles with example haskell code | |
| articles with example pseudocode | |
|
TRAVERSAL METHODS Compared to . To traverse a non-empty binary tree in preorder, perform the following operations: # Visit the root. # Traverse the left subtree. # Traverse the right subtree. To traverse a non-empty binary tree in inorder, perform the following operations: # Traverse the left subtree. # Visit the root. # Traverse the right subtree. To traverse a non-empty binary tree in postorder, perform the following operations: # Traverse the left subtree. # Traverse the right subtree. # Visit the root. (This is also called Depth-first Traversal .) 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 Example Sample implementations preorder(node) print 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 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 . 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 not (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 Tree s for more information. Level order traversal The example below is a simple 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''' q.enqueue(node.left) if node.right ≠ '''null''' q.enqueue(node.right) Uses Inorder traversal It is particularly common to traverse a Binary Search Tree inorder, because it gives the values in increasing order. 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 . 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 . We can also use preorder traversals to evaluate Expression Trees . We scan the expression tree 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: Postorder traversal In comparison to preorder notation, which correlates nicely with a stack, postorder notation correlates with a queue. FUNCTIONAL TRAVERSAL We could perform the same traversals in a functional language like Haskell using code similar to this: |
|
|