22.10. Singleton and Unmodifiable Collections and Maps
20.4. Binary Trees
A list, stack, or queue is a linear structure that consists of a sequence of elements. A binary tree is a hierarchical structure. It is either empty or consists of an element called the root and two distinct binary trees called the left subtree and right subtree . Examples of binary trees are shown in Figure 20.17.
Figure 20.17. Each node in a binary tree has zero, one, or two branches.
The root of a left (right) subtree of a node is called a left (right) child of the node. A node without children is called a leaf . A special type of binary tree called a binary search tree is often useful. A binary search tree (with no duplicate elements) has the property that for every node in the tree, the value of any node in its left subtree is less than the value of the node, and the value of any node in its right subtree is greater than the value of the node. The binary trees in Figure 20.17 are all binary search trees. This section is concerned with binary search trees.
20.4.1. Representing Binary Trees
A binary tree can be represented using a set of linked nodes. Each node contains a value and two links named left and right that reference the left child and right child, respectively, as shown in Figure 20.18.
Figure 20.18. A binary tree can be represented using a set of linked nodes.
A node can be defined as a class, as follows :
class TreeNode { Object element; TreeNode left; TreeNode right; public TreeNode(Object o) { element = o; } }
The variable root refers to the root node of the tree. If the tree is empty, root is null . The following code creates the first three nodes of the tree in Figure 20.18:
// Create the root node TreeNode root = new TreeNode( new Integer( 60 )); // Create the left child node root.left = new TreeNode( new Integer( 55 )); // Create the right child node root.right = new TreeNode( new Integer( 100 ));
20.4.2. Inserting an Element into a Binary Search Tree
If a binary tree is empty, create a root node with the new element. Otherwise , locate the parent node for the new element node. If the new element is less than the parent element, the node for the new element becomes the left child of the parent. If the new element is greater than the parent element, the node for the new element becomes the right child of the parent. Here is the algorithm:
if (root == null ) root = new TreeNode(element); else { // Locate the parent node current = root; while (current != null ) if (element value < the value in current.element) { parent = current; current = current.left; } else if (element value > the value in current.element) { parent = current; current = current.right; } else return false ; // Duplicate node not inserted // Create the new node and attach it to the parent node if (element < parent.element) parent.left = new TreeNode(element); else parent.right = new TreeNode(element); return true ; // Element inserted }
For example, to insert 101 into the tree in Figure 20.18, the parent is the node for 107. The new node for 101 becomes the left child of the parent. To insert 59 into the tree, the parent is the node for 57. The new node for 59 becomes the right child of the parent. Both of these insertions are shown in Figure 20.19.
Figure 20.19. Two new elements are inserted into the tree.
20.4.3. Tree Traversal
Tree traversal is the process of visiting each node in the tree exactly once. There are several ways to traverse a tree. This section presents inorder , preorder , postorder, depth-first, and breadth-first traversals.
With inorder traversal, the left subtree of the current node is visited first, then the current node, and finally the right subtree of the current node. The inorder traversal displays all the nodes in a binary search tree in increasing order.
With postorder traversal, the left subtree of the current node is visited first, then the right subtree of the current node, and finally the current node itself.
With preorder traversal, the current node is visited first, then the left subtree of the current node, and finally the right subtree of the current node. Depth-first traversal is the same as preorder traversal.
With breadth-first traversal, the nodes are visited level by level. First the root is visited, then all the children of the root from left to right, then the grandchildren of the root from left to right, and so on.
For example, in the tree in Figure 20.19, the inorder is 45 55 57 59 60 67 100 101 107. The postorder is 45 59 57 55 67 101 107 100 60. The preorder is 60 55 45 57 59 100 67 107 101. The breadth-first traversal is 60 55 100 45 57 67 107 59 101.
20.4.4. The Binary Tree Class
Let us define a binary tree class named BinaryTree with insert, inorder traversal, postorder traversal, and preorder traversal, as shown in Figure 20.20. Its implementation is given in Listing 20.8.
Figure 20.20. BinaryTree implements a binary tree with operations insert , inorder , preorder , and postorder .
Listing 20.8. BinaryTree.java
(This item is displayed on pages 680 - 682 in the print version)
1 public class BinaryTree { 2 private TreeNode root; 3 private int size = ; 4 5 /** Create a default binary tree */ 6 public BinaryTree() { 7 } 8 9 /** Create a binary tree from an array of objects */ 10 public BinaryTree(Object[] objects) { 11 for ( int i = ; i < objects.length; i++) 12 insert(objects[i]); 13 } 14 15 /** Insert element o into the binary tree 16 * Return true if the element is inserted successfully */ 17 public boolean insert(Object o) { 18 if (root == null ) 19 root = new TreeNode(o); // Create a new root 20 else { 21 // Locate the parent node 22 TreeNode parent = null ; 23 TreeNode current = root; 24 while (current != null ) 25 if (((Comparable)o).compareTo(current.element) < ) { 26 parent = current; 27 current = current.left; 28 } 29 else if (((Comparable)o).compareTo(current.element) > ) { 30 parent = current; 31 current = current.right; 32 } 33 else 34 return false ; // Duplicate node not inserted 35 36 // Create the new node and attach it to the parent node 37 if (((Comparable)o).compareTo(parent.element) < ) 38 parent.left = new TreeNode(o); 39 else 40 parent.right = new TreeNode(o); 41 } 42 43 size++; 44 return true ; // Element inserted 45 } 46 47 /** Inorder traversal */ 48 public void inorder() { 49 inorder(root); 50 } 51 52 /** Inorder traversal from a subtree */ 53 private void inorder(TreeNode root) { 54 if (root == null ) return ; 55 inorder(root.left); 56 System.out.print(root.element + " " ); 57 inorder(root.right); 58 } 59 60 /** Postorder traversal */ 61 public void postorder() { 62 postorder(root); 63 } 64 65 /** Postorder traversal from a subtree */ 66 private void postorder(TreeNode root) { 67 if (root == null ) return ; 68 postorder(root.left); 69 postorder(root.right); 70 System.out.print(root.element + " " ); 71 } 72 73 /** Preorder traversal */ 74 public void preorder() { 75 preorder(root); 76 } 77 78 /** Preorder traversal from a subtree */ 79 private void preorder(TreeNode root) { 80 if (root == null ) return ; 81 System.out.print(root.element + " " ); 82 preorder(root.left); 83 preorder(root.right); 84 } 85 86 /** Inner class tree node */ 87 private static class TreeNode { 88 Object element; 89 TreeNode left; 90 TreeNode right; 91 92 public TreeNode(Object o) { 93 element = o; 94 } 95 } 96 97 /** Get the number of nodes in the tree */ 98 public int getSize() { 99 return size; 100 } 101 } |
The insert(Object o) method (lines 17 “45) creates a node for element o and inserts it into the tree. If the tree is empty, the node becomes the root. Otherwise, the method finds an appropriate parent for the node to maintain the order of the tree. If the element is already in the tree, the method returns false ; otherwise it returns true .
The inorder() method (lines 48 “50) invokes inorder(root) to traverse the entire tree. The method inorder(TreeNode root) traverses the tree with the specified root. This is a recursive method. It recursively traverses the left subtree, then the root, and finally the right subtree. The traversal ends when the tree is empty.
The postorder() method (lines 61 “63) and the preorder() method (lines 74 “76) are implemented similarly using recursion.
Listing 20.9 gives an example that creates a binary tree using BinaryTree . Add strings into the binary tree and traverse the tree in inorder, postorder, and preorder. A sample run of the program is shown in Figure 20.21.
Figure 20.21. The program creates a tree, inserts elements into it, and displays them in inorder, postorder, and preorder.
Listing 20.9. TestBinaryTree.java
(This item is displayed on pages 682 - 683 in the print version)
1 public class TestBinaryTree { 2 public static void main(String[] args) { 3 BinaryTree tree = new BinaryTree(); 4 tree.insert( "George" ); 5 tree.insert( "Michael" ); 6 tree.insert( "Tom" ); 7 tree.insert( "Adam" ); 8 tree.insert( "Jones" ); 9 tree.insert( "Peter" ); 10 tree.insert( "Daniel" ); 11 System.out.print( "Inorder (sorted): " ); 12 tree.inorder(); 13 System.out.print( "\nPostorder: " ); 14 tree.postorder(); 15 System.out.print( "\nPreorder: " ); 16 tree.preorder(); 17 System.out.print( "\nThe number of nodes is " + tree.getSize() ); 18 } 19 } |
After all the elements are inserted, the tree should appear as shown in Figure 20.22.
Figure 20.22. The binary search tree is pictured here after line 10 is executed.
If the elements are inserted in a different order (e.g., Daniel, Adam, Jones, Peter, Tom, Michael, George), the tree will look different. However, the inorder is the same as long as the set of elements is the same. The inorder displays a sorted list.
EAN: N/A
Pages: 503