关于排序二叉树的插入操作和输出节点的问题

Ranbo_

刚学排序二叉树，题目描述这样的：有N个关键字值各不相同的节点，要求按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

我的代码是这样的：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node{
   
5.     int val;
   
6.     struct Node *lchild;
   
7.     struct Node *rchild;
   
8. }BTNode;
   
9. //创建节点
   
10. void create(BTNode *T, int value)
    
11. {
    
12.     T = (BTNode*) malloc(sizeof(BTNode));
    
13.     T -> lchild = NULL;
    
14.     T -> rchild = NULL;
    
15.     T -> val = value;
    
16. }
    
17. //插入节点，并输出父节点的值
    
18. int insert(BTNode *T, int value, int father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
    
19. {
    
20.     if(T == NULL)        //若T为空，说明已经找到叶节点，则创建新节点并输出父节点的值
    
21.     {
    
22.         create(T, value);
    
23.         //printf("%d\n", father);
    
24.         return father;
    
25.     }
    
26.     else if(value > T -> val)//若待插键值>当前节点键值，则插入到右子树上
    
27.     {
    
28.         return insert(T -> rchild, value, T -> val);
    
29.         //T -> rchild = insert(T -> rchild, value, T -> val);
    
30.     }
    
31.     else//若待插键值<当前节点键值，则插入到左子树上
    
32.     {
    
33.         return insert(T -> lchild, value, T -> val);
    
34.         //T -> lchild = insert(T -> lchild, value, T -> val);
    
35.     }
    
36. }
    
37. 
    
38. /*
    
39. //后序遍历清空树
    
40. void clear(BTNode *p)
    
41. {
    
42.     clear(p -> lchild);
    
43.     clear(p -> rchild);
    
44.     free(p);
    
45. }
    
46. */
    
47. 
    
48. int main()
    
49. {
    
50.     int n;
    
51.     int i;
    
52.     BTNode *T = (BTNode*) malloc(sizeof(BTNode));
    
53.     BTNode *root = T;
    
54.     scanf("%d", &n);//n个节点
    
55.         scanf("%d", &i);
    
56.         root -> val = i;
    
57.         root -> lchild = NULL;
    
58.         root -> rchild = NULL;
    
59.         printf("%d\n", -1);
    
60.         int value;
    
61.         for(i = 0; i < n - 1; i++)
    
62.         {
    
63.             T = root;
    
64.             //int father = -1;    //初始化储存的父节点的值
    
65.             int father;
    
66.             scanf("%d", &value);
    
67.             father = insert(T, value, -1);
    
68.             printf("%d\n", father);
    
69.         }
    
70.         /*
    
71.         BTNode *p = root;
    
72.         //后序遍历清空树
    
73.         clear(p);
    
74.         */
    
75.     return 0;
    
76. }

复制代码

有一个问题，就是我不管输入啥玩意儿进去它永远都输出的是根节点的值，这是为啥呀

ba21

一段怎么看怎么别扭的代码。


对指针还没有理解到位， 对树理解还很不足，对递归不理解。

1. BTNode *T = (BTNode*) malloc(sizeof(BTNode));
   
2.        T = NULL; // 这2行代码看着不别扭？
   
3. 直接
   
4. BTNode *T = NULL不行吗？
   

复制代码

1. 
   
2. // 前面看你传father 后面又看你传-1，是我没搞懂你的思维方式？ 我觉得father = insert(T, value) 这样够了吧。
   
3. father = insert(T, value, father);
   
4. father = insert(T, value, -1);
   

复制代码

1. 
   
2. // 实现递归的2个基本条件
   
3. // -调用函数本身
   
4. // -设置了正确的结束条件
   
5. int insert(BTNode *T, int value, int father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
   
6. {
   
7.     if(T == NULL)        //若T为空，说明已经找到叶节点，则创建新节点并输出父节点的值
   
8.     {
   
9.         create(T, value);
   
10.         //printf("%d\n", father);
    
11.         return father;
    
12.     }
    
13.     else if(value > T -> val)//若待插键值>当前节点键值，则插入到右子树上
    
14.     {
    
15.         return insert(T -> rchild, value, T -> val);
    
16.         //T = insert(T -> rchild, value, T -> val);
    
17.     }
    
18.     else//若待插键值<当前节点键值，则插入到左子树上
    
19.     {
    
20.         return insert(T -> lchild, value, T -> val);
    
21.         //T = insert(T -> lchild, value, T -> val);
    
22.     }
    
23. }
    

复制代码

我的建议 把基础打好，多练习，多打代码；别一头牛似的什么基础都没搞懂就一直冲。。。你这代码跟本没法给你解答，给你改完就以经全不是你的代码了。

Ranbo_

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. typedef struct Node{
   
5.     int val;
   
6.     struct BTNode *lchild;
   
7.     struct BTNode *rchild;
   
8. }BTNode;
   
9. 
   
10. BTNode* insert(BTNode *T, int value, int *father)//T为当前访问的节点，value是待插入节点的键值，father为当前访问节点的父节点的键值
    
11. {
    
12.     if(T == NULL)
    
13.     {
    
14.         T = (BTNode*) malloc(sizeof(BTNode));
    
15.         T -> lchild = NULL;
    
16.         T -> rchild = NULL;
    
17.         T -> val = value;
    
18.         return T;
    
19.     }
    
20.     else if(value > T -> val)
    
21.     {
    
22.         *father = T -> val;
    
23.         T -> rchild = insert(T -> rchild, value, father);
    
24.     }
    
25.     else
    
26.     {
    
27.         *father = T -> val;
    
28.         T -> lchild = insert(T -> lchild, value, father);
    
29.     }
    
30.     return T;
    
31. }
    
32. 
    
33. int main()
    
34. {
    
35.     BTNode *t = NULL;
    
36.     int n;
    
37.     int i;
    
38.     scanf("%d", &n);//n个节点
    
39.     int value;
    
40.     for(i = 0; i < n; i++)
    
41.     {
    
42.         int father = -1;    //初始化储存的父节点的值
    
43.         scanf("%d", &value);
    
44.         t = insert(t, value, &father);
    
45. 
    
46.         printf("%d\n", father);
    
47.     }
    
48. 
    
49.     return 0;
    
50. }
    
51. 
    

复制代码

重新学习了排序二叉树的构建和函数调用改了一遍终于改出来了，确实是基础超级不行哈，还是得慢慢摸索。我本科生物，只学了数据库技术，对计算机各类语言一点都不了解，考研834数据结构极其简单所以只学了皮毛，复试要笔试算法和机试，前一个多月恶补C语言，现在再写完整代码力不从心，本来就是实操不足哈，再过一个多月就得复试，只能边敲代码便理解了。问的问题确实很蠢，还希望各位不吝赐教哈