二叉查找树：对于树中的每个节点X，它的左子数种所有关键字值小于X的关键字，而它的右子树种所有关键字值大于X的关键字值。
/* 二叉查找树声明 */ #ifndef _TREE_H struct TreeNode;
typedef struct TreeNode *Position;
typedef struct 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);
ElementType Retrieve(Position P); #endif /* _TREE_H */
/* 建立一棵空树 */ SearchTree
MakeEmpty(SearchTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
/* 二叉查找树的Find操作 */ Position
Find(ElementType X, SearchTree T)
{
if(T == NULL)
return NULL;
if(X < T->Element)
return Find(X, T->Left);
else if(X > T->Element)
return Find(X, T->Right);
else
return T;
}
/* 对二叉查找树的FindMin的递归实现 */ Position
FindMin(SearchTree T)
{
if(T == NULL)
return NULL;
else if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
/* 对二叉查找树的FindMax的非递归实现 */ Position
FindMax(SearchTree T)
{
if(T != NULL)
while(T->Right != NULL)
T = T->Right; return T;
}
/* 插入元素到二叉树 */ SearchTree
Insert(ElementType X, SearchTree T)
{
if(T == NULL)
{
/* Create and return a one-node tree */
T = malloc(sizeof(struct TreeNode));
if(T == NULL)
FatalError("Out of space!\n");
else
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else if(X < T->Element)
T->Left = Insert(X, T->Left);
else if(X > T->Element)
T->Right = Insert(X, T->Right);
/* Else X is in the tree already; we'll do nothing */ return T; /* Do not forget this line!!! */
}
/* 二叉查找树的删除 */ SearchTree
Delete(ElementType X, SearchTree T)
{
Position TmpCell; if(T == NULL)
Error("Element not found!");
else if(X < T->Element) /* Go left */
T->Left = Delete(X, T->Left);
else if(X > T->Element)
T->Right = Delete(X, T->Right);
else if(T->Left && T->Right) /* Two children */
{
/* Replace with smallest in right subtree */
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}
else /* One or zero children */
{
TmpCell = T;
if(T->Left == NULL) /* Also handles 0 children */
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
} return T;
}