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

十泉浩

问题在于第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[0]~r[n-1]的二叉排序树
    ~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[0]~r[n-1]各个元素依次插入，生成一棵二叉排序树
template <typename DataType>
BiSortTree<DataType>::BiSortTree(DataType r[], int n)//构造函数
{
    root = nullptr;  //初始化空二叉树
    int i;
    for (i = 0; i < n; i++) {   //进行n次插入
        InsertBST(root, r[i]);//将结点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>
void  BiSortTree<DataType>::InOrderBST(BiNode<DataType>* bt)
{
    if (bt == nullptr) return;
    else
    {
        InOrderBST(bt->lchild);
        cout << bt->data << " ";
        InOrderBST(bt->rchild);
    }
}

//在下面补充实现相关算法
template <typename DataType>
void  BiSortTree<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[10], n;
    n = 0;
    while (1)
    {
        cin >> a[n];
        if (!a[n])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-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

^_^