论坛 › 数据结构与算法 › 关于二叉排序树的创建

澈影 发表于 2021-12-7 19:44:42

关于二叉排序树的创建

代码如下：
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
//二叉排序树的节点结构定义
typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void Insert(int num,BiTree *T);
int InsertBST2( BiTree *T, int key );
void construct(BiTree *T);
void destroy(BiTree *T);
//输入

void Insert(int num,BiTree *T)
{
        BiTree p;
        p = (*T);
        while(1)
        {
                if(!p)
                {
                        p = (BiTNode*)malloc(sizeof(BiTNode));
                        p->data = num;
                        break;
                }else if(num >= p->data)
                {
                        p = p->rchild;
                }else if(num < p->data)
                {
                        p = p->lchild;
                }
        }
}
int InsertBST2( BiTree *T, int key )
{
        /* 当二叉排序树T中不存在关键字等于key的数据元素时 */
        /* 插入key并返回TRUE，否则返回FALSE */
        /* 未调用查找函数，递归插入 */
        if( !(*T) )                                                                        /* 树为空， */
        {
                (*T) = (BiTree)malloc(sizeof(BiTNode));        /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */
                (*T)->data = key;
                (*T)->lchild = (*T)->rchild = NULL;
                return TRUE;
        }
        if( key == (*T)->data )
                return FALSE;
        if( key > (*T)->data )               
                return InsertBST2( &((*T)->rchild), key );                /* 插入右孩子 */
        else
                return InsertBST2( &((*T)->lchild), key );                /* 插入左孩子 */
}

//创建排序树
void construct(BiTree *T)
{
        int j;
        printf("请输入:");
    while(1)
    {
            scanf("%d",&j);
            //Insert(j,T);
            InsertBST2(T,j);
            if(getchar()=='\n')
            {
                    break;
                }
        }
}

void InTraverse(BiTree T)
{
       
        if(T)
        {
                InTraverse(T->lchild);
                printf("%d ",T->data);
                InTraverse(T->rchild);
        }
}

//销毁树
void destroy(BiTree *T)
{
        if(*T)
        {
                destroy(&(*T)->lchild);
                free(*T);
                destroy(&(*T)->rchild);
        }
}
int main()
{
       
        BiTree T = NULL;       
        construct(&T);
        printf("二叉树递归中序遍历:\n");       
        InTraverse(T);
        destroy(&T);
       
        return 0;
}
我是用循环使用插入函数来达到创建的目的，请问下我的Insert插入函数错在哪里？其他地方是没错的，我还特地找了网上别的插入函数来验证，求各位大佬帮帮忙！

最强废铁h 发表于 2021-12-8 16:29:07

看你创建的代码怪怪的，改了下就行了

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
//二叉排序树的节点结构定义
typedef struct BiTNode
{
      int data;
      struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void Insert(BiTree *T,int num);
int InsertBST2( BiTree *T, int key );
void construct(BiTree *T);
void destroy(BiTree *T);
//输入

void Insert(BiTree *T,int num)
{
      BiTree p;
      p = (*T);
      while(1)
      {
                if(!p)
                {
                        p = (BiTNode*)malloc(sizeof(BiTNode));
                        p->data = num;
                        break;
                }else if(num >= p->data)
                {
                        p = p->rchild;
                }else if(num < p->data)
                {
                        p = p->lchild;
                }
      }
}
int InsertBST2( BiTree *T, int key )
{
      /* 当二叉排序树T中不存在关键字等于key的数据元素时 */
      /* 插入key并返回TRUE，否则返回FALSE */
      /* 未调用查找函数，递归插入 */
      if( !(*T) )                                                                        /* 树为空， */
      {
                (*T) = (BiTree)malloc(sizeof(BiTNode));      /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */
                (*T)->data = key;
                (*T)->lchild = (*T)->rchild = NULL;
                //return TRUE;
      }
      if( key == (*T)->data )
                return FALSE;
      else if( key > (*T)->data )               
                return InsertBST2( &((*T)->rchild), key );                /* 插入右孩子 */
      else
                return InsertBST2( &((*T)->lchild), key );                /* 插入左孩子 */
}

//创建排序树
void construct(BiTree *T)
{
      int j,i,num;
      printf("请输入二叉树关键字数量:");
      scanf("%d",&num);                     
   for(i=1;i<=num;i++)      //构建二叉排序树
   {
                   printf("请输入 %d 个关键字:",j);
            scanf("%d",&j);
            InsertBST2(T,j);
   }
   /* while(1)
    {
            scanf("%d",&j);
            //Insert(j,T);
            InsertBST2(T,j);
            if(getchar()=='\n')
            {
                  break;
                }
      }*/
}

void InTraverse(BiTree T)
{
      
      if(T)
      {
                InTraverse(T->lchild);
                printf("%d ",T->data);
                InTraverse(T->rchild);
      }
}

//销毁树
void destroy(BiTree *T)
{
      if(*T)
      {
                destroy(&(*T)->lchild);
                free(*T);
                destroy(&(*T)->rchild);
      }
}
int main()
{
      
      BiTree T = NULL;      
      construct(&T);
      printf("二叉树递归中序遍历:\n");      
      InTraverse(T);
      destroy(&T);
      
      return 0;
}

澈影 发表于 2021-12-8 21:23:40

最强废铁h 发表于 2021-12-8 16:29
看你创建的代码怪怪的，改了下就行了

那个，不是construct函数出问题啦{:10_250:}是Insert函数，我这程序运行得出来的，因为我是拿了网上一个Insert函数，就是那个BSTInsert2,只是我换成了我自己写的那个Insert就出错了，我看不出那Insert函数错在哪里{:10_247:}

澈影 发表于 2021-12-12 13:21:01

最后我自己找到原因了。由于不知道怎么删帖，自己也给不了弄不了最佳答案，只能先先搁这了。哪位知道怎么删帖的告诉我一声呗{:10_269:}

查看完整版本: 关于二叉排序树的创建