Tree Traversals

• PreOrder
  visit a node, then traverse its left subtree, and then traverse its right subtree.

     void PreOrderTraversal( Tree_Node *ptr )
     {
       if (ptr !=0){
          cout << ptr->element << endl;
          PreOrderTraversal( ptr->left );
          PreOrderTraversal( ptr->right);
       }
     }
   
  

• PostOrder
  first traverse the left subtree, traverse the right subtree, and finally visit the node.

     void PostOrderTraversal( Tree_Node *ptr )
     {
       if (ptr !=0){
          PostOrderTraversal( ptr->left );
          PostOrderTraversal( ptr->right);
          cout << ptr->element << endl;
       }
     }
  

• InOrder
  traverse the left subtree, visit the node and then traverse its right subtree.

   void InOrderTraversal( Tree_Node *ptr )
     {
       if (ptr!=0){
          InOrderTraversal( ptr->left );
          cout << ptr->element << endl;
          InOrderTraversal( ptr->right);
       }
     }
  

• Level by level source code

  
  // level_by_level trversal of a binary tree
  // Mal Sutherland 1995
  
  #include <iostream.h>
  #include "queue.h"
  
  struct  treenode {
                      char data;
                      treenode *left;
                      treenode *right;
                   };
  
  typedef treenode* treeptr;         // variables of type treeptr contain
                                     // an address of a treenode.
  
  void build_tree (treeptr & root);
  
  
  void main ()
  {
  
     Queue<treeptr>  Q;             // A queue of pointers to treenodes
     treeptr         ptr;           // temporary pointer to a treenode
     treeptr         root = 0;      // Contains the address of the root node
  
     build_tree(root);              // Builds a binary tree
  
     ptr = root;                    // start traversal from the root node
  
     if ( ptr != 0 ){               // only do traversal if tree is not empty
  
          Q.enqueue(ptr);                   // put address of current node onto Q
          while ( !Q.isEmpty() )            // While there are nodes to visit
            {
              Q.dequeue( ptr );             //   current node = front from Q
              cout << ptr->data << endl;    //   visit node
  
              if ( ptr->left != 0 )         //   if current node has a left child
                 Q.enqueue(ptr->left);      //      put address of child onto Q
                                            //   end if
  
              if ( ptr->right != 0 )        //   if current node has a right child
                 Q.enqueue(ptr->right);     //      put address of child onto Q
                                            //   end if
  
            }                               // end while
      }
  } 
  
  

Binary Search Trees

• special case of the binary tree.
• the key data field of the left child (if it exists) is less than that of the parent.
• the key data field of the right child (if it exists) is greater than or equal to that of the parent.

                    M
                  /   \
                 D     P
               /      / \
              B      N   Z
            /  \      \
           A    C      O

An inorder traversal will visit each node of the tree by ascending order of the node data.

                 node *root = 0;   // empty tree

eg. non empty tree.

Using a binary search tree

• Inserting a new node into a binary search tree.

  
   void Insert( const Tree_Node* newptr, Tree_Node* &ptr)
    {
      if ( ptr==0 )
        ptr = newptr;                          // Attach new node
      else
        if ( newptr->element < ptr->element )
           Insert( newptr, ptr->left);
        else
           Insert( newptr, ptr->right);
     }
  
  
  

• Searching a binary search tree.

   Tree_node* Search( const Tree_Node* ptr, DataType key)
    {
      if ( ptr==0 )
        return 0;
      else
        if ( key == ptr->element )
            return ptr;
        else
            if ( key < ptr->element )
               return Search( ptr->left, key);
            else
               return Search( ptr->right, key);
     }
  
  

• Deleting from a binary search tree.