鱼C论坛

 找回密码
 立即注册
查看: 5293|回复: 8

二叉排序树删除元素问题

[复制链接]
发表于 2015-12-1 23:07:58 | 显示全部楼层 |阅读模式
15鱼币
这个程序在删除元素后再进行中序遍历发生问题,求大神帮忙解释问题原因!

#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0

typedef int Status;
typedef struct BiNode
{
        int data;
        struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
        if( !T )               
        {
                *p = f;              
                return FALSE;
        }
        else if( key == T->data )
        {
                *p = T;
                return TRUE;
        }
        else if( key < T->data )
        {
                return SearchBST(T->lchild,key,T,p);
        }
        else
        {
                return SearchBST(T->rchild,key,T,p);
        }
}

void InsertBST(BiTree *T,int key)
{
        BiTree p,s;
        if( !SearchBST(*T,key,NULL,&p) )
        {
                s = (BiNode *)malloc(sizeof(BiNode));
                s->data = key;
                s->rchild = s->lchild = NULL;

                if( !p )
                {
                        *T = s;
                }
                else if( key > p->data )
                {
                        p->rchild = s;
                }
                else
                {
                        p->lchild = s;
                }
        }
        else
        {
                printf("插入的元素 % d已存在!\n",key);
        }
}

void DeleteBST(BiTree *T,int key)
{
        BiTree p,s,q;
        if( !SearchBST(*T,key,NULL,&p) )
        {
                printf("你所删除的元素不存在!\n");
        }
        else if( p->rchild == NULL )
        {
                q = p;
                p = p->lchild;
                free(q);
        }
        else if( p->lchild == NULL )
        {
                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;
        
        if( q != p )
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        
        free(s);
    }
}

//中序遍历二叉树
void InOrder(BiTree T)
{
        if( T )
        {
                InOrder(T->lchild);
                printf("%d ",T->data);
                InOrder(T->rchild);
        }
}

int main()
{
        int key,i,n;
        BiTree T = NULL;

        printf("请输入插入元素的个数:");
        scanf("%d",&n);
        printf("请输入插入元素的值:");
        for( i = 0;i < n;i++ )
        {
                scanf("%d",&key);
                InsertBST(&T,key);
        }

        printf("中序遍历的结果:\n");
        InOrder(T);

        printf("\n请输入你所删除的元素:");
        scanf("%d",&key);
        DeleteBST(&T,key);

        printf("中序遍历的结果:\n");
        InOrder(T);

        printf("\n");

        return 0;
}
{

最佳答案

查看完整内容

找到原因了 你在删除函数里 把需要结构点的删除了,直接free掉了,但是 你没有把根的指针 赋值。也就是 父亲和孩子的联系断掉了,根节点还是指在free的节点,所以就报错了,你是自己找找怎么改 修修炼下自己 还是我帮你改代码 你这15个鱼币太少了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-12-1 23:07:59 | 显示全部楼层
本帖最后由 y290176346 于 2015-12-3 11:00 编辑

找到原因了 你在删除函数里 把需要结构点的删除了,直接free掉了,但是 你没有把根的指针 赋值。也就是 父亲和孩子的联系断掉了,根节点还是指在free的节点,所以就报错了,你是自己找找怎么改 修修炼下自己 还是我帮你改代码
你这15个鱼币太少了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-12-3 19:06:31 | 显示全部楼层
15个玉璧太少,多少算多?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-12-3 20:25:37 | 显示全部楼层
在网上查了半天资料,这个问题我已经弄懂了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-12-3 20:30:30 | 显示全部楼层
y290176346 发表于 2015-12-1 23:07
找到原因了 你在删除函数里 把需要结构点的删除了,直接free掉了,但是 你没有把根的指针 赋值。也就是 父 ...

不用给我代码了,已经弄懂了,多谢了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-12-4 07:56:01 | 显示全部楼层
本帖最后由 y290176346 于 2015-12-4 11:18 编辑
shield 发表于 2015-12-3 19:06
15个玉璧太少,多少算多?


怎么的也的16个吧 我看了你的代码足足2个小时
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-12-5 14:49:55 From FishC Mobile | 显示全部楼层
双指针
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2015-12-23 20:25:02 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-29 19:37:28 | 显示全部楼层
博伊314 发表于 2015-12-3 20:30
不用给我代码了,已经弄懂了,多谢了

能说一下是怎么改的吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 20:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表