notes by Dave Mulkey, 2015, Germany

The contents of a tree can be printed in many different orders,

by moving around the tree according to a specifictraversalalgorithm.

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

Traversals are most easily programmed usingrecursive procedures.public voidTRAVERSE(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

Mathematical formulae are the most significant issue. The most useful,

standard storage for a formula is in a tree. For example:

TreeAlgebraic 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.

The following is an ARRAY IMPLEMENTATION of a tree. A 0 indicatesnull.

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.

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

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.

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.