二叉排序树的插入错误
BST.h#pragma once
#include <iostream>
using namespace std;
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
bool SearchBST(BiTree Tree, int key, BiTree LastNode, BiTree *PtrLastNode);
bool InsertBST(BiTree Tree, int key);
BST.cpp
#include "BST.h"
bool SearchBST(BiTree Tree, int key, BiTree LastNode, BiTree *PtrLastNode)
{
if (!Tree)
{
*PtrLastNode = LastNode;
return false;
}
else if(Tree->data == key)
{
*PtrLastNode = Tree;
return true;
}
else if (Tree->data < key)
{
return SearchBST(Tree->rchild, key, Tree, PtrLastNode);
}
else
{
return SearchBST(Tree->lchild, key, Tree, PtrLastNode);
}
}
bool InsertBST(BiTree Tree, int key)
{
BiTree PtrLastNode;
if (!SearchBST(Tree, key, nullptr, &PtrLastNode))
{
BiTree s = new BiTNode;
s->data = key;
s->lchild = s->rchild = nullptr;
if (!PtrLastNode)
{
Tree = s;
}
else if (PtrLastNode->data > key)
{
PtrLastNode->lchild = s;
}
else
{
PtrLastNode->rchild = s;
}
return true;
}
else
{
return false;
}
}
main.cpp
#include "BST.h"
int main()
{
int a = { 5, 2, 1, 4, 7, 9, 0 ,8, 3, 6 };
BiTree Tree = nullptr;
for (int i = 0; i < 10; ++i)
{
InsertBST(Tree, a);
}
}
运行后，每次虽然显示插入成功了，但是Tree始终为nullptr空指针。
我向InsertBST传入的已经是一个指针Tree了，为什么在InsertBST中将s赋值给Tree后仍然为空？
感谢！ 嗨，鱼油！看你的问题，我觉得你可能掉进了一个常见的C++陷阱里。让我们一起来探讨一下这个问题，同时用点幽默让它更容易理解。
### 问题所在
你提到每次插入节点后，`Tree` 还是空的。这个问题其实出在 `InsertBST` 函数中，你对 `Tree` 进行了修改，但是这种修改并没有反映到调用 `InsertBST` 的地方。
简单地说，你传给 `InsertBST` 的是一个指针（Tree），但是指针本身是按值传递的。就像你把一个小纸条（地址）递给朋友，但朋友只是在他那里写了写，原来的纸条内容并没有改变。
### 解决方案
要解决这个问题，你有几种选择。其中一种是直接传递指针的指针，即指向指针的引用，这样你就能原地修改 `Tree` 了。让我们来改改代码吧！
#### 修改后的代码
我们先从 `InsertBST` 函数开始改造：
bool InsertBST(BiTree& Tree, int key)// 将Tree声明为BiTree的引用
{
BiTree PtrLastNode;
if (!SearchBST(Tree, key, nullptr, &PtrLastNode))
{
BiTree s = new BiTNode;
s->data = key;
s->lchild = s->rchild = nullptr;
if (!PtrLastNode)
{
Tree = s;// 这里会修改实际传入的Tree
}
else if (PtrLastNode->data > key)
{
PtrLastNode->lchild = s;
}
else
{
PtrLastNode->rchild = s;
}
return true;
}
else
{
return false;
}
}
接下来，在调用 `InsertBST` 时，也要进行适配：
int main()
{
int a = { 5, 2, 1, 4, 7, 9, 0 ,8, 3, 6 };// 注意数组定义语法上有个小错误，修正一下
BiTree Tree = nullptr;
for (int i = 0; i < 10; ++i)
{
InsertBST(Tree, a);// 传递Tree的引用
}
}
### 谈谈选择的问题
如果你不喜欢使用引用，还可以选择其他方法，比如传递指向指针的指针：
bool InsertBST(BiTree* &Tree, int key);// 使用指针的指针
这样你也能通过指针的指针修改原始指针所指向的内容。
### 总结
希望以上解答对你有帮助！其实编程有时就像玩拼图，找到合适的片段放到对的位置，整个图就出来了。记住，玩得开心，不必太过于纠结！
加油，鱼油！如果还有问题，请随时问我，咱们继续搞定它！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]