For each tree shown in Figure
show the order in which the nodes are visited during
the following tree traversals:
preorder traversal,
inorder traversal (if defined),
postorder traversal, and
breadth-first traversal.
Figure: Sample trees for Exercise
Write a visitor that prints the nodes of a general tree
in the format of Equation .
Derive an expression for the total space needed to
represent a tree of n internal nodes
using each of the following classes:
GeneralTree defined in Program ,
NaryTree defined in Program , and
BinaryTree defined in Program .
A full node in a binary tree is a node with two non-empty subtrees.
Let l be the number of leaf nodes in a binary tree.
Show that the number of full nodes is l-1.
The generic DepthFirstTraversal routine defined in
Program is a recursive function.
Write a non-recursive depth-first traversal routine
that has exactly the same effect as the recursive version.
Program defines a visitor that prints
using infix notation
the expression represented by an expression tree.
Write a visitor that prints the same expression
in prefix notation with the following format:
Repeat Exercise ,
but this time write a visitor that the expression
in postfix notation with the following format:
The InfixVisitor defined in Program
prints many redundant parentheses because it does
not take into consideration the precedence of the operators.
Rewrite the visitor so that it prints
rather than
Consider postfix expressions involving only binary operators.
Show that if such an expression contains n symbols,
it always has (n-1)/2 operators and (n+1)/2 operands.
Prove Theorem .
Generalize Theorem so that it applies to N-ary trees.
Consider two binary trees,
and and
the relation given by
If ,
the trees are said to be isomorphic.
Devise an algorithm to test whether two binary trees are isomorphic.
What is the running time of your algorithm?