- 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
The BinarySearchTreeTester.py Program
It’s always a good idea to test the functioning of a code module by writing tests that exercise each operation. Writing a comprehensive set of tests is an art in itself. Another useful strategy is to write an interactive test program that allows you to try a series of operations in different orders and with different arguments. To test all the BinarySearchTree class methods shown, you can use a program like BinarySearchTreeTester.py shown in Listing 8-12.
LISTING 8-12 The BinarySearchTreeTester.py Program
# Test the BinarySearchTree class interactively
from BinarySearchTree import *
theTree = BinarySearchTree() # Start with an empty tree
theTree.insert("Don", "1974 1") # Insert some data
theTree.insert("Herb", "1975 2")
theTree.insert("Ken", "1979 1")
theTree.insert("Ivan", "1988 1")
theTree.insert("Raj", "1994 1")
theTree.insert("Amir", "1996 1")
theTree.insert("Adi", "2002 3")
theTree.insert("Ron", "2002 3")
theTree.insert("Fran", "2006 1")
theTree.insert("Vint", "2006 2")
theTree.insert("Tim", "2016 1")
def print_commands(names): # Print a list of possible commands
print('The possible commands are', names)
def clearTree(): # Remove all the nodes in the tree
while not theTree.isEmpty():
data, key = theTree.root()
theTree.delete(key)
def traverseTree(traverseType="in"): # Traverse & print all nodes
for key, data in theTree.traverse(traverseType):
print('{', str(key), ', ', str(data), '}', end=' ')
print()
commands = [ # Command names, functions, and their parameters
['print', theTree.print, []],
['insert', theTree.insert, ('key', 'data')],
['delete', theTree.delete, ('key', )],
['search', theTree.search, ('key', )],
['traverse', traverseTree, ('type', )],
['clear', clearTree, []],
['help', print_commands, []],
['?', print_commands, []],
['quit', None, []],
]
# Collect all the command names in a list
command_names = ", ".join(c[0] for c in commands)
for i in range(len(commands)): # Put command names in argument list
if commands[i][1] == print_commands: # of print_commands
commands[i][2] = [command_names]
# Create a dictionary mapping first character of command name to
# command specification (name, function, parameters/args)
command_dict = dict((c[0][0], c) for c in commands)
# Print information for interactive loop
theTree.print()
print_commands(command_names)
ans = ' '
# Loop to get a command from the user and execute it
while ans[0] != 'q':
print('The tree has', theTree.nodes(), 'nodes across',
theTree.levels(), 'levels')
ans = input("Enter first letter of command: ").lower()
if len(ans) == 0:
ans = ' '
if ans[0] in command_dict:
name, function, parameters = command_dict[ans[0]]
if function is not None:
print(name)
if isinstance(parameters, list):
arguments = parameters
else:
arguments = []
for param in parameters:
arg = input("Enter " + param + " for " + name + " " +
"command: ")
arguments.append(arg)
try:
result = function(*arguments)
print('Result:', result)
except Exception as e:
print('Exception occurred')
print(e)
else:
print("Invalid command: '", ans, "'")
This program allows users to enter commands by typing them in a terminal interface. It first imports the BinarySearchTree module and creates an empty tree with it. Then it puts some data to it, using insert() to associate names with some strings. The names are the keys used to place the nodes within the tree.
The tester defines several utility functions to print all the possible commands, clear all the nodes from the tree, and traverse the tree to print each node. These functions handle commands in the command loop below.
The next part of the tester program defines a list of commands. For each one, it has a name, a function to execute the command, and a list or tuple of arguments or parameters. This is more advanced Python code than we’ve shown so far, so it might look a little strange. The names are what the user will type (or at least their first letter), and the functions are either methods of the tree or the utility functions defined in the tester. The arguments and parameters will be processed after the user chooses a command.
To provide a little command-line help, the tester concatenates the list of command names into a string, separating them with commas. This operation is accomplished with the join() method of strings. The text to place between each command name is the string (a comma and a space), and the argument to join() is the list of names. The program uses a list comprehension to iterate through the command specifications in commands and pull out the first element, which is the command name: ”, ”.join(c[0] for c in commands). The result is stored in the command_names variable.
Then the concatenated string of command names needs to get inserted in the argument list for the print_commands function. That’s done in the for loop. Two entries have the print_commands function: the help and ? commands.
The last bit of preparation for the command loop creates a dictionary, command_dict, that maps the first character of each command to the command specification. You haven’t used this Python data structure yet. In Chapter 11, “Hash Tables,” you see how they work, so if you’re not familiar with them, think of them as an associative array—an array indexed by a string instead of integer. You can assign values in the array and then look them up quickly. In the tester program, evaluating command_dict['p'] would return the specification for the print command, namely ['print', theTree.print, []]. Those specifications get stored in the dictionary using the compact (but cryptic) comprehension: dict((c[0][0], c) for c in commands).
The rest of the tester implements the command loop. It first prints the tree on the terminal, followed by the list of commands. The ans variable holds the input typed by the user. It gets initialized to a space so that the command loop starts and prompts for a new command.
The command loop continues until the user invokes the quit command, which starts with q. Inside the loop body, the number of nodes and levels in the tree is printed, and then the user is asked for a command. The string that is returned by input() is converted to lowercase to simplify the command lookup. If the user just pressed Return, there would be no first character in the string, so you would fill in a ? to make the default response be to print all the command names again.
In the next statement—if ans[0] in command_dict:—the tester checks whether the first character in the user’s response is one of the known commands. If the character is recognized, it extracts the name, function, and parameters from the specification stored in the command_dict. If there’s a function to execute, then it will be processed. If not, then the user asked to quit, and the while loop will exit. When the first character of the user’s response does not match a command, an error message is printed, and the loop prompts for a new command.
After the command specification is found, it either needs to prompt the user for the arguments to use when calling the function or get them from the specification. This choice is based on whether the parameters were specified as Python tuple or list. If it’s a tuple, the elements of the tuple are the names of the parameters. If it’s a list, then the list contains the arguments of the function. For tuples, the user is prompted to enter each argument by name, and the answers are stored in the arguments list. After the arguments are determined, the command loop tries calling the function with the arguments list using result = function(*arguments). The asterisk (*) before the arguments is not a multiplication operator. It means that the arguments list should be used as the list of positional arguments for the function. If the function raises any exceptions, they are caught and displayed. Otherwise, the result of the function is printed before looping to get another command.
Try using the tester to run the four main operations: search, insert, traverse, and delete. For the deletion, try deleting nodes with 0, 1, and 2 child nodes to see the effect. When you delete a node with 2 children, predict which successor node will replace the deleted node and see whether you’re right.