Chapter 9.4.1 Tree Traversal | Introduction to Programming Using Java
9.4.1 Tree Traversal
Consider any node in a binary tree. Look at that node together with all its descendents (that is, its children, the children of its children, and so on). This set of nodes forms a binary tree, which is called a subtree of the original tree. For example, in the picture, nodes 2, 4, and 5 form a subtree.
This subtree is called the left subtree of the root. Similarly, nodes 3 and 6 make up the right subtree of the root. We can consider any non-empty binary tree to be made up of a root node, a left subtree, and a right subtree. Either or both of the subtrees can be empty. This is a recursive definition, matching the recursive definition of the TreeNode class. So it should not be a surprise that recursive subroutines are often used to process trees.
Consider the problem of counting the nodes in a binary tree. (As an exercise, you might try to come up with a non-recursive algorithm to do the counting, but you shouldn’t expect to find one.) The heart of problem is keeping track of which nodes remain to be counted. It’s not so easy to do this, and in fact it’s not even possible without an auxiliary data structure such as a stack or queue.
With recursion, however, the algorithm is almost trivial. Either the tree is empty or it consists of a root and two subtrees. If the tree is empty, the number of nodes is zero. (This is the base case of the recursion.) Otherwise, use recursion to count the nodes in each subtree. Add the results from the subtrees together, and add one to count the root. This gives the total number of nodes in the tree. Written out in Java:
Or, consider the problem of printing the items in a binary tree. If the tree is empty, there is nothing to do. If the tree is non-empty, then it consists of a root and two subtrees. Print the item in the root and use recursion to print the items in the subtrees. Here is a subroutine that prints all the items on one line of output:
This routine is called “preorderPrint” because it uses a preorder traversal of the tree. In a preorder traversal, the root node of the tree is processed first, then the left subtree is traversed, then the right subtree. In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed.
And in an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed. Printing subroutines that use postorder and inorder traversal differ from preorderPrint only in the placement of the statement that outputs the root item:
Each of these subroutines can be applied to the binary tree shown in the illustration at the beginning of this section. The order in which the items are printed differs in each case:
In preorderPrint, for example, the item at the root of the tree, 1, is output before anything else. But the preorder printing also applies to each of the subtrees of the root. The root item of the left subtree, 2, is printed before the other items in that subtree, 4 and 5. As for the right subtree of the root, 3 is output before 6. A preorder traversal applies at all levels in the tree. The other two traversal orders can be analyzed similarly.
SEE MORE:
- Chapter 9.4.2 Binary Sort Trees | Introduction to Programming Using Java
- Chapter 10.1.1 Generic Programming in Smalltalk | Introduction to Programming Using Java
- Chapter 10.1.2 Generic Programming in C++ | Introduction to Program ming Using Java
- Chapter 10.1.3 Generic Programming in Java | Introduction to Programming Using Java
- Chapter 10.1.4 The Java Collection Framework | Introduction to Program ming Using Java
- Chapter 10.1.5 Iterators and for-each Loops | Introduction to Programming Using Java
- Chapter 11.2.1 Reading and Writing Files | Introduction to Program ming Using Java
- Chapter 11.4.2 TCP/IP and Client/Server | Introduction to Program ming Using Java
- Chapter 12 Advanced GUI Programming | Images and Resources | Introduction to Program ming Using Java
19 thoughts on “Chapter 9.4.1 Tree Traversal | Introduction to Programming Using Java”