(C语言)在二叉搜索树的学习时遇到了问题,求大佬帮忙看看

如题,在学习二叉搜索树时想要自己添加一些内容,但是不知道为什么就是会出错,自己感觉好像问题出在创建二叉树的地方,但是不知道怎么改.希望大佬能帮忙看看,如果能配上讲解就更好了,感谢.

下面贴上代码,之后是罗列的一些问题,如果代码中还有问题希望大佬能指点下我,谢谢:

项目总共三个文件,二叉搜索树头文件.h和.c文件,然后一个用于测试的主函数.c

(二叉搜索树头文件)
BSTree.h

#ifndef BSTREE_H
#define BSTREE_H

typedef int DataType;
//二叉排序树节点定义
struct BinSearchTreeNode
{
    DataType data;
    struct BinSearchTreeNode *leftchild;
    struct BinSearchTreeNode *rightchild;
};
typedef struct BinSearchTreeNode *BSTreeNode;
typedef struct BinSearchTreeNode *BinSearchTree;

/****************************************************************/
/* BinSearchTree *create()                                      */
/* 功能:创建二叉排序树                                         */
/* 输入参数:无                                                 */
/* 返回值:二叉排序树                                            */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
BinSearchTree create();

/****************************************************************/
/* void InOrder(BinSearchTree ptree)                            */
/* 功能:中序遍历二叉排序树                                       */
/* 输入参数ptree:二叉排序树                                        */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void InOrder(BinSearchTree ptree);

/****************************************************************/
/* BSTreeNode BSTSearch(BinSearchTree bt, DataType key)         */
/* 功能:检索二叉排序树                                         */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要检索的元素                                       */
/* 返回值:成功返回NULL,失败返回元素插入的父结点位置                */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
BSTreeNode BSTSearch(BinSearchTree bt, DataType key);

/****************************************************************/
/* int BSTInsert(BinSearchTree bt, DataType key)                */
/* 功能:在二叉排序树中插入元素key                              */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要插入的元素                                       */
/* 返回值:成功插入返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTInsert(BinSearchTree bt, DataType key);

/****************************************************************/
/* int BSTgetMax(BinSearchTree *bt)                             */
/* 功能:查找二叉排序树的最大值                                 */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BSTgetMax(BinSearchTree *bt);

/****************************************************************/
/* int BSTgetMin(BinSearchTree *bt)                             */
/* 功能:查找二叉排序树的最小值                                 */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BSTgetMin(BinSearchTree *bt);

/****************************************************************/
/* int BSTDelete1(BinSearchTree *bt, DataType key)              */
/* 功能:删除二叉排序树中的元素key,方法1                          */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要删除的元素                                       */
/* 返回值:成功删除返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTDelete1(BinSearchTree *bt, DataType key);

/****************************************************************/
/* int BSTDelete2(BinSearchTree *bt, DataType key)              */
/* 功能:删除二叉排序树中的元素key,方法2                          */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要删除的元素                                       */
/* 返回值:成功删除返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTDelete2(BinSearchTree *bt, DataType key);

/****************************************************************/
/* void BST_Destory(BinSearchTree bt)                           */
/* 功能:销毁二叉排序树                                         */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BST_Destory(BinSearchTree bt);

#endif  // BSTREE_H

对应的c文件
BSTree.c


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

/****************************************************************/
/* BinSearchTree create()                                       */
/* 功能:创建二叉排序树,注意这里输入的应该是先序序列,并且保证是一*/
/*      个二叉排序树的先序序列                                   */
/* 输入参数:无                                                 */
/* 返回值:二叉排序树                                            */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
BinSearchTree create()
{
    int ch = 0;//初始化
    BinSearchTree bt;
    scanf_s("%d", &ch);
    if (ch == -1)
    {
        bt = NULL;
    }
    else
    {
        bt = (BSTreeNode *)malloc(sizeof(struct BinSearchTreeNode));
        bt->data = ch;
        //递归赋值左子树
        bt->leftchild = create();
        //递归赋值右子树
        bt->rightchild = create();
    }
    //返回根节点
    return bt;
}

/****************************************************************/
/* void InOrder(BinSearchTree ptree)                            */
/* 功能:中序遍历二叉排序树                                       */
/* 输入参数ptree:二叉排序树                                        */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void InOrder(BinSearchTree ptree)
{
    if (ptree == NULL)
    {
        return;
    }
    InOrder(ptree->leftchild);
    printf("%d", ptree->data);
    InOrder(ptree->rightchild);
}

