- 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
Printing Trees
You’ve seen how to traverse trees in different orders. You could always use the traversal method to print all the nodes in the tree, as shown in the Visualization tool. Using the in-order traversal would show the items in increasing order of their keys. On a two-dimensional output, you could use the in-order sequence to position the nodes along the horizontal axis and the level of each node to determine its vertical position. That could produce tree diagrams like the ones shown in the previous figures.
On a simple command-line output, it’s easier to print one node per line. The problem then becomes positioning the node on the line to indicate the shape of the tree. If you want the root node at the top, then you must compute the width of the full tree and place that node in the middle of the full width. More accurately, you would have to compute the width of the left and right subtrees and use that to position the root in order to show balanced and unbalanced trees accurately.
On the other hand, if you place the root at the left side of an output line and show the level of nodes as indentation from the leftmost column, it’s easy to print the tree on a terminal. Doing so essentially rotates the tree 90° to the left. Each node of the tree appears on its own line of the output. That allows you to forget about determining the width of subtrees and write a simple recursive method, as shown in Listing 8-11.
LISTING 8-11 Methods to Print Trees with One Node per Line
class BinarySearchTree(object): # A binary search tree class
…
def print(self, # Print the tree sideways with 1 node
indentBy=4): # on each line and indenting each level
self.__pTree(self.__root, # by some blanks. Start at root node
"ROOT: ", "", indentBy) # with no indent
def __pTree(self, # Recursively print a subtree, sideways
node, # with the root node left justified
nodeType, # nodeType shows the relation to its
indent, # parent and the indent shows its level
indentBy=4): # Increase indent level for subtrees
if node: # Only print if there is a node
self.__pTree(node.rightChild, "RIGHT: ", # Print the right
indent + " " * indentBy, indentBy) # subtree
print(indent + nodeType, node) # Print this node
self.__pTree(node.leftChild, "LEFT: ", # Print the left
indent + " " * indentBy, indentBy) # subtree
The public print() method calls the private __pTree() method to recursively print the nodes starting at the root node. It takes a parameter, indentBy, to control how many spaces are used to indent each level of the tree. It labels the nodes to show their relationship with their parent (if it wasn’t already clear from their indentation and relative positions). The recursive method implementation starts by checking the base case, an empty node, in which case nothing needs to be printed. For every other node, it first recursively prints the right subtree because that is the top of the printed version. It adds spaces to the indent so that subtree is printed further to the right. Then it prints the current node prefixed with its indentation and nodeType label. Lastly, it prints the left subtree recursively with the extended indentation. This produces an output such as that shown in Figure 8-25. The nodes are printed as {key, data} pairs and the figure example has no data stored with it.
)
FIGURE 8-25 Tree printed with indentation for node depth
In printing the tree like this, you use a different traversal order from the three standard ones. The print order uses a reverse in-order traversal of the tree.