论坛 › 数据结构与算法 › 二叉排序树删除元素问题

博伊314 发表于 2015-12-1 23:07:58

二叉排序树删除元素问题

这个程序在删除元素后再进行中序遍历发生问题，求大神帮忙解释问题原因！

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

#define TRUE1
#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;
}
{

y290176346 发表于 2015-12-1 23:07:59

本帖最后由 y290176346 于 2015-12-3 11:00 编辑

找到原因了 你在删除函数里 把需要结构点的删除了，直接free掉了，但是 你没有把根的指针 赋值。也就是 父亲和孩子的联系断掉了，根节点还是指在free的节点，所以就报错了，你是自己找找怎么改 修修炼下自己 还是我帮你改代码
你这15个鱼币太少了

shield 发表于 2015-12-3 19:06:31

15个玉璧太少，多少算多？

博伊314 发表于 2015-12-3 20:25:37

在网上查了半天资料，这个问题我已经弄懂了

博伊314 发表于 2015-12-3 20:30:30

y290176346 发表于 2015-12-1 23:07
找到原因了 你在删除函数里 把需要结构点的删除了，直接free掉了，但是 你没有把根的指针 赋值。也就是 父 ...

不用给我代码了，已经弄懂了，多谢了

y290176346 发表于 2015-12-4 07:56:01

本帖最后由 y290176346 于 2015-12-4 11:18 编辑

shield 发表于 2015-12-3 19:06
15个玉璧太少，多少算多？

怎么的也的16个吧 我看了你的代码足足2个小时

1748504919 发表于 2015-12-5 14:49:55

双指针

莫欺少年穷 发表于 2015-12-23 20:25:02

Code_mzh 发表于 2018-3-29 19:37:28

博伊314 发表于 2015-12-3 20:30
不用给我代码了，已经弄懂了，多谢了

能说一下是怎么改的吗？

查看完整版本: 二叉排序树删除元素问题