/****************************************************************/
/* BSTreeNode BSTSearch(BinSearchTree bt, DataType key)         */
/* 功能:检索二叉排序树                                         */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要检索的元素                                       */
/* 返回值:成功返回NULL,失败返回元素插入的父结点位置                */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
BSTreeNode BSTSearch(BinSearchTree bt, DataType key)
{
    BSTreeNode p, parent;
    p = bt;
    parent = p; //记录待插入结点的父结点
    while (p)
    {
        parent = p;
        //当查找到时提示,返回NULL
        if (p->data == key)
        {
            printf("Exist this key\n");
            return NULL;
        }
        //根结点大于要查的结点,进入左分支查找
        if (p->data > key)
        {
            p = p->leftchild;
        }
        //根结点小于要查的结点,进入右分支查找
        else
        {
            p = p->rightchild;
        }
    }//p=NULL,跳出循环
    return parent;  //查找失败,返回parent
}//return NULL和parent是为了便于之后的操作

/****************************************************************/
/* int BSTInsert(BinSearchTree bt, DataType key)                */
/* 功能:在二叉排序树中插入元素key                              */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要插入的元素                                       */
/* 返回值:成功插入返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTInsert(BinSearchTree bt, DataType key)
{
    BSTreeNode p, temp;
    temp = BSTSearch(bt, key);   //temp保存查找之后的结果
    //已存在,返回0
    if (temp == NULL)
    {
        printf("Exist this key\n");
        return 0;
    }
    //申请结点的内存空间
    p = (BSTreeNode *)malloc(sizeof(struct BinSearchTreeNode));
    //申请失败提示
    if (p == NULL)
    {
        printf("Alloc Failure!\n");
        return 0;
    }
    p->data = key;  //数据域赋值,左右指针域默认为空
    //p->leftchild = NULL;  //左子树指针域赋值
    //p->rightchild = NULL; //右子树指针域赋值
    if (key < temp->data)
    {
        temp->leftchild = p;    //作为左子树插入
    }
    else
    {
        temp->rightchild = p;   //作为右子树插入
    }
    return 1;
}

/****************************************************************/
/* int BSTgetMax(BinSearchTree bt)                              */
/* 功能:查找二叉排序树的最大值                                 */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BSTgetMax(BinSearchTree *bt)
{
    BSTreeNode temp;
    temp = bt;
    if (temp)
    {
        while (temp->leftchild)
        {
            temp = temp->leftchild;
        }
        printf("%d", temp->data);
    }
}

/****************************************************************/
/* int BSTgetMin(BinSearchTree bt)                              */
/* 功能:查找二叉排序树的最小值                                 */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BSTgetMin(BinSearchTree *bt)
{
    BSTreeNode temp;
    temp = bt;
    if (temp)
    {
        while (temp->rightchild)
        {
            temp = temp->rightchild;
        }
        printf("%d", temp->data);
    }
}

