Web hosts - Chapter 23 Data Structures and Collections 1177 The
Chapter 23 Data Structures and Collections 1177 The preorder traversal processes the value in each node as the node is visited. After processing the value in a given node, the preorder traversal processes the values in the left subtree, then the values in the right subtree. The preorder traversal of the tree in Fig. 23.19 is 27 13 6 17 42 33 48 Method PostorderHelper (lines 183 198) defines the steps for a postorder traversal. Those steps are as follows: 1. If the argument is null, return immediately. 2. Traverse the left subtree with a call to PostorderHelper (line 189). 3. Traverse the right subtree with a call to PostorderHelper (line 192). 4. Process the value in the node (line 195). The postorder traversal processes the value in each node after the values of all that node s children are processed. The postorder traversal of the tree in Fig. 23.19 is 6 17 13 33 48 42 27 The binary search tree facilitates duplicate elimination. While building a tree, the insertion operation recognizes attempts to insert a duplicate value, because a duplicate follows the same go left or go right decisions on each comparison as the original value did. Thus, the insertion operation eventually compares the duplicate with a node containing the same value. At this point, the insertion operation might simply discard the duplicate value. Searching a binary tree for a value that matches a key value is fast, especially for tightly packed trees. In a tightly packed tree, each level contains about twice as many elements as the previous level. Figure 23.19 is a tightly packed binary tree. A binary search tree with n elements has a minimum of log2n levels. Thus, at most log2n comparisons are required either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000. The chapter exercises present algorithms for other binary tree operations, such as performing a level-order traversal of a binary tree. The level-order traversal of a binary tree visits the nodes of the tree row by row, starting at the root-node level. On each level of the tree, a level-order traversal visits the nodes from left to right. 23.6.2 Binary Search Tree of IComparable Objects The binary tree example in Section 23.6.1 works nicely when all the data is of type int. Suppose that you want to manipulate a binary tree of double values. You could rewrite the TreeNode and Tree classes with different names and customize the classes to manipulate double values. Similarly, for each data type you could create customized versions of classes TreeNode and Tree. This results in a proliferation of code, which can become difficult to manage and maintain. The C++ programming language provides a technology called templates that enables us to write a class definition once, then have the compiler generate new versions of the class for any data type we choose. Ideally, we would like to define the functionality of a binary tree once and reuse that functionality for many data types. Languages like Java and C# provide polymorphic
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision tomcat hosting services