Search

0.2.3.2 Source Code

The following double pointer implementation of a BST was written by Thomas Niemann and is available on his algorithm collection webpages.

#include 
 #include 
 
 /* modify these lines to establish data type */
 typedef int T;
 #define CompLT(a,b) (a < b)
 #define CompEQ(a,b) (a == b)
 
 typedef struct Node_ {
     struct Node_ *Left;         /* left child */
     struct Node_ *Right;        /* right child */
     struct Node_ *Parent;       /* parent */
     T Data;                     /* data stored in node */
 } Node;
 
 Node *Root = NULL;               /* root of binary tree */
 
 Node *InsertNode(T Data) {
     Node *X, *Current, *Parent;
 
 
    /***********************************************
     *  allocate node for Data and insert in tree  *
     ***********************************************/
 
     /* setup new node */
     if ((X = malloc (sizeof(*X))) == 0) {
         fprintf (stderr, "insufficient memory (InsertNode)\n");
         exit(1);
     }
     X->Data = Data;
     X->Left = NULL;
     X->Right = NULL;
 
     /* find X's parent */
     Current = Root;
     Parent = 0;
     while (Current) {
         if (CompEQ(X->Data, Current->Data)) return (Current);
         Parent = Current;
         Current = CompLT(X->Data, Current->Data) ?
             Current->Left : Current->Right;
     }
     X->Parent = Parent;
 
     /* insert X in tree */
     if(Parent)
         if(CompLT(X->Data, Parent->Data))
             Parent->Left = X;
         else
             Parent->Right = X;
     else
         Root = X;
 
     return(X);
 }
 void DeleteNode(Node *Z) {
     Node *X, *Y;
 
    /*****************************
     *  delete node Z from tree  *
     *****************************/
 
     /* Y will be removed from the parent chain */
     if (!Z || Z == NULL) return;
 
     /* find tree successor */
     if (Z->Left == NULL || Z->Right == NULL)
         Y = Z;
     else {
 
         Y = Z->Right;
         while (Y->Left != NULL) Y = Y->Left;
     }
 
     /* X is Y's only child */
     if (Y->Left != NULL)
         X = Y->Left;
     else
         X = Y->Right;
 
     /* remove Y from the parent chain */
     if (X) X->Parent = Y->Parent;
     if (Y->Parent)
         if (Y == Y->Parent->Left)
             Y->Parent->Left = X;
         else
             Y->Parent->Right = X;
     else
         Root = X;
 
     /* Y is the node we're removing */
     /* Z is the data we're removing */
     /* if Z and Y are not the same, replace Z with Y. */
     if (Y != Z) {
         Y->Left = Z->Left;
         if (Y->Left) Y->Left->Parent = Y;
         Y->Right = Z->Right;
         if (Y->Right) Y->Right->Parent = Y;
         Y->Parent = Z->Parent;
         if (Z->Parent)
             if (Z == Z->Parent->Left)
                 Z->Parent->Left = Y;
             else
                 Z->Parent->Right = Y;
         else
             Root = Y;
         free (Z);
     } else {
         free (Y);
     }
 }
 
 Node *FindNode(T Data) {
 
    /*******************************
     *  find node containing Data  *
     *******************************/
 
     Node *Current = Root;
     while(Current != NULL)
         if(CompEQ(Data, Current->Data))
             return (Current);
         else
             Current = CompLT (Data, Current->Data) ?
                 Current->Left : Current->Right;
     return(0);
 }