关于二叉排序树的创建

澈影

代码如下：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define TRUE 1
   
4. #define FALSE 0
   
5. //二叉排序树的节点结构定义
   
6. typedef struct BiTNode
   
7. {
   
8.         int data;
   
9.         struct BiTNode *lchild, *rchild;
   
10. } BiTNode, *BiTree;
    
11. 
    
12. void Insert(int num,BiTree *T);
    
13. int InsertBST2( BiTree *T, int key );
    
14. void construct(BiTree *T);
    
15. void destroy(BiTree *T);
    
16. //输入
    
17. 
    
18. void Insert(int num,BiTree *T)
    
19. {
    
20.         BiTree p;
    
21.         p = (*T);
    
22.         while(1)
    
23.         {
    
24.                 if(!p)
    
25.                 {
    
26.                         p = (BiTNode*)malloc(sizeof(BiTNode));
    
27.                         p->data = num;
    
28.                         break;
    
29.                 }else if(num >= p->data)
    
30.                 {
    
31.                         p = p->rchild;
    
32.                 }else if(num < p->data)
    
33.                 {
    
34.                         p = p->lchild;
    
35.                 }
    
36.         }
    
37. }
    
38. int InsertBST2( BiTree *T, int key )
    
39. {
    
40.         /* 当二叉排序树T中不存在关键字等于key的数据元素时 */
    
41.         /* 插入key并返回TRUE，否则返回FALSE */
    
42.         /* 未调用查找函数，递归插入 */
    
43.         if( !(*T) )                                                                        /* 树为空， */
    
44.         {
    
45.                 (*T) = (BiTree)malloc(sizeof(BiTNode));        /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */
    
46.                 (*T)->data = key;
    
47.                 (*T)->lchild = (*T)->rchild = NULL;
    
48.                 return TRUE;
    
49.         }
    
50.         if( key == (*T)->data )
    
51.                 return FALSE;
    
52.         if( key > (*T)->data )               
    
53.                 return InsertBST2( &((*T)->rchild), key );                /* 插入右孩子 */
    
54.         else
    
55.                 return InsertBST2( &((*T)->lchild), key );                /* 插入左孩子 */
    
56. }
    
57. 
    
58. //创建排序树
    
59. void construct(BiTree *T)
    
60. {
    
61.         int j;
    
62.         printf("请输入:");
    
63.     while(1)
    
64.     {
    
65.             scanf("%d",&j);
    
66.             //Insert(j,T);
    
67.             InsertBST2(T,j);
    
68.             if(getchar()=='\n')
    
69.             {
    
70.                     break;
    
71.                 }
    
72.         }
    
73. }
    
74. 
    
75. void InTraverse(BiTree T)
    
76. {
    
77.        
    
78.         if(T)
    
79.         {
    
80.                 InTraverse(T->lchild);
    
81.                 printf("%d ",T->data);
    
82.                 InTraverse(T->rchild);
    
83.         }
    
84. }
    
85. 
    
86. //销毁树
    
87. void destroy(BiTree *T)
    
88. {
    
89.         if(*T)
    
90.         {
    
91.                 destroy(&(*T)->lchild);
    
92.                 free(*T);
    
93.                 destroy(&(*T)->rchild);
    
94.         }
    
95. }
    
96. int main()
    
97. {
    
98.        
    
99.         BiTree T = NULL;       
    
100.         construct(&T);
     
101.         printf("二叉树递归中序遍历:\n");       
     
102.         InTraverse(T);
     
103.         destroy(&T);
     
104.        
     
105.         return 0;
     
106. }

复制代码

我是用循环使用插入函数来达到创建的目的，请问下我的Insert插入函数错在哪里？其他地方是没错的，我还特地找了网上别的插入函数来验证，求各位大佬帮帮忙！

最强废铁h

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

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #define TRUE 1
   
4. #define FALSE 0
   
5. //二叉排序树的节点结构定义
   
