Algorithms and Data Structures
Exercise 6
Tree 1 (Parse Tree)

Question 1 [PostScript for printing]

(1) Which nodes of the figure correspond to the following names?
Tree
root
parent of G
child of B
sibling of H
external node
internal node
height
level of C
path length

(2) Draw a parse tree of the following in-order formula: 

4*(3+2)+1

(3) Write down results of traversing the parse tree written in (2) by pre-order, in-order and post-order.

The following figure is a example of a parse tree of 1+2*3.
parse tree

The following formulas are result of traversing the tree. 

 preorder: +1*23
  inorder: 1+2*3
postorder: 123*+
Question 2

Write the following C-functions using recursive calls: 

void preorder(NodePointer node);
void inorder(NodePointer node);
void postorder(NodePointer node);

Those functions traverse with displaying contents of nodes. Use ex06-2-skel.c. 

Program execution example:
% ./a.out
preorder:  + 1 * 2 3 
inorder:   1 + 2 * 3 
postorder: 1 2 3 * +

The following structure node is written in ex06-2-skel.c. 

struct node {
  struct node *right;
  char key;
  struct node *left;
};

right is the pointer pointing to right node. left is the pointer pointing to left node. key is the node content.

Question 3

Write a program which create a parse a tree from post-order formula. 

Program execution example:
% ./a.out
Input data by Reverse Polish Notation: 123*+
preorder:  + 1 * 2 3 
inorder:   1 + 2 * 3 
postorder: 1 2 3 * +
The program is based on the following two processes:
  1. For each input character, a node is created.
    1. If the character is a number, it is pushed to the stack.
    2. If the character is operator, two characters are popped from stack and the input character is pushed to stack. The first popped character is linked to the left of the operator, and the second one is linked to the right of the operator.

creating method of parse tree

Written by Naoki Wakamatsu.