- Why Use Binary Trees?
- Tree Terminology
- An Analogy
- How Do Binary Search Trees Work?
- Finding a Node
- Inserting a Node
- Traversing the Tree
- Finding Minimum and Maximum Key Values
- Deleting a Node
- The Efficiency of Binary Search Trees
- Trees Represented as Arrays
- Printing Trees
- Duplicate Keys
- The BinarySearchTreeTester.py Program
- The Huffman Code
- Summary
- Questions
- Experiments
- Programming Projects
This chapter is from the book
This chapter is from the book
This chapter is from the book
Programming Projects
Writing programs to solve the Programming Projects helps to solidify your understanding of the material and demonstrates how the chapter’s concepts are applied. (As noted in the Introduction, qualified instructors may obtain completed solutions to the Programming Projects on the publisher’s website.)
8.1 Alter the BinarySearchTree class described in this chapter to allow nodes with duplicate keys. Three methods are affected: __find(), insert(), and delete(). Choose to insert new left children at the shallowest level among equal keys, as shown on the left side of Figure 8-26, and always find and delete the deepest among equal keys. More specifically, the __find() and search() methods should return the deepest among equal keys that it encounters but should allow an optional parameter to specify finding the shallowest. The insert() method must handle the case when the item to be inserted duplicates an existing node, by inserting a new node with an empty left child below the deepest duplicate key. The delete() method must delete the deepest node among duplicate keys, thus providing a LIFO or stack-like behavior among duplicate keys. Think carefully about the deletion cases and whether the choice of successor nodes changes. Demonstrate how your implementation works on a tree inserting several duplicate keys associated with different values. Then delete those keys and show their values to make it clear that the last duplicate inserted is the first duplicate deleted.
){kind=link}
8.2 Write a program that takes a string containing a postfix expression and builds a binary tree to represent the algebraic expression like that shown in Figure 8-16. You need a BinaryTree class, like that of BinarySearchTree, but without any keys or ordering of the nodes. Instead of find(), insert(), and delete() methods, you need the ability to make single node BinaryTrees containing a single operand and a method to combine two binary trees to make a third with an operator as the root node. The syntax of the operators and operands is the same as what was used in the PostfixTranslate.py module from Chapter 4. You can use the nextToken() function in that module to parse the input string into operator and operand tokens. You don’t need the parentheses as delimiters because postfix expressions don’t use them. Verify that the input expression produces a single algebraic expression and raise an exception if it does not. For valid algebraic binary trees, use pre-, in-, and post-order traversals of the tree to translate the input into the output forms. Include parentheses for the in-order traversal to make the operator precedence clear in the output translation. Run your program on at least the following expressions:
){kind=link}
91 95 + 15 + 19 + 4 *
B B * A C 4 * * –
42
A 57 # this should produce an exception
+ / # this should produce an exception
8.3 Write a program to implement Huffman coding and decoding. It should do the following:
Accept a text message (string).- Create a Huffman tree for this message.
- Create a code table.
- Encode the text message into binary.
- Decode the binary message back to text.
- Show the number of bits in the binary message and the number of characters in the input message.
If the message is short, the program should be able to display the Huffman tree after creating it. You can use Python string variables to store binary messages as arrangements of the characters 1 and 0. Don’t worry about doing actual bit manipulation using bytearray unless you really want to. The easiest way to create the code table in Python is to use the dictionary (dict) data type. If that is unfamiliar, it’s essentially an array that can be indexed by a string or a single character. It’s used in the BinarySearchTreeTester.py module shown in Listing 8-12 to map command letters to command records. If you choose to use an integer indexed array, you can use Python’s ord() function to convert a character to an integer but be aware that you will need a large array if you allow arbitrary Unicode characters such as emojis (☺) in the message.
8.4 Measuring tree balance can be tricky. You can apply two simple measures: node balance and level (or height) balance. As mentioned previously, balanced trees have an approximately equal number of nodes in their left and right subtrees. Similarly, the left and right subtrees must have an approximately equal number of levels (or height). Extend the BinarySearchTree class by writing the following methods:
nodeBalance()—Computes the number of nodes in the right subtree minus the number of nodes in the left subtree
levelBalance()—Computes the number of levels in the right subtree minus the number of levels in the left subtree
unbalancedNodes(by=1)— Returns a list of node keys where the absolute value of either of the balance metrics exceeds the by threshold, which defaults to 1
These three methods all require (recursive) helper methods that traverse subtrees rooted at nodes inside the tree. In a balanced tree, the list of unbalanced nodes would be empty. Try your measures by inserting the following four lists of keys into an empty BinarySearchTree (in order, left to right), printing the resulting 15-node tree, printing the node and level balance of the resulting root node, and then printing the list of unbalanced keys with by=1 and by=2.
[7, 6, 5, 4, 3, 2, 1, 8, 12, 10, 9, 11, 14, 13, 15], [8, 4, 5, 6, 7, 3, 2, 1, 12, 10, 9, 11, 14, 13, 15], [8, 4, 2, 3, 1, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15], [8, 4, 2, 3, 1, 6, 5, 7, 12, 10, 9, 11, 14, 13, 8.5]
8.5 Every binary tree can be represented as an array, as described in the section titled “Trees Represented as Arrays.” The reverse of representing an array as a tree, however, works only for some arrays. The missing nodes of the tree are represented in the array cells as some predefined value—such as None—that cannot be a value stored at a tree node. If the root node is missing in the array, then the corresponding tree cannot be built. Write a function that takes an array as input and tries to make a binary tree from its contents. Every cell that is not None is a value to store at a tree node. When you come across a node without a parent node (other than the root node), the function should raise an exception indicating that the tree cannot be built. Note that the result won’t necessarily be a binary search tree, just a binary tree. Hint: It’s easier to work from the leaf nodes to the root, building nodes for each cell that is not None and storing the resulting node back in the same cell of the input array for retrieval when it is used as a subtree of a node on another level. Print the result of running the function on the following arrays where n = None. The values in the array can be stored as either the key or the value of the node because the tree won’t be interpreted as a binary search tree.
[], [n, n, n], [55, 12, 71], [55, 12, n, 4], [55, 12, n, 4, n, n, n, n, 8, n, n, n, n, n, n, n, n, 6, n], [55, 12, n, n, n, n, 4, n, 8, n, n, n, n, n, n, n, n, 6, n]