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

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

项目总共三个文件,二叉搜索树头文件.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;
  ...
}

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

qq_35868760

输入序列生成二叉树(c++版的)

1条回答

为你推荐