6. typedef struct BiTNode
   
7. {
   
8.         int data;
   
9.         struct BiTNode *lchild, *rchild;
   
10. } BiTNode, *BiTree;
    
11. 
    
12. void Insert(BiTree *T,int num);
    
13. int InsertBST2( BiTree *T, int key );
    
14. void construct(BiTree *T);
    
15. void destroy(BiTree *T);
    
16. //输入
    
17. 
    
18. void Insert(BiTree *T,int num)
    
19. {
    
20.         BiTree p;
    
21.         p = (*T);
    
22.         while(1)
    
23.         {
    
24.                 if(!p)
    
25.                 {
    
26.                         p = (BiTNode*)malloc(sizeof(BiTNode));
    
27.                         p->data = num;
    
28.                         break;
    
29.                 }else if(num >= p->data)
    
30.                 {
    
31.                         p = p->rchild;
    
32.                 }else if(num < p->data)
    
33.                 {
    
34.                         p = p->lchild;
    
35.                 }
    
36.         }
    
37. }
    
38. int InsertBST2( BiTree *T, int key )
    
39. {
    
40.         /* 当二叉排序树T中不存在关键字等于key的数据元素时 */
    
41.         /* 插入key并返回TRUE，否则返回FALSE */
    
42.         /* 未调用查找函数，递归插入 */
    
43.         if( !(*T) )                                                                        /* 树为空， */
    
44.         {
    
45.                 (*T) = (BiTree)malloc(sizeof(BiTNode));        /* 这个位置要留心，要重新分配空间，*T为空，说明未曾分配空间 */
    
46.                 (*T)->data = key;
    
47.                 (*T)->lchild = (*T)->rchild = NULL;
    
48.                 //return TRUE;
    
49.         }
    
50.         if( key == (*T)->data )
    
51.                 return FALSE;
    
52.         else if( key > (*T)->data )               
    
53.                 return InsertBST2( &((*T)->rchild), key );                /* 插入右孩子 */
    
54.         else
    
55.                 return InsertBST2( &((*T)->lchild), key );                /* 插入左孩子 */
    
56. }
    
57. 
    
58. //创建排序树
    
59. void construct(BiTree *T)
    
60. {
    
61.         int j,i,num;
    
62.         printf("请输入二叉树关键字数量:");
    
63.         scanf("%d",&num);                       
    
64.    for(i=1;i<=num;i++)      //构建二叉排序树
    
65.    {
    
66.                    printf("请输入 %d 个关键字:",j);
    
67.             scanf("%d",&j);
    
68.             InsertBST2(T,j);
    
69.    }
    
70.    /* while(1)
    
71.     {
    
72.             scanf("%d",&j);
    
73.             //Insert(j,T);
    
74.             InsertBST2(T,j);
    
75.             if(getchar()=='\n')
    
76.             {
    
77.                     break;
    
78.                 }
    
79.         }*/
    
80. }
    
81. 
    
82. void InTraverse(BiTree T)
    
83. {
    
84.         
    
85.         if(T)
    
86.         {
    
87.                 InTraverse(T->lchild);
    
88.                 printf("%d ",T->data);
    
89.                 InTraverse(T->rchild);
    
90.         }
    
91. }
    
92. 
    
93. //销毁树
    
94. void destroy(BiTree *T)
    
95. {
    
96.         if(*T)
    
97.         {
    
98.                 destroy(&(*T)->lchild);
    
99.                 free(*T);
    
100.                 destroy(&(*T)->rchild);
     
101.         }
     
102. }
     
103. int main()
     
104. {
     
105.         
     
106.         BiTree T = NULL;        
     
107.         construct(&T);
     
108.         printf("二叉树递归中序遍历:\n");        
     
109.         InTraverse(T);
     
110.         destroy(&T);
     
111.         
     
112.         return 0;
     
113. }

复制代码

澈影

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

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

澈影

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