/****************************************************************/
/* int BSTDelete1(BinSearchTree *bt, DataType key)              */
/* 功能:删除二叉排序树中的元素key,方法1                          */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要删除的元素                                       */
/* 返回值:成功删除返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTDelete1(BinSearchTree *bt, DataType key)
{
    BSTreeNode parent, p, maxpl;
    p = *bt;
    parent = NULL;
    //查找被删除的结点
    while (p != NULL)
    {
        if (p->data == key)
            break;  //查找到了,跳出循环
        if (p->data > key)
            p = p->leftchild;
        else
            p = p->rightchild;
    }//查询结束
    if (p == NULL)
    {
        printf("%d not exist\n", key);
        return 0;
    }
    //只有右子树的情况
    if (p->leftchild == NULL)
    {
        //如果被删除的结点是根结点,那就要修改的是二叉排序树的根
        if (parent == NULL)
            *bt = p->rightchild;
        //检查是左孩子还是右孩子
        else if (parent->leftchild == p)
            parent->leftchild = p->rightchild;
        else
            parent->rightchild = p->rightchild;
    }
    //既有左子树也有右子树
    if (p->leftchild != NULL)
    {
        BSTreeNode parentp; //parentp记录maxpl的父结点
        parentp = p;
        maxpl = p->leftchild;
        //对称遍历中,右侧的总是大的数
        //定位p的左子树中的最大结点maxpl
        while (maxpl->rightchild != NULL)
        {
            parentp = maxpl;
            maxpl = maxpl->rightchild;
        }
        p->data = maxpl->data;  //修改p的数据域为maxpl的值
        if (parentp == p)    //如果maxpl的父结点是p
            p->leftchild = maxpl->leftchild;    //修改p结点的左指针
        else
            parentp->rightchild = maxpl->leftchild; //修改父结点的右指针
        p = maxpl;  //更新p指针为maxpl结点以便删除
    }
    //释放空间
    free(p);
    return 1;
}

/****************************************************************/
/* int BSTDelete2(BinSearchTree *bt, DataType key)              */
/* 功能:删除二叉排序树中的元素key,方法2                          */
/* 输入参数bt:二叉排序树的根                                 */
/* 输入参数key:要删除的元素                                       */
/* 返回值:成功删除返回1,否则返回0                              */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
int BSTDelete2(BinSearchTree *bt, DataType key)
{
    //parent记录p的父结点,maxpl记录p的左子树中的关键码最大结点
    BSTreeNode parent, p, maxpl;
    p = *bt;
    parent = NULL;
    //查找被删除的结点
    while (p != NULL)
    {
        if (p->data == key)
            break;  //查找到了,跳出循环
        parent = p; //注意这一句
        if (p->data > key)
            p = p->leftchild;
        else
            p = p->rightchild;
    }//查找结束
    if (p == NULL)
    {
        printf("%d not exist!\n", key);
        return 0;
    }
    //只有右子树的情况
    if (p->leftchild == NULL)
    {
        //删除的是根结点,做特殊处理
        if (parent == NULL)
            *bt = p->rightchild;
        //p是父结点parent的左孩子,则修改父结点的左指针
        else if (parent->leftchild == p)
            parent->leftchild = p->rightchild;
        else
            parent->rightchild = p->rightchild;
    }
    //以上和方法1几乎完全相同

    //有左子树和右子树
    if (p->leftchild != NULL)
    {
        maxpl = p->leftchild;
        //定位左子树中的最大结点maxpl
        while (maxpl->rightchild != NULL)
            maxpl = maxpl->rightchild;
        maxpl->rightchild = p->rightchild;
        if (parent == NULL)
            *bt = p->leftchild;
        //p是父结点parent的左孩子,则修改父结点的左指针
        else if (parent->leftchild == p)
            parent->leftchild = p->leftchild;
        //p是父结点parent的右孩子,则修改父结点的右指针
        else
            parent->rightchild = p->leftchild;
    }
    free(p);    //释放结点p
    return 1;
}

/****************************************************************/
/* void BST_Destory(BinSearchTree *bt)                          */
/* 功能:递归销毁二叉排序树                                       */
/* 输入参数bt:二叉排序树的根                                 */
/* 返回值:无                                                    */
/* 创建日期:2019-5-21                       Author:Cyber Kaka   */
/****************************************************************/
void BST_Destory(BinSearchTree bt)
{
    if (bt)
    {
        BST_Destory(bt->leftchild);
        BST_Destory(bt->rightchild);
        free(bt);
    }
}

主函数.c文件

main.c

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


//用于测试的二叉树先序序列,-1表示空
//40 10 5 -1 -1 -1 55 45 -1 48 47 -1 -1 52 -1 -1 60 -1 70 -1 -1
void main()
{
    BinSearchTree bt;
    int n = 0;
    printf("输入二叉排序树的先序序列:\n");
    bt = create();
    printf("输入要查找的元素,存在返回1,不存在返回0,插入:");
    scanf_s("%d", &n);
    printf("%d\n", BSTSearch(bt, n)->data);
    printf("输入要插入的元素,成功插入返回1,否则返回0:");
    scanf_s("%d", &n);
    printf("%d\n", BSTInsert(bt, n));
    //printf("二叉排序树的中序遍历序列:\n");
    //InOrder(bt);
    printf("\n第一种删除方法,输入要删除的元素,成功返回1,不成功返回0:");
    scanf_s("%d", &n);
    printf("%d\n", BSTDelete1(&bt, n));
    //printf("二叉排序树的中序遍历序列:\n");
    //InOrder(bt);
    printf("\n第二种删除方法,输入要删除的元素,成功返回1,不成功返回0:");
    scanf_s("%d", &n);
    printf("%d\n", BSTDelete2(&bt, n));
    //printf("二叉排序树的中序遍历序列:\n");
    //InOrder(bt);

}

