| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 809 人关注过本帖, 2 人收藏
标题:二叉排序树基本操作详解
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  问题点数:0  回复次数:1   
二叉排序树基本操作详解
二叉排序树基本操作详解
巧若拙(欢迎转载,但请注明出处:http://blog./qiaoruozhuo)

所谓二叉排序树,指的是一棵空二叉树,或者是一棵具有如下特性的非空二叉树:
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),等同于顺序查找。因此,如果希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树(平衡二叉树)。
搜索更多相关主题的帖子: 二叉树 
2014-10-04 17:58
超级无敌阳光
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2016-4-18
  得分:0 
好好好!!!
2016-04-20 21:25







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037688 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved