[已解决]C++....................二叉排序树引用传递

十泉浩

问题在于第77行的插入函数和第35行构造函数中的调用
为什么在第一次插入的时候root可以随bt而改变
而在后面几次插入的时候root就不随bt而改变了

1. #include <iostream>
   
2. using namespace std;
   
3. //BiNode
   
4. template <typename DataType>
   
5. struct BiNode
   
6. {
   
7.     DataType data;
   
8.     BiNode* lchild, * rchild;
   
9. };
   
10. 
    
11. //BiSortTree
    
12. template <typename DataType>
    
13. class BiSortTree
    
14. {
    
15. public:
    
16.     BiSortTree(DataType r[], int n);    //建立关键字序列r[0]~r[n-1]的二叉排序树
    
17.     ~BiSortTree();       //析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数
    
18.     void InsertBST(BiNode<DataType>*& bt, DataType key);    //插入key
    
19.     BiNode<DataType>* SearchBST(BiNode<DataType>* bt, DataType key);   //查找值为k的结点，返回值为k所在结点的地址
    
20.     void InOrderBST(BiNode<DataType>* bt);   //中序遍历二叉树（递归）
    
21.     BiNode<DataType>* GetRoot();//获取root值
    
22. 
    
23. private:
    
24.     BiNode<DataType>* root;    //二叉排序树（即二叉链表）的根指针
    
25.     void Release(BiNode<DataType>*& bt);   //析构函数调用
    
26. };
    
27. 
    
28. //构造函数，将r[0]~r[n-1]各个元素依次插入，生成一棵二叉排序树
    
29. template <typename DataType>
    
30. BiSortTree<DataType>::BiSortTree(DataType r[], int n)//构造函数
    
31. {
    
32.     root = nullptr;  //初始化空二叉树
    
33.     int i;
    
34.     for (i = 0; i < n; i++) {   //进行n次插入
    
35.         InsertBST(root, r[i]);//将结点s插入到二叉排序树中,这里的root一直不变！！所以在插入时的初始bt一直指向root的数
    
36.     }
    
37. }
    
38. 
    
39. //析构函数，调用Release释放内存
    
40. template <typename DataType>
    
41. BiSortTree<DataType>::~BiSortTree()
    
42. {
    
43.     Release(root);
    
44. }
    
45. 
    
46. //释放二叉排序树的存储空间，调用析构函数实现
    
47. template <typename DataType>
    
48. void BiSortTree<DataType>::Release(BiNode<DataType>*& bt)
    
49. {
    
50.     if (bt) {
    
51.         Release(bt->lchild);   //释放左子树
    
52.         Release(bt->rchild);   //释放右子树
    
53.         delete bt;
    
54.     }
    
55. }
    
56. 
    
57. template <typename DataType>
    
58. BiNode<DataType>* BiSortTree<DataType>::GetRoot()
    
59. {
    
60.     return root;
    
61. }
    
62. 
    
63. template <typename DataType>
    
64. void  BiSortTree<DataType>::InOrderBST(BiNode<DataType>* bt)
    
65. {
    
66.     if (bt == nullptr) return;
    
67.     else
    
68.     {
    
69.         InOrderBST(bt->lchild);
    
70.         cout << bt->data << " ";
    
71.         InOrderBST(bt->rchild);
    
72.     }
    
73. }
    
74. 
    
75. //在下面补充实现相关算法
    
76. template <typename DataType>
    
77. void  BiSortTree<DataType>::InsertBST(BiNode<DataType>*& bt, DataType key)//35行使用  
    
