Lecture 34OutlineGeneral Binary Tree AlgorithmTreeSizeCopying a TreeTreeCopyDestroying a TreeTreeClearHuffman Code TreesBag ClassBinary Search Trees 1Binary Search Trees 2Finding ItemsInserting ItemsErasing Items 1Erasing Items 2Erasing Items 3In-class ExercisseFriday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 1Lecture 34Log into Linux. No files to copy; will finish bintree.h from last time.Reminders: Project 6 is due today. NO CLASS on Monday (instructor out of town)Homework 8 posted to course webpage. Due next Friday.Project 7 posted. Due after Thanksgiving break, but really should be completed before break...Questions?Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 2OutlineFinish binary tree toolkitTreeSize - reviewTreeCopyTreeClearHuffman code trees – Project 7Binary search treesFriday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 3General Binary Tree AlgorithmReview: Many binary tree operations use a post-order form as follows:1. Handle the case of an empty tree.2. Do the computation on the left subtree.3. Do the computation on the right subtree.4. Combine the results into the result for the entire tree.For example, counting the number of nodes in the tree.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 4TreeSizeTreeSize receives a BTNode root pointer and returns the number of nodes in the tree. The algorithm is:1. If rootPtr is the null pointer, return 02. Set leftCount = TreeSize (rootPtr->Left( ))3. Set rightCount = TreeSize(rootPtr->Right( ))4. Compute and return the total number of nodesWrite the code for this function. Compile and run the driver program to test it.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 5Copying a TreeClasses implemented using the binary tree toolkit will need to make copies of a tree.This function follows the general binary tree algorithm. We copy a tree by first copying its children (subtrees).Once we have copies of the children, we can make a copy of the whole tree by making a copy of the root node and hooking it up to the children copies.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 6TreeCopyTreeCopy receives a BTNode root pointer and returns a BTNode pointer that points to a copy of the tree. The algorithm is simply:1. If root is the null pointer, return the null pointer2. Set leftCopy to TreeCopy (rootPtr->Left( ))3. Set rightCopy to TreeCopy (rootPtr->Right( ))4. Return a pointer to a new BTNode with rootPtr->Data( ) as is data value and leftCopy and rightCopy as it left and right child links, respectively.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 7Destroying a TreeDestroying a tree (i.e., returning all of the nodes to the system) also is a recursive algorithm that follows the general binary tree algorithm. We destroy a tree by first destroying its children (subtrees).Once the children are destroyed, all that is left is to destroy the root node.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 8TreeClearTreeClear receives a BTNode root pointer and destroys the tree. The algorithm is:1. If root is the null pointer, return.2. Destroy the left subtree using TreeClear(rootPtr->Left( )).3. Destroy the right subtree using TreeClear(rootPtr->Right( )).4. Delete rootPtr's node.Write the code for TreeCopy and TreeClear. Compile and run the driver program to test them.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 9Huffman Code TreesBinary trees by themselves are not particularly useful. But as with arrays and linked lists, they can be used as an implementation technique for other data structures.The Huffman code tree in Project 7 is one such data structure. Since the code consists of two values (0 and 1), a binary tree can be used to represent each code as a path from the root to a leaf that contains the character encoded by the path. Class operations encode & decode messages using the constructed tree.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 10Bag ClassAnother data structure that can be represented by a binary tree is the Bag class.Will use a binary tree in a particular way to make finding items in a bag more efficient than linear search.Today we will concentrate on the storage rules and the basic algorithms for finding, inserting, and erasing data items. Next class we will look at the implementation code for Bag operations.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 11Binary Search TreesThe storage rules we will use is called a binary search tree (BST). A BST is defined as a binary tree with the following ordering:For each node, the data values in the left subtree are less than or equal to the node value.For each node, the data values in the right subtree are greater than the node value.Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 12Binary Search TreesHere are some examples:2510 3730 651553 30505962Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 13Finding ItemsGiven root of BST on the right. How do we find 37?37 < 50, go left37 > 30, go right37 > 35, go right37 = 37, found itemWhat about 58?50 < 58, go right55 < 58, go right58 < 60, go leftnull subtree, item not found5030 5525 35 53 6010 32 37 6215Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 14Inserting ItemsInserting items looks for the place item would be if it were in the tree (i.e., use the find algorithm).First inserted item becomes root.Insert the following items: 35, 18, 25, 48, 72, 60. Tree on right shows first three inserts.Note that because of the ordering, an in-order print of the tree produces the values in ascending order.351825Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 15Erasing ItemsThree cases for erasing items.Item is in a leaf, i.e., in a node with 0 children. E.g., 62. Just delete it; set child pointer to null.Item is in a node with 1 child. E.g. 25. Replace the node with its child and delete it.Item is in a node with 2 children. E.g., 50.5030 5525 35 53 6010 32 37 621537Friday, November 12 CS 215 Fundamentals of Programming II - Lecture 34 16Erasing
View Full Document
Unlocking...