求大佬帮帮忙：二叉排序树的插入问题！！！

雪月圣雕

我根据数据结构与算法#整理 - 庖丁解牛中的代码，完成了一个二叉排序树的插入和查找算法。
但是，我发现插入算法有问题：只能插入一个，如果再次插入会将前一个覆盖。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define FALSE 0
   
5. #define TRUE 1
   
6. 
   
7. typedef struct BiTNode
   
8. {
   
9.         int data;
   
10.         struct BiTNode *lchild, *rchild;
    
11. }BiTNode, *BiTree;
    
12. 
    
13. int SearchBST(BiTree T, BiTree f, int key, BiTree *p);
    
14. int InsertBST(BiTree *T, int key);
    
15. 
    
16. /*
    
17.         1.递归遍历二叉树，有没有key
    
18.         2.如果有，则返回TRUE,并令p指向找到的结点。
    
19.         3.如果没有，则返回FALSE，并令p指向查找路径上失败结点的父结点
    
20.         4.如果T为空，那么返回FALSE，并令p指向T。
    
21.         @param1:T是二叉树。
    
22.         @param2：f为T的双亲结点指针，初始为NULL。
    
23.         @param3：key为待查结点的data值。
    
24.         @param4：p是查找指针，执行查找过程。
    
25.         注意：由于f、p、s都要接收或者链接T，所以类型必须一致都为BiTree
    
26. */
    
27. int SearchBST(BiTree T, BiTree f, int key, BiTree *p)
    
28. {
    
29.         if(!T)//查找不成功
    
30.         {
    
31.                 *p = T;
    
32.                 return FALSE;
    
33.         }
    
34.         else if(T->data == key)        //查找成功
    
35.         {
    
36.                 *p = T;
    
37.                 return TRUE;
    
38.         }
    
39.         else if(T->data > key)
    
40.         {
    
41.                 SearchBST(T->lchild, T, key, p);        //p内存放的是外部实参p的地址
    
42.         }
    
43.         else if(T->data < key)
    
44.         {
    
45.                 SearchBST(T->rchild, T, key, p);
    
46.         }
    
47. }
    
48. 
    
49. 
    
50. /*
    
51.         二叉排序树的插入：
    
52.         1.首先判断：二叉排序树中有没有相应结点。如果有：返回FALSE；如果没有，申请空间存放key并将其插入到失败结点的父结点之后。
    
53.         2.其次判断：二叉排序树是否为空（可用p来判断），若为空，则令新结点作为根结点。
    
54. */
    
55. int InsertBST(BiTree *T, int key)
    
56. {
    
57.         BiTree s, p;
    
58.        
    
59.         if(!SearchBST(*T, NULL, key, &p))        //如果没有该结点
    
60.         {
    
61.                 s = (BiTree)malloc(sizeof(BiTNode));
    
62.                 s->data = key;
    
63.                 s->lchild = NULL;
    
64.                 s->rchild = NULL;
    
65.                
    
66.                 if(!p)        //p为空结点时：树为空树
    
67.                 {
    
68.                         *T = s;
    
69.                 }
    
70.                 else if(key > p->data)
    
71.                 {
    
72.                         p->rchild = s;
    
73.                 }
    
74.                 else
    
75.                 {
    
76.                         p->lchild = s;
    
77.                 }
    
78.                 return TRUE;
    
79.         }
    
80.         else        //如果节点存在
    
81.         {
    
82.                 return FALSE;
    
83.         }
    
84. }
    
85. 
    
86. int main(void)
    
87. {
    
88.         BiTree T;
    
89.         BiTree p;
    
90.         int key, ch;
    
91.        
    
92.         T = NULL;
    
93.         p = NULL;
    
94.        
    
95.         printf("操作指南：\n");
    
96.         printf("1,代表插入\n");
    
97.         printf("2,代表查找\n");
    
98.         printf("0,代表结束\n");
    
99.        
    
100.         printf("请输入操作指令：");
     
101.         scanf("%d", &ch);
     
102.                
     
103.         while(ch)
     
104.         {
     
105.                
     
106.                 switch(ch)
     
107.                 {
     
108.                         case 1:
     
109.                                 printf("请输入待插入的值：");
     
110.                                 scanf("%d", &key);
     
111.                                 if(InsertBST(&T, key))
     
112.                                 {
     
113.                                         printf("插入成功！\n");
     
114.                                 }
     
115.                                 else
     
116.                                 {
     
117.                                         printf("插入失败！\n");
     
118.                                 }
     
119.                                 break;
     
120.                         case 2:
     
121.                                 printf("请输入待查找的值：");
     
122.                                 scanf("%d", &key);
     
123.                                 if(SearchBST(T, NULL, key, &p))
     
124.                                 {
     
125.                                         printf("查找%d成功\n", p->data);
     
126.                                 }
     
127.                                 else
     
128.                                 {
     
129.                                         printf("查找%d失败\n", key);
     
130.                                 }
     
131.                                 break;
     
132.                         default:
     
133.                                 break;
     
134.                 }
     
135.                
     
136.                 printf("请输入操作指令：");
     
137.                 scanf("%d", &ch);
     
138.        
     
139.         }
     
140.        
     
141.         return 0;
     
142. }

复制代码

雪月圣雕

已发现错误：第31行，*p = T; 改为：*p = f; 原因：见代码注释3