qq_40737185 2020-04-09 13:14 采纳率: 0%
浏览 156

求助!二叉树删除算法实现不了?

求助!写二叉排序树的时候写了个删除节点算法,运行到后面总是崩溃,我是试验叶子节点能否删除,请大佬帮忙指正下错误

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

typedef int KeyType;
typedef struct BSNode{
    KeyType key;
    struct BSNode *lchild, *rchild;
}BSNode, *BiTree;

//54,20,66,40,28,79,52
int BST_Insert(BiTree &T, KeyType k)
{
    //如果树空,创建树根 
    if(NULL == T)
    {
        T = (BiTree)malloc(sizeof(BSNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    //如果插入的元素在树中已有,则不插入 
    else if(k == T->key)
    {
        return 0;
     } 
     //若左子树非空,则左子树上的值均小于根节点的值 
     else if(k<T->key)
     {
        return BST_Insert(T->lchild, k);
      } 
      //若右子树非空,则右子树上的值均大于根节点的值 
      else
      {
        return BST_Insert(T->rchild, k);
      }
}

//创建二叉排序树 
void Creat_BST(BiTree &T, KeyType str[], int n)
{
    int i = 0; 
    T = NULL;
    while(i<n)
    {
        //将数组中的元素依次插入 
        BST_Insert(T, str[i]);
        i++;
    }
}

//递归实现,但时间复杂度大,效率低 
BSNode *BST_Search(BiTree &T, KeyType key)
{
    if(T == NULL) return NULL;
    if(key < T->key)
    {
        return BST_Search(T->lchild, key);
    }
    else if(key > T->key)
    {
        return BST_Search(T->rchild, key);
    }
    else if(T->key = key)
    {
        return T;
    }
}

//用循环实现查找
BSNode * BST_Search(BiTree T, KeyType key, BiTree &p)
{
    p = NULL;
    while(T!=NULL && T->key!=key)
    {
        p = T;
        if(key < T->key) T = T->lchild;
        else T = T->rchild;

    }
    return T;
}

bool DeleteNode(BiTree &T, KeyType key)
{
    if(T!=NULL)
    {
        //如果查找的值比根节点小,就查找左子树,如果比根节点大,就查找右子树 
        if(key < T->key) DeleteNode(T->lchild, key);
        else if(key > T->key) DeleteNode(T->rchild, key);
        //如果相等,若左右节点为空,直接释放节点资源(删除节点) 
        else
        {
            if(T->lchild == NULL && T->rchild == NULL)
            {
                free(T);
                T == NULL;
                return true;
            }   
    }
    }
    return false;
}

void InOrder(BiTree &T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        printf("%4d", T->key);
        InOrder(T->rchild);
    }
}
int main()
{
    BiTree T;
    //用来存储父亲的地址值 
    BiTree parent;
    BiTree search;
    KeyType str[] = {10,5,15,6,4,16}; //将要进入二叉树的元素值 
    Creat_BST(T, str, 6); //左子节点比parent小,右子节点比parent大 
    //printf("aaa\n");
    InOrder(T);
    printf("\n");
    //递归查找 
//  search = BST_Search(T, 20);
    //if(search) printf("%d\n", search->key);
    //else printf("未查找到\n");        
    //循环查找 
    //search = BST_Serach(T, 41, search);
    if(DeleteNode(T, 4))
    {
        printf("删除成功\n");
    }
    else
    {
        printf("失败!\n");
    }
    InOrder(T);
    printf("\n"); 

    system("pause");
    return 0;
 } 
  • 写回答

1条回答 默认 最新

  • 有梦袭来 2020-04-09 14:14
    关注

    bool DeleteNode(BiTree &T, KeyType key)
    {
    if(T!=NULL)
    {
    if(key < T->key) DeleteNode(T->lchild, key);
    else if(key > T->key) DeleteNode(T->rchild, key);
    else
    {
    if(T->lchild == NULL && T->rchild == NULL)
    {
    free(T);
    T == NULL; // == 换成= ,应该是粗心导致
    return true;
    }

    }
    }
    return false;
    }

    评论

报告相同问题?

悬赏问题

  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名