Problem Solving with Algorithms & Data Structures part 3/4

Problem Solving with Algorithms and Data Structures 3.0 by Brad Miller, David Ranum

(A Summary of ADT’s, Trees, and Binary Search)

 

Date

2022.08.01

 

Binary Tree Applications

 

We will look at parse trees as an example. We can represent a mathematical expression such as ((7 + 3) * ( 5- 2)) as a parse tree. Using the Hierarchical structure of trees, we can simply replace an entire subtree with one node once we have evaluated the expressions in the children.

 

The first step in building a parse tree is to break up the expression string into a list of tokens. There are four different kinds of tokens to consider: left parentheses, right parentheses, operators, and operands.

 

Using the information we can define our four rules as follows:

1. If the current token is a ‘(’, add a new node as the left child of the current node, and descend to the left child.
2. If the current token is in the list [‘+’,’-’,’/’,’*’], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.
3. If the current token is a number, set the root value of the current node to the number and return to the parent.
4. If the current token is a ‘)’, go to the parent of the current node.

 

Before writing the Python code, let’s look at an example of the rules outlined above in action. We will use the expression (3 + (4 * 5)). We will parse this expression into the following list of character tokens [‘(‘, ‘3’, ‘+’, ‘(‘, ‘4’, ‘*’, ‘5’, ‘)’, ‘)’]. Initially we will start out with a parse tree that consists of an empty root node. 

1. Create an empty tree.
2. Read ( as the first token. By rule 1, create a new node as the left child of the root. Make the current node this new child.
3. Read 3 as the next token. By rule 3, set the root value of the current node to 3 and go back up the tree to the parent.
4. Read + as the next token. By rule 2, set the root value of the current node to + and add a new node as the right child. The new right child becomes the current node.
5. Read a ( as the next token. By rule 1, create a new node as the left child of the current node. The new left child becomes the current node.
6. Read 4 as the next token. By rule 3, set the value of the current node to 4. Make the parent of 4 the current node.
7. Read * as the next token. By rule 2, set the root value of the current node to * and create a new right child. The new right child becomes the current node.
8. Read 5 as the next token. By rule 3, set the root value of the current node to 5. Make the parent of 5 the current node.
9. Read ) as the next token. By rule 4, we make the parent of * the current node.
10. Read ) as the next token. By rule 4, we make the parent of + the current node. At this point there is no parent for + so we are done.

 

From the example above, it is clear that we need to keep track of the current node as well as the parent of the current node. The tree interface provides us with a way to get children of a node, through the get_left_child and get_right_child methods, but how can we keep track of the parent? A simple solution to keeping track of parents as we traverse the tree is to use a stack. Whenever we want to descend to a child of the current node, we first push the current node on the stack. When we want to return to the parent of the current node, we pop the parent off the stack.

 

Along with the Stack and BinaryTree operations, the code for our parse tree builder is presented below.

 

 

Tree Traversals

 

We call the visitation of nodes a “traversal.” There are 3 types of tree traversals that are called preorder, inorder, and postorder.

 

• preorder : We visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.
• inorder : We recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.
• postorder : We recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.

 

An example of a preorder would be reading a book from front to back. The preorder traversal gives you the exact ordering. Starting at the root of the tree (the Book node) we will follow the preorder traversal instructions. We recursively call preorder on the left child, in his case Chapter 1. We again recursively call preorder on the left child to get to Section 1.1. Since Section 1.1 has no children, we do not make any additional recursive calls. When we are finished with Section 1.1, we move up the tree to Chapter 1. At this point we still need to visit the right subtree of Chapter 1, which is Section 1.2. As before we visit the left subtree, which brings us to Section 1.2.1, then we visit the node for Section 1.2.2. With Section 1.2 finished, we return to Chapter 1. Then we return to the Book node and follow the same procedure for Chapter 2.

 

The code for writing tree traversals is surprisingly elegant, largely because the traversals are written recursively.

 

preorder

 

The next is postorder traversal which follows closely with the code we wrote earlier to evaluate a parse tree.

 

postorder

 

The final traversal is the inorder traversal. All three traversal functions are simply changing the position of the print statement with respect to the two recursive function calls.

 

inorder

 

If we perform a simple inorder traversal of a parse tree we get our original expression back, without any parentheses. Going back to the parse tree code we can test this by making slight modifications.

 

Add this to the parse tree code written above

 

We get the original input expression