Search
Next: 0.2.3.3 References Up: 0.2.3 Binary Search Trees Previous: 0.2.3.1 Inserting and Deleting

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);
}
```

Scott Gasch
1999-07-09