平衡二叉树的删除（我不是来求代码的）

kingteng 2009-11-18 11:36:30

我写了这么一段，里面那个两个子节点的情况我没有写完整，没有用左子树的最大节点或者右子树的最小值来取代要删除的节点，我现在要问的是为什么连叶子节点都删除不了呢？

void delte(binarytree **tree,Type data){

    binarytree *p,*parent;

    if(*tree == NULL)

        printf("empty tree,illegal to delte\n");

    if((p = search(*tree,parent,data)) != NULL){

        if(p->leftch == NULL && p->rightch == NULL){//叶子节点

            if(p->data < parent->data)//左叶子节点

                parent->leftch = NULL;

            else//右叶子节点

                parent->rightch = NULL;

            p = NULL;



            printf("11111\n");

        }

        else if(p->leftch == NULL || p->rightch == NULL){//有一个子节点的节点

            binarytree *temp = (p->leftch==NULL)?p->rightch:p->leftch;

            printf("22222\n");

            if(p->data > parent->data)//且该节点是父节点的右子节点

                parent->rightch = temp;

            else

                parent->leftch = temp;//且该节点是父节点的左子节点

            p = NULL;

        }

        else{//有两个子节点

            printf("33333\n");

            p->rightch->leftch = p->leftch;

            p->rightch->rightch = NULL;

            parent->leftch = p->rightch;

            p = NULL;

        }



    }

    else

        printf("no data matched\n");//没有该值的节点





}

...全文

216 12 打赏收藏转发到动态举报

写回复

用AI写文章

12 条回复

切换为时间正序

请发表友善的回复…

发表回复

jiayucunyan 2009-11-20

打赏
举报

[Quote=引用 9 楼 kingteng 的回复:]
我在删除函数里没有malloc，为什么要free呢。。。。还有，照你那个该法好像还是不对呀，不过p和parent的关系确实应该是那样的引用 8 楼 jiayucunyan 的回复:
删除节点p，要free（p），再p=NULL

[/Quote]

你建树的时候，malloc了

jiayucunyan 2009-11-19

打赏
举报

[Quote=引用 4 楼 kingteng 的回复:]
还是没有看出来，大家帮个忙啊，我把search也贴出来吧
binarytree *search(binarytree *tree,binarytree *parent,Type data){
binarytree *p = (binarytree *)malloc(sizeof(struct binarytree)*1); //这句好像有问题，内存泄露。你定义了一个p，并为它分配了空间，下面又用p指向了tree，那么刚才分配的空间就没有指针指向它了。
p = tree;
bool find = false;
while(p && !find){
parent = p;
if(p->data == data){
find = true;
//printf("find %d\n",p->data);
}
else if(p->data > data)
p = p->leftch;
else
p = p->rightch;
}
return find?p:NULL;//这句直接返回p，就可以了，找不到p就是NULL
}
[/Quote]

再看看删除函数

kingteng 2009-11-19

打赏
举报

还是没有看出来，大家帮个忙啊，我把search也贴出来吧
binarytree *search(binarytree *tree,binarytree *parent,Type data){
binarytree *p = (binarytree *)malloc(sizeof(struct binarytree)*1);
p = tree;
bool find = false;
while(p && !find){
parent = p;
if(p->data == data){
find = true;
//printf("find %d\n",p->data);
}
else if(p->data > data)
p = p->leftch;
else
p = p->rightch;
}
return find?p:NULL;
}

kingteng 2009-11-19

打赏
举报

parent在search赋值了

logiciel 2009-11-19

打赏
举报

parent没有被赋过值.

很土 2009-11-19

打赏
举报

关于平衡二叉树可以参考:
http://blog.csdn.net/kyee/archive/2009/10/22/4711654.aspx
http://blog.csdn.net/kyee/archive/2009/10/20/4704329.aspx

kingteng 2009-11-19

打赏
举报

谢谢各位了

kingteng 2009-11-19

打赏
举报

谢谢，对了~~[Quote=引用 7 楼 logiciel 的回复:]
LZ的search函数不能返回parent,要把parent的类型改为:

binarytree *search(binarytree *tree,binarytree **parent,Type data)

*parent = p;

调用改为:

if((p = search(*tree,&parent,data)) != NULL){

[/Quote]

kingteng 2009-11-19

打赏
举报

我在删除函数里没有malloc，为什么要free呢。。。。还有，照你那个该法好像还是不对呀，不过p和parent的关系确实应该是那样的[Quote=引用 8 楼 jiayucunyan 的回复:]
删除节点p，要free（p），再p=NULL
[/Quote]

jiayucunyan 2009-11-19

打赏
举报

删除节点p，要free（p），再p=NULL

logiciel 2009-11-19

打赏
举报

LZ的search函数不能返回parent,要把parent的类型改为:

binarytree *search(binarytree *tree,binarytree **parent,Type data)

*parent = p;

调用改为:

if((p = search(*tree,&parent,data)) != NULL){

jiayucunyan 2009-11-19

打赏
举报

[Quote=引用 4 楼 kingteng 的回复:]
还是没有看出来，大家帮个忙啊，我把search也贴出来吧
binarytree *search(binarytree *tree,binarytree *parent,Type data){
binarytree *p = (binarytree *)malloc(sizeof(struct binarytree)*1);
//改为binarytree *p = NULL;
p = tree;
bool find = false;
parent = p;
while(p && !find){
if(p->data == data){
find = true;
break;
//printf("find %d\n",p->data);
}

parent = p;

else if(p->data > data)
p = p->leftch;
else
p = p->rightch;
}
return p;
}
[/Quote]

你原来的代码，返回的p和parent指向的是一个节点

另外，删除的时候应该判断一下是否为树根