C++....................二叉排序树引用传递,C\C++交流,技术交流,鱼C论坛

十泉浩 发表于 2021-4-1 15:50:31

C++....................二叉排序树引用传递

本帖最后由十泉浩于 2021-4-1 15:51 编辑

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

#include <iostream>
using namespace std;
//BiNode
template <typename DataType>
struct BiNode
{
DataType data;
BiNode* lchild, * rchild;
};

//BiSortTree
template <typename DataType>
class BiSortTree
{
public:
BiSortTree(DataType r[], int n); //建立关键字序列r~r的二叉排序树
~BiSortTree();    //析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数
void InsertBST(BiNode<DataType>*& bt, DataType key); //插入key
BiNode<DataType>* SearchBST(BiNode<DataType>* bt, DataType key); //查找值为k的结点，返回值为k所在结点的地址
void InOrderBST(BiNode<DataType>* bt); //中序遍历二叉树（递归）
BiNode<DataType>* GetRoot();//获取root值

private:
BiNode<DataType>* root; //二叉排序树（即二叉链表）的根指针
void Release(BiNode<DataType>*& bt); //析构函数调用
};

//构造函数，将r~r各个元素依次插入，生成一棵二叉排序树
template <typename DataType>
BiSortTree<DataType>::BiSortTree(DataType r[], int n)//构造函数
{
root = nullptr;//初始化空二叉树
int i;
for (i = 0; i < n; i++) { //进行n次插入
   InsertBST(root, r);//将结点s插入到二叉排序树中,这里的root一直不变！！所以在插入时的初始bt一直指向root的数
}
}

//析构函数，调用Release释放内存
template <typename DataType>
BiSortTree<DataType>::~BiSortTree()
{
Release(root);
}

//释放二叉排序树的存储空间，调用析构函数实现
template <typename DataType>
void BiSortTree<DataType>::Release(BiNode<DataType>*& bt)
{
if (bt) {
   Release(bt->lchild); //释放左子树
   Release(bt->rchild); //释放右子树
   delete bt;
}
}

template <typename DataType>
BiNode<DataType>* BiSortTree<DataType>::GetRoot()
{
return root;
}

template <typename DataType>
voidBiSortTree<DataType>::InOrderBST(BiNode<DataType>* bt)
{
if (bt == nullptr) return;
else
{
   InOrderBST(bt->lchild);
   cout << bt->data << " ";
   InOrderBST(bt->rchild);
}
}

//在下面补充实现相关算法
template <typename DataType>
voidBiSortTree<DataType>::InsertBST(BiNode<DataType>*& bt, DataType key)//35行使用
{
//1.如果不带 & 为什么不能传递：因为带 & 才能使树的改变保存下来
//2.是指针之间的传参必须用引用传参吗？如果要让改变不止存留在函数中，就要用引用传参
//3.如果用了引用传递，root的地址不会随bt的改变而改变吗：不会
//BiNode<DataType>* p = bt;
//如果不用&实现root将一直为空
if (bt == NULL)
{
   BiNode<DataType>* p = NULL;
   p = new BiNode<DataType>;
   p->data = key;
   p->lchild = NULL;
   p->rchild = NULL;
   bt = p;
}
else if (key == bt->data)
{
   return;
}
else if (key > bt->data)
{
   return InsertBST(bt->rchild, key);
}
else
{
   return InsertBST(bt->lchild, key);
}
}
template <typename DataType>
BiNode<DataType>* BiSortTree<DataType>::SearchBST(BiNode<DataType>* bt, DataType key)
{
if (bt == NULL)return NULL;
else if (bt->data == key)return bt;
else if (bt->data > key)return SearchBST(bt->lchild, key);
else return SearchBST(bt->rchild, key);
//{
// SearchBST(bt->lchild, key);
// //cout << bt->data << " ";
// if (bt->data == key) goto g;
// SearchBST(bt->rchild, key);
//g:if (bt->data == key)return bt; else return NULL;
//}
}

//二叉排序树的主函数
int main() {
int a, n;
n = 0;
while (1)
{
   cin >> a;
   if (!a)break;//输入数据以0结束
   n++;
}
BiSortTree<int> bst(a, n);//构造二叉排序树
BiNode<int>* root;
root = bst.GetRoot();
cout << "Inorder:";
bst.InOrderBST(root);//中序遍历二叉排序树（得到递增有序序列）
cout << endl;
int x;
cin >> x;
BiNode<int>* s;
s = bst.SearchBST(root, x);
if (s == nullptr) cout << "Find " << x << " failure";
else cout << "Find " << x << " success";
cout << endl;
return 0;
}

十泉浩 发表于 2021-4-1 15:52:55

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

十泉浩 发表于 2021-4-2 22:40:19

没人回答吗。。{:10_266:}

人造人 发表于 2021-4-3 00:20:09

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

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

人造人 发表于 2021-4-3 00:39:02

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

十泉浩 发表于 2021-4-4 19:25:59

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

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

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

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

人造人 发表于 2021-4-4 19:39:35

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

^_^

页: [1]

鱼C论坛's Archiver

C++....................二叉排序树引用传递