问题:


  • [0]生成解决方案的时候有警告,但是我忽略了,因为显示程序生成成功了,感觉这几个警告是最大的问题,第4个问题中我详细列出了这些内容

  • [1]二叉树的递归创建自己感觉有问题,尤其是内存申请这里

    bt = (BSTreeNode *)malloc(sizeof(struct BinSearchTreeNode));

  • [2]中序遍历的内容在搜索到左子树底的时候本应返回上一步时会出现异常,建立断点异常内容如下:
    引发了异常: 读取访问权限冲突。
    ptree 是 0xCDCDCDCD。

  • [3]由于中序遍历有异常,所以我注释掉了所有的相关内容,编译时没什么问题,但是删除结点的函数也会出现类似的异常,异常内容如下:
    引发了异常: 读取访问权限冲突。
    maxpl 是 0xCDCDCDCD。


  • [4]好吧,我就都注释掉了,看看别的代码是不是有问题,重新生成解决方案,熟悉的警告出现了,c语言是速成的结构体这块不是很明了,感觉应该是创建二叉搜索树的代码有问题,或者是结构体创建有问题,以下是警告的内容:
    */bstree.c(24): warning C4047: “=”:“BinSearchTree”与“BSTreeNode *”的间接级别不同
    */bstree.c(108): warning C4047: “=”:“BSTreeNode”与“BSTreeNode *”的间接级别不同
    *\bstree.c(139): warning C4047: “=”:“BSTreeNode”与“BinSearchTree *”的间接级别不同
    *\bstree.c(160): warning C4047: “=”:“BSTreeNode”与“BinSearchTree *”的间接级别不同

    第24行:
    BinSearchTree create()
    {
      ...
        bt = (BSTreeNode *)malloc(sizeof(struct BinSearchTreeNode));
      ...
    }

    第108行:
    int BSTInsert(BinSearchTree bt, DataType key)
    {
      ...
        //申请结点的内存空间
        p = (BSTreeNode *)malloc(sizeof(struct BinSearchTreeNode));
      ...
    }

    第139行:
    void BSTgetMax(BinSearchTree *bt)
    {
      ...
        temp = bt;
      ...
    }

    第160行:
    void BSTgetMin(BinSearchTree *bt)
    {
      ...
        temp = bt;
      ...
    }

    以上,求各位大佬指点迷津

2个回答

  1. 警告的问题不大,就是同一个类型两个别名而已。

  2. 你代码的主要问题就在,你每次在malloc内存结点的时候,没有给该结点的左右子结点指针赋空,导致野指针的访问异常。
    (VC的debug下会把未初始化的堆内存上的指针全部填成 0xCDCDCDCD,所以看到 0xCDCDCDCD的时候你就该知道存在未初始化的分配空间了。)

解决方法,在每次你malloc结点内存的地方,给左右子结点指针赋NULL即可。

qq_24258127
Cyber丶Kaka 感谢大佬
6 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

1
ball ball各位大佬,C语言中序表达式树求值问题
1
跪求大佬,请问怎么用代码实现求二叉排序树的平均检索长度,或者用什么思路实现
1
C++语言编程 二叉搜索树 查找
0
并查集生成迷宫广度优先搜索最短路径时出现了问题 求大佬解答QAQ很急 拜托了!!!
1
[C++数据结构]自己按书中代码打了一个二叉查找树模板类,发现不能在树上正常插入元素
0
一个有关多叉树的问题的采用了C语言的方式怎么实现多叉树
0
C++ 二叉搜索树 根节点的值运行过程中改变了 代码很短
1
给出一个n叉树,一个叶子节点值,不用递归,怎样求这个叶子节点的路径?
0
二叉搜索树在数据结构方面的综合运用,如何利用C语言编程解决这个算法?
0
多叉树的快速搜索算法的优化,这个问题如何利用C语言的办法解决
0
二叉平衡树的高效率的求法的问题,运用C语言系统的编程的技术
1
大佬们帮忙看看这个二叉搜索树哪错了
1
还是被二叉搜索树难住了,结果出不来,求教各位大佬到底哪错了
1
[Python] 尾递归方式求二叉查找树r中大于x的最小key
1
在查找方面二叉排序树效率与顺序查找的效率谁高(这里一般二叉排序树 不是指平衡二叉树)
0
树的可见性的存储问题,怎么采用C语言的程序的代码实现的
1
有没有大佬讲一手线段树的区间更新,初学,实在不懂
0
树的数据结构的可见性的判断的算法的问题,如何利用C语言的程序的编写的过程实现计算的?
2
二分查找判定树,有两个问题,求大佬支援。
0
树上的一个路径的表示的问题,怎么采用C语言的程序的编写的代码的实现的过程来做解决?