一、什么是二叉搜索树
二叉搜索树（Binary Search Tree，BST）也称 二叉排序树 或 二叉查找树。二叉搜索树 是一颗特殊的二叉树，它可以为空，如果不为空，满足以下性质：
- 非空 左子树 的所有 键值小于其根节点的键值
- 非空 右子树 的所有 键值大于其根节点的键值
- 左、右子树 都是 二叉搜索树
二、二叉搜索树操作的特别函数
Position Find(ElementType X,BinTree BST); // 从二叉搜索树BST中查找元素X，返回其所在的结点的地址
Positon FindMin(BinTree BST); // 从二叉搜索树BST中查找并返回最小元素所在结点的地址
Postion FindMax(BinTree BST); // 从二叉搜索树BST中查找并返回最大元素所在结点的地址
BinTree Insert(ElementType X,BinTree BST); // 在二叉搜索树BST中插入一个新的结点
BinTree Delete(ElementType X,BinTree BST); // 在二叉搜索树BST中删除一个结点
【1】、二叉搜索树的查找操作：Find
- 查找从根节点开始，如果 树为空，返回 NULL
- 若搜索树非空，则根据 关键字 和 X 进行比较，并进行不同处理：
- 若 X 小于根节点键值，只需在 左子树 中继续搜索；
- 若 X 大于根节点键值，只需在 右子树 中继续搜索
- 若两者笔比较结果是 相等，搜索完成，返回指向此结点的指针
Positon 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
{
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; // 查找失败
}
查找的效率决定于树的高度
【2】、最小元素 一定是在树的 最右分支的端结点 上。
// 查找最小元素的递归函数
Position FindMin(BinTree BST)
{
if(!BST) // 空的二叉搜索树，返回NULL
{
return NULL;
}
else if(!BST->Left)
{
return BST; // 找到最左叶节点并返回
}
else
{
return FinMin(BST->Left); // 沿做分支继续查找
}
}
【3】、查找最大元素
最大元素 一定是在树的 最右分支的端结点 上。
Position FindMax(BinTree BST)
{
if(BST)
{
while(BST->Right)
{
BST = BST->Right; // 沿右分支继续查找，直到最右叶结点
}
}
return BST;
}
【4】、二叉搜索树插入一个新的结点
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;
}
【5】、二叉搜索树的删除
删除要考虑三种情况：
- 要删除的是 叶节点：直接删除，并在修改其 父节点指针 置为 NULL
- 要删除的结点 只有一个孩子结点：将其 父节点的指针 指向 要删除结点的 孩子结点
- 要删除的结点有 左、右两颗子树：用另一个结点替代被删除结点：右子树的最小元素 或者 左子树的最大元素
BinTree Delete(ElementType X,BinTree BST)
{
Position Tmp;
if(!BST)
{
printf("要删除的元素未找到");
}
else if(X < BST->Data)
{
BST->Left = Delete(X,BST->Left); // 左子树递归删除
}
else if(X > BST->Data)
{
BST->Right = Delete(X,BST->Right); // 右子树递归删除
}
else // 找到要删除的结点
{
if(BST->Left && BST->Right) // 被删除结点有左右两个子节点
{
Tmp = FindMin(BST->Right); // 在右子树中找最小的元素填充删除结点
BST->Data = Tmp->Data;
BST->Right - Delete(BST->Data,BST->Right); // 在删除结点的右子中删除最小元素
}
else // 被删除结点有一个或无子节点
{
Tmp = BST;
if(!BST->Left) // 有右孩子或无子节点
{
BST = BST->Right;
}
else if(!BST->Right) // 有左孩子或无子节点
{
BST = BST->Left;
}
free(Tmp);
}
}
return BST;
}
三、判别是否是同一颗二叉搜索树
给定一个插入序列就可以唯一确定一颗二叉搜索树。然而，一颗给定的二叉搜索树却可以由多种不同的插入序列得到。那我们如何判断两个序列是否对应相同的二叉搜索树呢？
这里主要有三种方法：第一种方法是 根据两个序列分别建立两个二叉搜索树，再判别树是否一样；
第二种方法是 先比较第一个整数是否一样，如果一样，则说明对应的根节点一样，然后根据这个根节点，将后面的数分为两对，一对比根节点大，一对比过根节点小，然后用同样的方法依次处理这两对数。
第三种方法是建一棵树，再判别其它序列是否与该树一致。
3.1、搜索树表示
typedef struct TreeNode *Tree;
struct TreeNode
{
int v;
Tree Left,Right;
// flag=0，表示这个结点没被访问过
// flag=1，表示这个结点已经被访问过了
int flag;
};
3.2、读入数据建搜索树T
Tree MakeTree(int N)
{
Tree T;
int i,V;
printf("请输入树的元素：\n");
scanf("%d",&V);
T = NewNode(V);
for(i = 1; i < N; i++)
{
scanf("%d",&V);
T = Insert(T,V);
}
return T;
}
Tree NewNode(int V)
{
Tree T = (Tree)malloc(sizeof(struct TreeNode));
T->v = V;
T->Left = T->Right = NULL;
T->flag = 0;
return T;
}
Tree Insert(Tree T,int V)
{
if(!T) // 如果树为空，则创建根节点
{
T = NewNode(V);
}
else
{
if (V > T->v) // 如果要插入的数据大于当前结点的数据，则插入右子树
{
T->Right = Insert(T->Right,V);
}
else // 如果要插入的数据小于当前结点的数据，则插入左子树
{
T->Left = Insert(T->Left,V);
}
}
return T;
}
3.3、判别序列是否与T构成一样的搜索树
那我们如何判别序列是否与 T 一致呢？我们可以在树 T 中按顺序搜索序列中的每个数，如果每次搜索所经过的结点在前面均出现过，则一致，否则（某次搜索中遇到前面没有出现的结点），则不一致。
int Judge(Tree T,int N)
{
int i,V;
// flag=0，代表目前还一致
// flag=1，代表已经不一致
int flag = 0;
printf("请输入要比较的序列：\n");
scanf("%d",&V);
if(V != T->v)
{
flag = 1;
}
else
{
T->flag = 1;
}
for(i = 1; i < N; i++)
{
scanf("%d",&V);
if((!flag) && (!check(T,V)))
{
flag = 1;
}
}
if(flag)
{
return 0;
}
else
{
return 1;
}
}
int check(Tree T,int V)
{
if(T->flag) // 如果被访问过
{
if(V < T->v) // 到它的左子树找
{
return check(T->Left,V);
}
else if(V > T->v) // 到它的右子树找
{
return check(T->Right,V);
}
else // 整数出现两次以上
{
return 0;
}
}
else // 如果没被访问过
{
if(V == T->v) // 正好是该结点
{
T->flag = 1;
return 1;
}
else // 以前没见过的结点
{
return 0;
}
}
}
// 清除T中各节点的flag标记
void ResetT(Tree T)
{
if(T->Left)
{
ResetT(T->Left);
}
if(T->Right)
{
ResetT(T->Right);
}
T->flag = 0;
}
// 释放T的空间
void FreeTree(Tree T)
{
if(T->Left)
{
FreeTree(T->Left);
}
if(T->Right)
{
FreeTree(T->Right);
}
free(T);
}
3.4、测试程序
#include <stdio.h>
#include <stdlib.h>
int main()
{
int N,L,i;
Tree T;
printf("请输入序列中元素的个数：\n");
scanf("%d",&N);
T = MakeTree(N);
printf("请输入要比较的序列的个数：\n");
scanf("%d",&L);
for(i = 0; i < L; i++)
{
if(Judge(T,N)){
printf("Yes\n");
}
else
{
printf("No\n");
}
ResetT(T); // 清除T中的标志flag
}
FreeTree(T);
return 0;
}