Related Blog Items

• Printing Binary Trees in Ascii
• Balanced (AVL) Binary Search Trees
• Binary decimal conversion....
• Binary to decimal
• Data structures lectures

A binary tree is a tree in which no node can have more than two children. The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in its left subtree are smaller than the key value in X, and the values of all the keys in its right subtree are larger than the key value in X.

An important application of binary trees is their use in searching.

Here are the operations which are possible on binary search tree ADT (abstract data type),

1)Make Empty
2)Find
3)FindMin
4)FindMax
5)Insert
6)Delete

All operations except MakeEmpty above takes O(log N) time on average case.

Our algorithms used tail recursion, as the average depth of a binary search tree is O(log N),
the amount of stack space used is expected to be only O(log N).

Binary search is represented list of nodes, each node may have left and right nodes,
here is the single tree node represenation

struct Tree 
{
  Tree * left, * right;
  int element;
};

1. Make Empty

This operation is for mainly intialization and can be used to destroy entire search tree also.

Tree *make_empty(Tree *t)
{
  if (t != NULL)
  {
    make_empty(t->left);
    make_empty(t->right);
    free(t);
  }
 
  return NULL;
}

2. Find

This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
element stored in the tree node

3b212968e7bddb0d2972b7a65ab33ea5002

3. FindMin

This operation returns the smallest element node in the tree, i.e. left most element of the tree

Tree *find_min(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->left == NULL)
  {
    return t;
  }
  else
  {
    return find_min(t->left);
  }
}

4. FindMax

This operation returns the biggest element node in the tree, i.e. right most element of the tree

Tree *find_max(Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }
  else if (t->right == NULL)
  {
    return t;
  }
  else
  {
    return find_max(t->right);
  }
}

5. Insert

This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
insert the element at the last spot on the path traversed.

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
 
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
      return t;
    }
 
    new_node->element = value;
 
    new_node->left = new_node->right = NULL;
    return new_node;
  }
 
  if (value < t->element) 
  {
    t->left = insert(value, t->left);
  } 
  else if (value > t->element) 
  {
    t->right = insert(value, t->right);
  } 
  else 
  { 
    //duplicate, ignore it
    return t;
  }
  return t;
}

6. Delete

This is the complicated operation among other tree operations. If the node to be deleted is a leaf, it can be deleted immediately. If the node has one child, the node can deleted after its parents adjusts a pointer to bypass the node. While deleting a node which has two children, the general strategy is to replace the data of this node with the smallest data of the right subtree and recursively delete that node.

Tree * delete(int value, Tree * t) 
{
  //Deletes node from the tree
  // Return a pointer to the resulting tree
  Tree * x;
  Tree *tmp_cell;
 
  if (t==NULL) return NULL;
 
  if (value < t->element) 
  {
    t->left = delete(value, t->left);
  } 
  else if (value > t->element) 
  {
    t->right = delete(value, t->right);
  } 
  else if (t->left && t->right)
  {
    tmp_cell = find_min(t->right);
    t->element = tmp_cell->element;
    t->right = delete(t->element, t->right);
  }
  else
  { 
    tmp_cell = t;
    if (t->left == NULL)
      t = t->right;
    else if (t->right == NULL)
      t = t->left;
    free(tmp_cell);
  }
 
  return t;
}

Here are the operations examples..

Download the Binary Search Tree Source Code [note: I’ve used some what old compiler(msvc6.0), if you are using a new compiler you may get some compilation errors, fix them yourself otherwise drop a message over here]

Popularity: 29%

You need to log on to convert this article into PDF

Related Blog Items

• Printing Binary Trees in Ascii
• Balanced (AVL) Binary Search Trees
• Binary decimal conversion....
• Binary to decimal
• Data structures lectures

This entry was written by ponnada and posted on December 21, 2007 at 7:28 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.