78. {
    
79.     //1.如果不带 & 为什么不能传递：因为带 & 才能使树的改变保存下来
    
80.     //2.是指针之间的传参必须用引用传参吗？如果要让改变不止存留在函数中，就要用引用传参
    
81.     //3.如果用了引用传递，root的地址不会随bt的改变而改变吗：不会
    
82.     //BiNode<DataType>* p = bt;
    
83.     //如果不用&实现root将一直为空
    
84.     if (bt == NULL)
    
85.     {
    
86.         BiNode<DataType>* p = NULL;
    
87.         p = new BiNode<DataType>;
    
88.         p->data = key;
    
89.         p->lchild = NULL;
    
90.         p->rchild = NULL;
    
91.         bt = p;
    
92.     }
    
93.     else if (key == bt->data)
    
94.     {
    
95.         return;
    
96.     }
    
97.     else if (key > bt->data)
    
98.     {
    
99.         return InsertBST(bt->rchild, key);
    
100.     }
     
101.     else
     
102.     {
     
103.         return InsertBST(bt->lchild, key);
     
104.     }
     
105. }
     
106. template <typename DataType>
     
107. BiNode<DataType>* BiSortTree<DataType>::SearchBST(BiNode<DataType>* bt, DataType key)
     
108. {
     
109.     if (bt == NULL)return NULL;
     
110.     else if (bt->data == key)return bt;
     
111.     else if (bt->data > key)return SearchBST(bt->lchild, key);
     
112.     else return SearchBST(bt->rchild, key);
     
113.     //{
     
114.     //    SearchBST(bt->lchild, key);
     
115.     //    //cout << bt->data << " ";
     
116.     //    if (bt->data == key) goto g;
     
117.     //    SearchBST(bt->rchild, key);
     
118.     //g:if (bt->data == key)return bt; else return NULL;
     
119.     //}
     
120. }
     
121. 
     
122. //二叉排序树的主函数
     
123. int main() {
     
124.     int a[10], n;
     
125.     n = 0;
     
126.     while (1)
     
127.     {
     
128.         cin >> a[n];
     
129.         if (!a[n])break;  //输入数据以0结束
     
130.         n++;
     
131.     }
     
132.     BiSortTree<int> bst(a, n);//构造二叉排序树
     
133.     BiNode<int>* root;
     
134.     root = bst.GetRoot();
     
135.     cout << "Inorder:";
     
136.     bst.InOrderBST(root);//中序遍历二叉排序树（得到递增有序序列）
     
137.     cout << endl;
     
138.     int x;
     
139.     cin >> x;
     
140.     BiNode<int>* s;
     
141.     s = bst.SearchBST(root, x);
     
142.     if (s == nullptr) cout << "Find " << x << " failure";
     
143.     else cout << "Find " << x << " success";
     
144.     cout << endl;
     
145.     return 0;
     
146. }

复制代码

最佳答案

月排行榜 / 总排行榜

人造人

2021-4-3 00:20:09

提供一下下面这些信息
1. 这个程序的一组或多组输入
2. 你期望的输出结果
3. 程序现在的输出结果

知道了这3点，对调试程序很有帮助

跳转到最佳答案楼层

十泉浩

当root为空的时候，第一次插入操作，root随bt而变为bt的地址
当root不为空的时候，也就是后几次插入操作，bt改变而root不改变（用调试测试过了）

十泉浩

没人回答吗。。

人造人

提供一下下面这些信息
1. 这个程序的一组或多组输入
2. 你期望的输出结果
3. 程序现在的输出结果

知道了这3点，对调试程序很有帮助

人造人

还需要一个，你在写这个代码的时候主要参考了哪篇文章？我需要先去看看这篇文章，看看你这个代码的编写思路

十泉浩

人造人 发表于 2021-4-3 00:20
提供一下下面这些信息
1. 这个程序的一组或多组输入
2. 你期望的输出结果

感谢提醒
我刚才看了一眼恍然大悟
第一次执行p=bt的时候（91行）引用的是root
而后面几次执行p=bt的时候都是引用的bt->right或者bt->left
所以后面几次不会改变root的地址

还是回答下您的提醒把
这是我们学校oj上的题目，，答案是正确的
就是对实现过程有些疑惑
参考资料就是王红梅老师的数据结构书

感谢你的回答，就把你设成最佳答案啦

人造人

十泉浩 发表于 2021-4-4 19:25
感谢提醒
我刚才看了一眼恍然大悟
第一次执行p=bt的时候（91行）引用的是root

^_^