CS61B, Fall 2002 Discussion #8 Amir KamilUC Berkeley 10/17/02Topics: Trees1 Trees1.1 IntroductionRecall our linked list definition:class List {ListNode head;class ListNode {Object data;ListNode next;}// other fields and methods}Let’s define some terminology. If a node points to a second node, we’ll call the first node the parent of thesecond, and the second the child of the first. Then in our linked list, each node can only have one child.(This is also true for a doubly-linked list, but the child points back to its parent.) What if we extend ourlist definition to allow a node to have two children?class NewList {NewListNode head;class NewListNode {Object data;NewListNode child1;NewListNode child2;}// other fields and methods}Let’s draw an example of such a structure:You may recall from CS61A that this structure is a tree. So a tree is just a linked list in which each node isno longer constrained to have a single child.What if we extend our definition further to add another child. And another? For any k > 0, we canextend our definition such that each node can have as many as k children. If our tree allows k children, we1Figure 1: An example of a general tree.call it a k-ary tree. Our definition above is a binary tree since each node may have up to two children. Thefields in a binary tree have special names, and the tree is conventionally defined as:class BinaryTree {BTNode root;class BTNode {Object data;BTNode left;BTNode right;}// other fields and methods}The naming of the two children make sense if you look at the above picture of the tree.A linked list is just a unary tree. The most general case of a tree is one in which k = ∞, and is definedas follows:class Tree {TreeNode root;class TreeNode {Object data;Vector children; // children nodes}// other fields and methods}Note that a constraint on linked lists carries over to trees. There cannot be any cycles in the tree. Inaddition, another constraint is introduced that was unnecessary for linked lists. Each node may only have asingle parent. Without these constraints, tree traversals may fall into infinite loops.1.2 TraversalsOur simple iterative traversal of a linked list will not work on trees, since multiple children of a node mustbe visited. Instead, we recursively traverse a tree. At each node, we must make one recursive call for eachchild.Before we write our traversals, we need to figure out in what order we will traverse the tree. There arethree ways to traverse the tree: preorder, inorder, and postorder. In a preorder traversal, the parent nodeis visited (i.e. whatever operation we are doing is done on the parent node) before any of its children. Aninorder traversal only makes sense for a binary tree, and is one in which the left child is visited, then theparent, and finally the right child. In a postorder traversal, the parent is visited after its children. Sinceinorder traversals only apply to binary trees, we will use them as our medium for defining the traversals.2Figure 2: Preorder, inorder, and postorder traversals shown in blue, green, and red, respectively.Pictorially we can execute the three traversals by drawing a line tightly around the tree, starting at theleft of the root. For a preorder traversal, we visit a node when we pass to its left. In an inorder traversal,we visit a node when we pass underneath it. And for a postorder traversal, we visit a node when we pass toits right.The actual definitions of the traversals are very simple. For simplicity, our traversals will just print outthe values in the tree. A more advanced traversal could take in objects corresponding to operations that wecould apply to each value.class BinaryTree {BTNode root;void preorder() {System.out.print("The tree:");head.preorder();System.out.println();}void inorder() {System.out.print("The tree:");head.inorder();System.out.println();}void preorder() {System.out.print("The tree:");head.postorder();System.out.println();}class BTNode {Object data;BTNode left;BTNode right;void preorder() {System.out.print(" " + data);left != null ? left.preorder();right != null ? right.preorder();}3Figure 3: An unbalanced tree, with the unbalanced node in blue.void inorder() {left != null ? left.inorder();System.out.print(" " + data);right != null ? right.inorder();}void postorder() {left != null ? left.postorder();right != null ? right.postorder();System.out.print(" " + data);}}// other fields and methods}1.3 Specialized TreesNow that we have defined a tree, what use are they to us? A general tree can be used to represent a heirarchyamong items, such as the Java class tree we saw before. But besides that, a tree is not very useful unlesswe introduce more properties that must be satisfied. Specifically, we would like there to be some orderingamong the values in the tree, and a fast and simple way to exploit that ordering. As such, the items inthe tree must be of type Comparable so that an ordering actually exists among them. We will ignore theexistence of equal items.Some additional terminology is necessary in order to allow us to assess the usefulness of specialized trees.A binary tree is balanced if for each node in the tree, the heights of its subtree differ by at most one. Abinary tree is complete if all but the last level in the tree are completely filled, and all nodes in the last levelare all the way to the left. A complete tree is always balanced.1.3.1 Binary Search TreesIf we are most interested in searching for individual items in a collection, or of obtaining a sorted list of allthe items, then we use a binary search tree (BST). Such a tree introduces only a single constraint among thedata items, that an inorder traversal on the tree visits the values in their natural order. This requires thetree to have two properties:• The subtree to the left of a value may only contain values less than it.• The subtree to the left of a value may only contain values greater than it.4Figure 4: A balanced, but incomplete, tree.Figure 5: A complete tree.5Figure 6: A binary search tree, with integer values.Figure 7: Insertion of the value 4 into the BST.It is easy to see that an inorder traversal on a tree that obeys the two properties will visit values in order.Thus we can obtain an ordered list of elements by executing an inorder traversal on the tree.Using the two BST properties, searching for an element is straightforward. Starting at the root, go leftif the target is less than the value at the current node, right if it is greater. If it is equal,
View Full Document
Unlocking...