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