二叉搜索树也称二叉排序树或二叉查找树；

二叉搜索树：一颗二叉树可以为空；如果不为空，满足以下性质：

1.非空左子树的所有键值小于其根结点的键值。

2.非空右子树的所有键值大于其根节点的键值。

3.左、右子树都是二叉搜索树。

 

查找：Find

1.若X小于根节点键值，只需在左子树中继续搜索

2.若X大于根节点键值，只需在右子树中继续搜索

3.若两者比较结果是相等，返回指向此结点的指针

尾递归

Position Find (ElementType X, BinTree BST) {

　　if (!BST)　　return NULL;　　//查找失败

　　if (X > BST->Data)　　

　　　　return Find (X, BST->Right);　　//在右子树中继续查找

　　else if (X < BST->Data)

　　　　return Find (X, BST->Left);　　//在左子树中继续查找

　　else //X==BST->Data

　　　　return BST;　　//查找成功，返回结点的地址
}

 

 

迭代函数

Position IterFind (ElementType X, BinTree BST){

　　while (BST) {

　　　　if (X > BST->Data)

　　　　　　BST = BST->Right;　　//向右子树中移动，继续查找

　　　　else if (X < BST->Data)

　　　　　　BST = BST->Left;　　//向左子树中移动，继续查找

　　　　else

　　　　　　return BST;

　　}

　　return NULL;　　//查找失败

}

查找的效率取决于树的高度

 

查找最大和最小元素

最大元素一定是在树的最右分枝的端结点上，最小元素一定是在树的最左分枝的端结点上

1.查找最小元素的递归函数

Position FindMin (BinTree BST) {

　　if (!BST) 　　return NULL;　　//空的二叉搜索树，返回NULL

　　else if (!BST->Left)

　　　　return BST;　　//找到最左叶结点并返回

　　else

　　　　return FindMin (BST->Left)　　//沿左分枝继续查找

}

 

2.查找最大元素的迭代函数

Position FindMax (BinTree BST) {

　　if (BST) {

　　　　while (BST->Right) {

　　　　　　BST = BST->Right;　　

　　　　　　//沿右分枝继续查找，直到最右叶结点

　　　　}

　　}

　　return BST；

}

 

插入

BinTree Insert (ElementType X, BinTree BST) {

　　if (!BST) {

　　　　//若原树为空，生成并返回一个结点的二叉搜索树

　　　　BST = malloc (sizeof(struct TreeNode));

　　　　BST->Data = X;

　　　　BST->Left = BST->Right = NULL;

　　}

　　else {　　//寻找插入元素的位置

　　　　if (X < BST->Data) {

　　　　　　BST->Left = Insert (X, BST->Left);　　//递归插入左子树

　　　　else if (X > BST->Data {

　　　　　　BST->Right = Insert(X, BST->Right);

　　}

　　return BST;

}