Tree Traversals
The contents of a tree can be printed in many different orders,
by moving around the tree according to a specific traversal algorithm.
Three standard methods are called PREORDER, INORDER, and POSTORDER.
The diagram below illustrates the results of each method:
----- P ----
/ \
/ \
F S
/ \ / \
/ \ / \
B H R Y
/ / \
/ / \
G T Z
\
\
W
Pre-order : P F B H G S R Y T W Z
In Order : B F G H P R S T W Y Z
Post-order: B G H F R W T Z Y S P
( Useless : P F S B N R Y G T Z W )
The names describe whether a parent is printed BEFORE its children,
BETWEEN its children, or AFTER its children.
Pre-order : Parent processed BEFORE the children
Parent, then left-child, then right-child
In-order : Parent processed BETWEEN the children
Left-child, then parent, then right-child
Post-order: Parent processed AFTER the children
Left-child, then right-child, then parent
Useless : Ignore this one - it has no value at all
Recursive Algorithms
Traversals are most easily programmed using recursive procedures.
public void TRAVERSE(Node here)
{
if (here.leftchild != null)
{ TRAVERSE(here.leftchild); }
if (temp.rightchild != null)
{ TRAVERSE(here.rightchild); }
output(here.data);
}
(1) Which type of traversal is represented in the TRAVERSE method ?
(2) Change the method to do the other two types of traversals.
(3) Input the example tree above into your tree program, and test the
results of your three traversal algorithms.
Tree traversals are particularly useful for:
storing, printing, and evaluating mathematical formulae
storing and searching a dictionary for a spelling check
storing and processing computer programs in symbolic form
storing and processing any other hierarchical, recursive structures
Math Formulae
Mathematical formulae are the most significant issue. The most useful,
standard storage for a formula is in a tree. For example:
Tree Algebraic Form: 3*x+4/(5-x)
(+)
/ \ RPN form: 3 x * 4 5 x - / +
/ \
/ \ Programming Form:
(*) (/) Add( Mul(3,x), Div(4, Sub(5,x) ) )
/ \ / \
/ \ / \
(3) (x) (4) (-)
/ \
/ \
(5) (x)
If the tree is printed using an INORDER traversal, the result is
the Algebraic formula (fully bracketed): (3*x) + ( 4/ (5-x) )
If the tree is printed by a POSTORDER traversal, the result is the RPN
expression.
If the tree is printed using a PREORDER traversal, the result is the
Programming command style expression.
For this reason, normal algebraic notation is called INFIX notation.
RPN notation is called POSTFIX notation. And Pascal is called PREFIX notation.
-----------------------------------------------------------------------------
(4) Draw a tree for the expression: 1*2-3/4+5
(5) Show the POSTORDER TRAVERSAL of your tree from #4.
Storing in Arrays
The following is an ARRAY IMPLEMENTATION of a tree. A 0 indicates null.
Root = 4
Position Contents Left Right
1 a 0 0
2 + 1 3
3 d 0 0
4 * 2 9
5 b 0 0
6 e 0 0
7 c 0 0
8 / 6 7
9 - 4 8
(6) Write the INORDER and PREORDER traversals of this tree.
Binary Search Tree
There are two commonly used methods for SEARCHING an array:
(1) Sequential - start at position 1 and search in order
(2) Binary - start in the middle, check whether the target
value comes before or after the middle, then
go to the middle of that half, and repeat
The binary search requires the list to be SORTED. If the list is sorted,
the binary method is much faster than the sequential method.
On the average, in a list of length N, the sequential method requires N steps,
whereas the binary method requires LOG N steps ( Log base 2).
A further refinement of the binary search is a BINARY SEARCH TREE .
This is a tree which is already arranged so that the binary search is
carried out by following the branches, rather than calculating the middle
positions over and over again. Once the tree is set up, the binary search
is very simple to program, and executes faster than a normal binary
search, since there are no calculations to do. The concept is also
easily extended to non-binary trees, which can improve search-times even
further.
List Tree
========= ====== ------- Freddy ------
1 Adam / \
2 Annie / \
3 Barney Carl Mildred
4 Carl / \ / \
5 Chuck / \ / \
6 Debbie Annie Debbie Herman Terry
7 Ed / \ / \ / \ / \
8 Freddy / \ / \ / \ / \
9 George Adam Barney Chuck Ed George Irene Piroski Zelda
10 Herman
11 Irene
12 Mildred
13 Piroski
14 Terry
15 Zelda
Binary Search Tree Rules
Keep in mind that a list must be sorted before a binary search can
be carried out. A tree must also be sorted before a binary search can be
carried out. The tree must satisfy the following rule:
Binary Search Tree Rules:
For every parent node, all members of the left sub-tree
are less than the parent, and all members of the
right sub-tree are greater than the parent.
The example tree above is in the proper format for a binary search tree.
Since all branches reach down to the same level, it is a FULL, BALANCED tree.
There are many other possible arrangements for a binary search tree for
this data, but this one is the most efficient. It guarantees that
every search can be completed in 4 steps, which is LOG2 (16) .
On the next page are some more trees for the same data - the names are
shown in abbreviated form.
Binary Search Tree Practice
For each tree, decide whether it is a proper binary search tree -
that is, does it obey the rule stated above ?
(1) (2)
--- Fr --- Ad
/ \ \
Ca M An
/ \ / \ \
An De He Te Ba
\ / \ / \ \
Ba Ch Ed Ge Ze Ca
/ \ / \
Ad Ir Pi He
/ \
Ed Pi
/ \ / \
De Ge Ir Te
/ / \ \
Ch Fr Mi Ze
(3) Make the best balanced tree possible, starting with Herman at the root.
(4) To the following tree, add the nodes A , J , X , Q
------- P ------
/ \
/ \
F S
/ \ / \
/ \ / \
B H R Y
/ / \
/ / \
G T Z
\
\
W
(5) Draw a BALANCED BINARY SEARCH TREE for the data in #4, including
the new nodes.