正文
我所理解的二杈树022005-12-28 11:09:00
【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/8938.html
二杈排序树
所谓二杈排序树，指的是一棵空二杈树，或者是一棵具有如下特性的非空二杈树：
1。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
2。若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
3。左，右子树本身又各是一棵二杈排序树。
二杈排序树的基本操作包括二杈排序树的查找，生成（插入）和删除。
二杈排序树的查找：
在二杈排序树b中查找x的过程为：
1。若b是空树，则搜索失败，否则
2。若x等于b的根结点的数据域之值，则查找成功；否则
3。若x小于b的根结点的数据域之值，则搜索左子树；否则
4。搜索右子树
btree* search(btree *b, ElemType x)
{
if(b == NULL)
return NULL;
if(b->data == x)
return b;
if(b->data > x)
return search(b->lchild);
else
return search(b->rchild);
}
二杈排序树的生成（插入）
先讨论向一个二杈排序树b中插入一个结点s的算法：
1。若b是空树，则将s所指结点作为根结点插入，否则
2。若s->data等于b的根结点的数据域之值，则什么也不做，或者在结构中增添一个标记，表示该结点
数据出现的次数；否则
3。若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中；否则
4。把s所指结点插入到右子树中
void insert(btree **b, btree *s)
{
if(*b == NULL)
*b = s;
else if((*b)->data == s->data)//不做任何插入操作
;
else if((*b)->data > s->data)//把s所指结点插入到左子树中
insert(&((*b)->lchild), s);
else //把s所指结点插入到右子树中
insert(&((*b)->rchild), s);
}
生成二杈排序树的过程是先有一个空树b，然后向该空树插入一个个结点实现的，因此，
根据用户输入的一系列正整数（以-1为结束标志）生成一棵二杈排序树的函数如下：
void Creat(btree *b)
{
ElemType x;
btree *s;
b = NULL;
do
{
scanf("%d", &x);
s = (btree*)malloc(sizeof(btree));
if(s == NULL)
{
puts("wrong");
exit(1);
}
s->data = x;
s->lchild = s->rchild = NULL;
insert(&b, s); //插入一个结点s
} while(x != -1);
}
或者直接一个函数搞定：
btree* insert(btree *b, char x)
{
if(b == NULL)
{
b = (btree*)malloc(sizeof(btree));
if(b == NULL)
{
puts("wrong");
exit(1);
}
b->data = x; //putchar(x);
b->lchild = b->rchild = NULL;
}
else if(b->data == x)//不做任何插入操作
;
else if(b->data > x)//把s所指结点插入到左子树中
b->lchild = insert(b->lchild, x);
else //把s所指结点插入到右子树中
b->rchild = insert(b->rchild, x);
return b;
}
二杈排序树的删除：
删除二杈排序树b中一个数据域为x的结点的方法有两种。
第一种过程如下：
1。首先查找到数据域为x的结点p。
2。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子
作为r的父亲的右孩子。
3。若p没有左子树，直接用p的右孩子取代它。
第二种过程如下：
1。首先查找到数据域为x的结点p。
2。若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r
的右子树。
3。若p没有左子树，直接用p的右孩子取代它。
两种方法各有优劣，第二种操作简单一点点，但均衡性不如第一种，因为它将结点p的右子树
全部移到左边来了。下面将以第一种思路编写代码。
void delnode(btree *b, ElemType x)
{
btree *p, *prep, *r, *prer; //p和r指向待比较的结点，prep和prer分别指向它们的前驱结点
p = b;
prer = prep = NULL;
while(p != NULL && p->data != x)//查找数据域为x的结点p
{
if(x < p->data)
{
prep = p;
p = p->lchild;
}
else
{
prep = p;
p = p->rchild;
}
}
if(p == NULL)
printf("No find!\n");
else if(p->lchild != NULL) //被删结点有左子树
{
r = p->lchild; //r指向其左子树
while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
{
prer = r;
r = r->rchild;
}
if(prer != NULL)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子
prer->rchild = r->lchild;
r->rchild = p->rchild; //被删结点p的右子树作为r的右子树
if(prep == NULL) //若p为根结点，直接删除根结点
{
b = r;
free(p);
}
esle if(p == prep->lchild)//若p为prep的左孩子，把r作为prep的左孩子
{
prep->lchild = r;
free(p);
}
esle //若p为prep的右孩子，把r作为prep的右孩子
{
prep->rchild = r;
free(p);
}
}
else
{
if(prep == NULL)
{
b = p->rchild;
free(p);
}
esle if(p == prep->lchild)
{
prep->lchild = p->rchild;
free(p);
}
esle
{
prep->rchild = p->rchild;
free(p);
}
}
}
阅读(2980) | 评论(0)
版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！
评论