二叉搜索树（Binary Search Tree），又名二叉查找树、二叉排序树，是一种简单的二叉树。它的特点是每一个结点的左（右）子树各结点的元素一定小于（大于）该结点的元素。将该树用于查找时，由于二叉树的性质，查找操作的时间复杂度可以由线性降低到O(logN)。
当然，这一复杂度只是描述了平均的情况，事实上，具体到每一棵二叉搜索树，查找操作的复杂度与树本身的结构有关。如果二叉树的结点全部偏向一个方向，那么与线性查找将毫无区别。这就牵扯到二叉树的平衡问题，暂时不做考虑。
下面给出二叉搜索树的实现。其中，个别可以递归实现的函数，笔者采用了循环的方式。由于递归方法通常较为简洁易懂，在此便不再补充给出。
// BinarySearchTree.h #include <stdio.h>
#include <stdlib.h> struct _TreeNode;
typedef struct _TreeNode TreeNode;
typedef TreeNode *Position;
typedef TreeNode *SearchTree; SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
// BinarySearchTree.c #include "BinarySearchTree.h" struct _TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
int Count;
}; SearchTree MakeEmpty(SearchTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
} Position Find(ElementType X, SearchTree T)
{
while (T != NULL)
{
if (T->Element < X)
T = T->Right;
else if (T->Element > X)
T = T->Left;
else
return T;
}
printf("Not found! \n");
return NULL;
} // I write FindMin and FindMax in two different forms. The latter is more clean while the former is more understandable.
Position FindMin(SearchTree T)
{
if (T == NULL)
return NULL;
while (T->Left != NULL)
{
T = T->Left;
}
return T;
} Position FindMax(SearchTree T)
{
if (T != NULL)
while (T->Right != NULL)
T = T->Right;
return T;
} Position CreateNode(ElementType X)
{
Position p;
p = (Position)malloc(sizeof(TreeNode));
if (p == NULL)
{
printf("Error! Out of memory! \n");
return NULL;
}
p->Left = p->Right = NULL;
p->Element = X;
p->Count = 1;
return p;
} // I do this without recursion, so the code is a bit long.
SearchTree Insert(ElementType X, SearchTree T)
{
Position t = CreateNode(X);
Position p = T;
if (T == NULL)
return t;
while (1)
{
if (p->Element < X)
{
if (p->Right != NULL)
p = p->Right;
else
{
p->Right = t;
return T;
}
}
else if (p->Element > X)
{
if (p->Left != NULL)
p = p->Left;
else
{
p->Left = t;
return T;
}
}
else
{
p->Count++;
return T;
}
}
} SearchTree Delete(ElementType X, SearchTree T)
{
Position temp;
int t;
if(T == NULL)
{
printf("Error! The tree is empty! \n");
return NULL;
}
if(T->Element < X)
T->Right = Delete(X, T->Right);
else if(T->Element > X)
T->Left = Delete(X, T->Left);
else
{
if(T->Count > 1)
T->Count--;
else
{
if(T->Left && T->Right)
{
temp = FindMin(T);
t = FindMin(T->Right)->Element;
T->Count = temp->Count;
temp->Count = 1;
Delete(t, T);
T->Element = t;
return T;
}
else if(T->Left)
{
temp = T->Left;
free(T);
return temp;
}
else if(T->Right)
{
temp = T->Right;
free(T);
return temp;
}
else
{
free(T);
return NULL;
}
}
}
} ElementType Retrieve(Position P)
{
return P->Element;
}
至于ADT正确性的测试，可以通过插入、删除结点后设置断点，观察各结点的左右子树元素值，从而与实际插入、删除的情况进行分析比较，判断其是否一致。
如果使用的编程环境进行此操作不甚方便，也可以通过二叉树的前/中/后序遍历序列来对照。