Trees - General & Binary

General trees

• the root node of a tree has no parent.
• each node has a single parent.
• a leaf node has no children.

A leaf node is the root node of an empty tree.

Binary Trees

Each node can have two children at most.

Implementation:
Use dynamic memory allocation to create and destroy nodes when required.

Eg. struct node { DataType data;
                  node     *right;
                  node     *left;
                };

                 node *root = 0;   // empty tree

eg. non empty tree.

Tree Traversals

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

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

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

• Level by level

Expression trees

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.

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

• Inserting a new node into a binary search tree.
• Searching a binary search tree.

Tree Traversals

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

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

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

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

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

   void InOrderTraversal( treenode *ptr )
     {
       if (ptr!=0){
          InOrderTraversal( ptr->left );
          cout << ptr->data << 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