This program demonstrates a few routines for processing binary sort trees. It uses a binary sort tree of strings. The user types in strings. The user’s string is converted to lower case, and — if it is not already in the tree — it is inserted into the tree. Then the number of nodes in the tree and a list of items in the tree are output. The program ends when the user enters an empty string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | /******************************************************* * MYCPLUS Sample Code - https://www.mycplus.com * * * * This code is made available as a service to our * * visitors and is provided strictly for the * * purpose of illustration. * * * * Please direct all inquiries to saqib at mycplus.com * *******************************************************/ public class SortTreeDemo { static class TreeNode { // An object of type TreeNode represents one node // in a binary tree of strings. String item; // The data in this node. TreeNode left; // Pointer to left subtree. TreeNode right; // Pointer to right subtree. TreeNode(String str) { // Constructor. Make a node containing the specified string. item = str; } } // end nested class TreeNode static TreeNode root; // Pointer to the root node in a binary tree. This // tree is used in this program as a binary sort tree. // The tree is not allowed to contain duplicate // items. When the tree is empty, root is null. public static void main(String[] args) { TextIO.putln("This programs stores strings that you enter in a binary sort"); TextIO.putln("tree. After each items is inserted, the contents of the tree"); TextIO.putln("are displayed. The number of nodes in the tree is also output."); TextIO.putln(" Any string you enter will be converted to lower case."); TextIO.putln("Duplicate entries are ignored."); while (true) { // Get one string from the user, insert it into the tree, // and print some information about the tree. Exit if the // user enters an empty string. Note that all strings are // converted to lower case. TextIO.putln("\n\nEnter a string to be inserted, or press return to end."); TextIO.put("? "); String item; // The user's input. item = TextIO.getln().trim().toLowerCase(); if (item.length() == 0) break; if (treeContains(root,item)) { // Don't insert a second copy of an item that is already // in the tree. TextIO.putln("\nThat item is already in the tree."); } else { treeInsert(item); // Add user's string to the tree. TextIO.putln("\nThe tree contains " + countNodes(root) + " items."); TextIO.putln("\nContents of tree:\n"); treeList(root); } } // end while TextIO.putln("\n\nExiting program."); } // end main() static void treeInsert(String newItem) { // Add the item to the binary sort tree to which the global // variable "root" refers. (Note that root can't be passed as // a parameter to this routine because the value of root might // change, and a change in the value of a formal parameter does // not change the actual parameter.) if ( root == null ) { // The tree is empty. Set root to point to a new node containing // the new item. This becomes the only node in the tree. root = new TreeNode( newItem ); return; } TreeNode runner; // Runs down the tree to find a place for newItem. runner = root; // Start at the root. while (true) { if ( newItem.compareTo(runner.item) < 0 ) { // Since the new item is less than the item in runner, // it belongs in the left subtree of runner. If there // is an open space at runner.left, add a new node there. // Otherwise, advance runner down one level to the left. if ( runner.left == null ) { runner.left = new TreeNode( newItem ); return; // New item has been added to the tree. } else runner = runner.left; } else { // Since the new item is greater than or equal to the item in // runner it belongs in the right subtree of runner. If there // is an open space at runner.right, add a new node there. // Otherwise, advance runner down one level to the right. if ( runner.right == null ) { runner.right = new TreeNode( newItem ); return; // New item has been added to the tree. } else runner = runner.right; } } // end while } // end treeInsert() static boolean treeContains( TreeNode root, String item ) { // Return true if item is one of the items in the binary // sort tree to which root points. Return false if not. if ( root == null ) { // Tree is empty, so it certainly doesn't contain item. return false; } else if ( item.equals(root.item) ) { // Yes, the item has been found in the root node. return true; } else if ( item.compareTo(root.item) < 0 ) { // If the item occurs, it must be in the left subtree. return treeContains( root.left, item ); } else { // If the item occurs, it must be in the right subtree. return treeContains( root.right, item ); } } // end treeContains() static void treeList(TreeNode node) { // Print the items in the tree in postorder, one item // to a line. Since the tree is a sort tree, the output // will be in increasing order. if ( node != null ) { treeList(node.left); // Print items in left subtree. TextIO.putln(" " + node.item); // Print item in the node. treeList(node.right); // Print items in the right subtree. } } // end treeList() static int countNodes(TreeNode node) { // Count the nodes in the binary tree to which node // points. Return the answer. if ( node == null ) { // Tree is empty, so it contains no nodes. return 0; } else { // Add up the root node and the nodes in its two subtrees. int leftCount = countNodes( node.left ); int rightCount = countNodes( node.right ); return 1 + leftCount + rightCount; } } // end countNodes() } // end class SortTreeDemo |
