(1) Which nodes of the figure correspond to the following names?
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
.
The following formulas are result of traversing the tree.
preorder: +1*23 inorder: 1+2*3 postorder: 123*+
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.
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 * +