注册 登录
编程论坛 数据结构与算法

二叉排序树删除节点的操作

wobuzhidao0 发布于 2012-05-07 13:56, 724 次点击
void Delete(Bitree &p)
{//从二叉排序树中删除节点p,并重接它的左或右子树
    if(!p->rchild)//右子树空则只需重接它的左或右字数
    {
        q=p;p=p->lchild;
        free(q);
    }
    else if(!p->lchild)//只需重接它的右子树
    {
        q=p;
        p=p->rchild;
        free(q);
    }
    else//左右字数均不空
    {
        q=p;
        s=p->lchild;
        while(s->rchild)
        {//转左,然后向右到尽头
            q=s;
            s=s->rchild
        }
        p->data=s->data; //s指向被删除节点的前驱
        if(q!=p) q->rchild=s->lchile; //重接*q的柚子树
        else q->lchild=s->lchild;//重接*q的左子树
    }

}
上面红体字部分是什么意思,看不懂
4 回复
#2
silent_world2012-05-07 20:00
这是平衡二叉树的删除节点操作。
如果一个中间节点被删除,那么,需要有一个替代节点,其值最接近这个中间节点。
因此,这个节点为左子树中的最大节点或右子树中的最小节点。
左子树中的最大节点为左子树中右子树的终点;
右子树中的最小节点为右子树中左子树的终点。
在获取替代节点后,如果替代节点的左子树或右子树不为空,需要链接其子树至其父节点。

整个算法基本上就是这样。
#3
wobuzhidao02012-05-07 21:21
以下是引用silent_world在2012-5-7 20:00:43的发言:

这是平衡二叉树的删除节点操作。
如果一个中间节点被删除,那么,需要有一个替代节点,其值最接近这个中间节点。
因此,这个节点为左子树中的最大节点或右子树中的最小节点。
左子树中的最大节点为左子树中右子树的终点;
右子树中的最小节点为右子树中左子树的终点。
在获取替代节点后,如果替代节点的左子树或右子树不为空,需要链接其子树至其父节点。

整个算法基本上就是这样。
那个if(!q=p)是说删除点的左子树没有右子树吗,为什么这样表达
#4
寒风中的细雨2012-05-07 21:41
在纸上画图自己分析下  比较好理解
#5
wobuzhidao02012-05-07 21:55
刚刚弄明白了,谢谢你们
1