## Tree Traversals

`notes by Dave Mulkey, 2015, GermanyThe 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 repeatThe 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 middlepositions over and over again.  Once the tree is set up, the binary searchis very simple to program, and executes faster than a normal binarysearch, since there are no calculations to do.  The concept is alsoeasily extended to non-binary trees, which can improve search-times evenfurther. 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 canbe carried out.  A tree must also be sorted before a binary search can becarried 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 forthis data, but this one is the most efficient.  It guarantees thatevery 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 areshown 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.`