|
In computer science, tree-traversal refers to the process of visiting each node in a 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. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...
In computer science, a binary tree is a tree data structure in which each node has at most two children. ...
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. 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 are: Performing an action on the current node (referred to as "visiting" the node); or repeating the process with the subtrees rooted at our left and right children. Thus the process is most easily described through recursion. This is a list of data structures. ...
In computer science, a linked list is one of the fundamental data structures used in computer programming. ...
In computer programming, an array, also known as a vector or list, is one of the simplest data structures. ...
This article is about the concept of recursion. ...
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.) Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
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 a 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
| Image File history File links No higher resolution available. ...
A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13. ...
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. 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 the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the...
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 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 the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the...
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. A queue (pronounced /kuË/) 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 are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ...
Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. ...
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). A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13. ...
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. Structural induction is a proof method that is used in mathematical logic (e. ...
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. A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13. ...
We can also use preorder traversals to evaluate expression trees. A parse tree or concrete syntax tree is a tree that represents the syntactic structure of a string according to some formal grammar. ...
We scan the expression tree from right to left, placing the elements in a stack. Look up Stack in Wiktionary, the free dictionary. ...
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 | 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: Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
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. Recursive traversal may be converted into an iterative one using various well-known methods.
See also Tree programming refers to the use of a programming language to analyze data trees, in a way unique from conventional programming languages. ...
It has been suggested that this article or section be merged with Reverse Polish notation. ...
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. ...
External links
References |
Feeds |
Contact