二叉排序树基本操作详解
二叉排序树基本操作详解巧若拙（欢迎转载，但请注明出处：http://blog.）
所谓二叉排序树，指的是一棵空二叉树，或者是一棵具有如下特性的非空二叉树：
1。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
2。若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
3。左，右子树本身又各是一棵二叉排序树。
二叉排序树的基本操作包括二叉排序树的输出，查找，生成（插入）和删除。
一：二叉排序树的输出：
关于二叉排序树的输出，我总结了以下几种方式：按递增次序（即中序遍历）输出结点，按递减次序输出结点，按层序输出结点，按凹入表表示输出结点和按嵌套括号表示输出结点。代码如下：
程序代码：
/*
函数名称：InOrderPrint
函数功能：按递增次序（即中序遍历）输出结点
输入变量：BiTree p：指向二叉树结点p的指针
输出变量；无
*/
void InOrderPrint(BiTree p)
{
if (p != NULL)
{
InOrderPrint(p->lchild); //遍历左子树
printf("%c ", p->data);//输出该结点
InOrderPrint(p->rchild); //遍历右子树
}
}
/*
/*
函数名称：DestOrderPrint
函数功能：按递减次序遍历输出结点
先遍历右子树，再输出结点，然后遍历左子树
输入变量：BiTree p：二叉树（或子树）根结点p
输出变量；无
*/
void DestOrderPrint(BiTree p)
{
if (p != NULL)
{
DestOrderPrint(p->rchild); //遍历右子树
printf("%c ", p->data);//输出该结点
DestOrderPrint(p->lchild); //遍历左子树
}
}
/*
函数名称：LevelOrderPrint
函数功能：层序遍历输出结点。
使用一个队列，先将二叉树根结点入列。队头结点退列并输出，若它有左孩子，将左孩子入列；若它有右孩子，将右孩子入列。如此直到队列空为止。
输入变量：BiTree BT：二叉树BT的头指针
输出变量；无
*/
void LevelOrderPrint(BiTree BT)
{
BiTree p, queue[MAXSIZE];
int front = 0, rear = 0;
if (BT != NULL)
{
queue[rear++] = BT;
while (front < rear)
{
p = queue[front++]; //队头结点退列并输出
printf("%c ", p->data);//输出该结点
if (p->lchild != NULL)
{
queue[rear++] = p->lchild;
}
if (p->rchild != NULL)
{
queue[rear++] = p->rchild;
}
}
}
}
函数名称：DisplayBiTree
函数功能：给定一个二叉树，输出其嵌套括号表示。
首先输出根结点，然后再依次输出它的左子树和右子树，不过在输出左子树之前要打印左括号，在输出右子树之前后要打印右括号；另外，依次输出左，右子树要至少有一个不为空，若都为空则不输出。
输入变量：BiTree BT：二叉树BT的头指针
输出变量；无
*/
void DisplayBiTree(BiTree BT)
{
if (BT != NULL)
{
printf("%c", BT->data);
if (BT->lchild != NULL || BT->rchild != NULL)
{
printf("(");
DisplayBiTree(BT->lchild);
if (BT->rchild != NULL)
{
printf(",");
}
DisplayBiTree(BT->rchild);
printf(")");
}
}
}
/*
函数名称：DisplayBiTree
函数功能：给定一个二叉树，输出其凹入表表示法。
采用先序遍历的非递归函数，除了使用一个栈外，还增加一个场宽数组level[]，儿子结点的场宽设置为width，即每下一层缩进width。
输入变量：BiTree BT：二叉树BT的头指针
输出变量；无
*/
void DisplayIndent(BiTree BT)
{
BiTree p, stack[MAXSIZE];
int level[MAXSIZE] = {0};
int i, n, top = -1;
const int width = 3;
if (BT != NULL)//先判断是否为空树
{
stack[++top] = BT; //根结点入栈
while (top >= 0)
{
p = stack[top]; //栈顶元素出栈并凹入显示该结点值
n = level[top--];
for (i=0; i<n; i++)
printf(" ");
printf("%c\n", p->data);//输出该结点
if (p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
{
stack[++top] = p->rchild;
level[top] = n + width;
}
if (p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
{
stack[++top] = p->lchild;
level[top] = n + width;
}
}
}
}
二：二叉排序树的查找：
普通的二叉树查找需要先查找某棵子树，找不到再到另一颗子树中查找，时间复杂度为O(N)，而二叉排序树由于是有序的，故可以采用二分查找的方法。比较代码如下：
在普通二叉树b中查找x的过程为：
1。若b是空树，则搜索失败，否则
2。若x等于b的根结点的数据域之值，则查找成功；否则
3。搜索左子树，若查找成功，返回对应结点；否则
4。搜索右子树
程序代码：
/*
函数名称：LocateElment_2
函数功能：在普通二叉树中寻找值为x的结点
输入变量：BiTree b：二叉树（或子树）根结点b，
ElemType x：数据x
输出变量；值为x的结点，若找不到则返回NULL
*/
BiTree LocateElment_2 (BiTree b, ElemType x)
{
BiTree p;
if (b == NULL || b->data == x)
return b;
else
{
p = LocateElment_2(b->lchild, x); //到左子树中寻找
if (p != NULL)
return p;
else
return LocateElment(b->rchild, x); //到右子树中寻找
}
}
在二叉排序树b中查找x的过程为：
1。若b是空树，则搜索失败，否则
2。若x等于b的根结点的数据域之值，则查找成功；否则
3。若x小于b的根结点的数据域之值，则搜索左子树；否则
4。搜索右子树
程序代码：
/*
函数名称：LocateElment
函数功能：在二叉排序树中寻找值为x的结点
输入变量：BiTree b：二叉树（或子树）根结点b，
ElemType x：数据x
输出变量；值为x的结点，若找不到则返回NULL
*/
BiTree LocateElment(BiTree b, ElemType x)
{
if (b == NULL || b->data == x)
return b;
else if (b->data > x) //到左子树中寻找
return LocateElment(b->lchild, x);
else //到右子树中寻找
return LocateElment(b->rchild, x);
}
这里补充一个有趣的应用：输出值为x的结点的路径。算法是先在二叉树中找到值为x的结点p，然后采用非递归后序遍历二叉树的方法，当后序遍历访问到结点s时，此时栈中的元素均为s所指结点的祖先，依次输出栈中元素即得到路径。代码如下：
程序代码：
/*
函数名称：PathPrint
函数功能：输出值为x的结点的路径
输入变量：BiTree BT：二叉树根结点BT，
ElemType x：数据x
输出变量；无
*/
void PathPrint(BiTree BT, ElemType x)
{
BiTree s = LocateElment_2(BT, x);
if (s != NULL)
Path(BT, s);
else
printf("\n%c不存在\n", x);
}
/*
函数名称：Path
函数功能：输出从根结点BT到结点s的路径
采用非递归后序遍历二叉树，当后序遍历访问到结点s时，此时栈中的元素均为s所指结点的祖先，依次输出栈中元素即得到路径。
输入变量：BiTree BT：二叉树根结点BT，
BiTree s：二叉树的某个结点s
输出变量；无
*/
void Path(BiTree BT, BiTree s)
{
BiTree p, stack[MAXSIZE];//p表示当前结点，栈stack[]用来存储结点
int tag[MAXSIZE] = {0}; //用来标志栈顶元素的右孩子是否被访问过，0表示未访问，1表示已访问
int i, top = -1; //栈空
if (BT != NULL)//先判断是否为空树
{
p = BT;
while (p || top >= 0)
{
if (p != NULL) //不急着输出结点数据，先访问左孩子
{
stack[++top] = p;
tag[top] = 0; //表明该结点的右子树尚未访问
p = p->lchild;
}
else
{
p = stack[top]; //取栈顶元素，但先不出栈
if (p->data == s->data) //找到结点p，输出其路径
{
for (i=0; i<top; i++)
{
printf("%c->", stack[i]->data);
}
printf("%c\n", p->data);
return;
}
if (tag[top] == 0) //若右子树尚未访问，访问其右孩子
{
tag[top] = 1; //表明该结点的右子树已接受访问
p = p->rchild;
}
else
{
top--; //退栈，并让p指向NULL，以避免重复访问左孩子
p = NULL;
}
}
}
}
}
三：二叉排序树的生成（插入）
向二叉排序树b中插入一个结点s的算法：
1。若b是空树，则将s所指结点作为根结点插入，否则
2。若s->data等于b的根结点的数据域之值，则什么也不做，或者在结构中增添一个标记，表示该结点数据出现的次数；否则
3。若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中；否则
4。把s所指结点插入到右子树中
生成二杈排序树的过程是先有一个空树b，然后向该空树插入一个个结点实现的，因此，
生成一棵二叉排序树（输入单个字符，以#结束）函数如下：
程序代码：
/*
函数名称：CreateBiTree
函数功能：生成一棵二叉排序树（输入单个字符，以#结束）
输入变量：BiTree *bt：指向二叉树根结点bt的指针
输出变量；无
*/
void CreateBiTree(BiTree *bt)
{
BiTree s;
ElemType x;
scanf("%c", &x);
while (x != '#')
{
s = NewBiTree(x);//构造一个数据域为x的新结点
Insert(bt, s);//在二叉排序树中插入新结点s
scanf("%c", &x);
}
}
/*
函数名称：NewBiTree
函数功能：构造一个数据域为x的新结点
输入变量：ElemType x：数据x
输出变量；新结点s
*/
BiTree NewBiTree(ElemType x)
{
BiTree s = (BiTree)malloc(sizeof(BiTreeNode));
if (!s)
{
printf("Out of space!");
exit (1);
}
s->data = x;
s->lchild = s->rchild = NULL;
return s;
}
/*
函数名称：Insert
函数功能：在二叉排序树中插入新结点s
输入变量：BiTree *b：指向二叉树根结点b的指针
BiTree s：新结点s
输出变量；无
*/
void Insert(BiTree *b, BiTree s)
{
if (*b == NULL)
*b = s;
else if ((*b)->data == s->data)//不做任何插入操作
return;
else if((*b)->data > s->data)//把s所指结点插入到左子树中
Insert(&(*b)->lchild, s);
else //把s所指结点插入到右子树中
Insert(&(*b)->rchild, s);
}
四：二叉排序树的删除：
对于一般的二叉树来说，删去树中的一个结点是没有意义的，因为它将使以被删除的结点为根的子树变成森林，破坏了整棵树的结构。但是，对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点后不改变二叉排序树的特性即可。
程序代码：
/*
函数名称：DeleteBST
函数功能：删除二叉排序树中值为x的结点
输入变量：BiTree b：指向二叉树根结点b的指针
ElemType x：数据x
输出变量；新的根结点
*/
BiTree DeleteBST(BiTree b, ElemType x)
{
if (b)
{
if (b->data == x)
b = DelNode_1(b);
else if (b->data > x)
b->lchild = DeleteBST(b->lchild, x);
else
b->rchild = DeleteBST(b->rchild, x);
}
return b;
}
在二叉排序树上删除一个结点的算法有两种方法。
第一种过程如下：
1。若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r的右子树。
2。若p没有左子树，直接用p的右孩子取代它。
第二种过程如下：
1。若p有左子树，找到其左子树的最右边的叶子结点r。若p的左孩子有右子树，即r的双亲不是p，则把r的左子树作为r双亲的右子树，把p的左子树作为r的左子树；否则直接把p的左子树作为r的左子树。把p的右子树作为r的右子树。
2。若p没有左子树，直接用p的右孩子取代它。
两种方法各有优劣，第一种操作简单一点，但均衡性不如第二种，因为它将结点p的右子树全部移到左边来了。下面将分别以两种种思路编写代码。
程序代码：
/*
函数名称：DelNode_1
函数功能：删除二叉树的结点p
输入变量：BiTree p：指向二叉树结点p的指针
输出变量；新的根结点
*/
BiTree DelNode_1(BiTree p)//删除结点*p
{
BiTree r;
if (p->lchild) //若p有左子树，用p的左孩子取代它
{
r = p->lchild; //寻找左子树的最右结点
while (r->rchild)
{
r = r->rchild;
}
r->rchild = p->rchild; //被删结点p的右子树作为r的右子树
r = p->lchild;
}
else //p没有左孩子，则直接返回其右子树
{
r = p->rchild;
}
free(p);
return r;
}
/*
函数名称：DelNode_2
函数功能：删除二叉树的结点p
输入变量：BiTree p：指向二叉树结点p的指针
输出变量；新的根结点
*/
BiTree DelNode_2(BiTree p)
{
BiTree q, r;
if (p->lchild)
{
q = p;
r = q->lchild;
while (r->rchild) //寻找左子树的最右结点
{
q = r;
r = r->rchild;
}
if (p != q)//r的双亲不是p，则把r的左子树作为r双亲的右子树，r的左孩子指向p的左孩子
{
q->rchild = r->lchild;
r->lchild = p->lchild;
}
r->rchild = p->rchild; //被删结点p的右子树作为r的右子树
}
else //p没有左孩子，则直接返回其右子树
{
r = p->rchild;
}
free(p);
return r;
}
认真阅读函数DelNode_2，我们发现函数最终返回了新的根结点r，需要修改r的左右孩子指针，很容易出错，其实在这里我们删除的只是p的元素值，而不是它的地址，所以完全没有必要修改指针。
仔细观察，发现我们删除的地址实际上是p的左子树的最右边的叶子结点r的地址，所以我们只要把r的数据填到p中，然后把r删除即可。代码如下：
程序代码：
/*
函数名称：DelNode_3
函数功能：删除二叉树的结点p
输入变量：BiTree p：指向二叉树结点p的指针
输出变量；新的根结点
*/
BiTree DelNode_3(BiTree p)
{
BiTree q, r;
if (p->lchild)
{
q = p;
r = q->lchild;
while (r->rchild) //寻找左子树的最右结点
{
q = r;
r = r->rchild;
}
p->data = r->data; //把结点r的数据赋值给p，这样就可以直接删除结点r了。
if (p != q)//p的左孩子有右子树
{
q->rchild = r->lchild;
}
else
{
q->lchild = r->lchild;
}
free(r);
return p;
}
else //p没有左孩子，则直接返回其右子树
{
r = p->rchild;
free(p);
return r;
}
}
二叉排序树性能分析
每个结点的度为该结点的层次数。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和logn成正比（O(log2(n))）。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树为一棵斜树，树的深度为n，其平均查找长度为(n + 1) / 2。也就是时间复杂度为O(n)，等同于顺序查找。因此，如果希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树（平衡二叉树）。
