最简单的二叉树插入不起作用
Simplest binary tree insertion is not working
#include<iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
node(int value = 0);
};
node::node(int value){
data = value;
left = NULL;
right = NULL;
}
class LinkedList{
public:
node *root;
LinkedList();
bool isEmpty();
void insertInto(int value, node *key);
};
LinkedList::LinkedList(){
root = NULL;
}
bool LinkedList::isEmpty(){
if(root == NULL) return true;
}
void LinkedList::insertInto(int value, node* root){
if (root == NULL)
{
node *n = new node(value);
root = n;
}
else if(value <= root->data){
insertInto(value, root->left);
}
else if(value > root->data){
insertInto(value,root->right);
}
}
int main() {
cout<<"I am gonna write the insertion of a binary tree"<<"\n";
LinkedList sample;
if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;
sample.insertInto(5,sample.root);
if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;
return 1;
}
我已经为此工作了很长一段时间,我似乎不明白为什么结果显示树是空的,即使在添加了值 5 之后。另外请提供有关如何改进的提示。谢谢
忽略我对您发布的代码 style/structure 的评论:
void LinkedList::insertInto(int value, node* root){
if (root == NULL)
{
node *n = new node(value);
root = n;
}
您没有在此处通过引用传递 node* root
变量。相反,您正在更改 node* root
的副本以指向您构造的新 node
对象。如果您希望此代码实际更改您从 main 传入的 sample.root
变量的值,则必须通过引用传递 root
。
void LinkedList::insertInto(int value, node* &root){
既然LinkedList::insertInto
无论如何都是一个成员函数,为什么要传入root呢?
您可以访问成员变量 root
,只需使用它即可。如果您仍然希望能够递归地使用它,您可以创建一个仅包含该值的 public 函数,并让该函数调用一个私有版本,该版本还接受一个 node*
作为参数。
这里有一些编码风格的建议,因为你要求它们:
最佳编码实践要求您将 class 的成员变量设为私有,并使用 public 成员函数来操纵 class。这是出于各种不同的原因。一种解释在这里:
https://softwareengineering.stackexchange.com/questions/143736/why-do-we-need-private-variables
所以你的 class(我们称它为 BinaryTree
)看起来像这样:
class BinaryTree{
public:
/* functions */
private:
node *root;
};
因此,我们没有让 class 的用户提供二叉树的根(这没有意义,因为我们知道它),我们只是要求他们插入值,并提供我们自己的根源。
class BinaryTree{
public:
/* other functions */
void insertInto(int value);
private:
void insertInto(int value, node* &n);
node *root;
};
// Public version of the insertInto function
void insertInto(int value) {
insertInto(value, root);
}
// Private helper function for insertInto
void insertInto(int value, node* &n) {
if (n == NULL)
{
n = new node(value);
}
else if(value <= root->data){
insertInto(value, root->left);
}
else if(value > root->data){
insertInto(value,root->right);
}
}
int main() {
BinaryTree sample;
sample.insertInto(5);
}
#include<iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
node(int value = 0);
};
node::node(int value){
data = value;
left = NULL;
right = NULL;
}
class LinkedList{
public:
node *root;
LinkedList();
bool isEmpty();
void insertInto(int value, node *key);
};
LinkedList::LinkedList(){
root = NULL;
}
bool LinkedList::isEmpty(){
if(root == NULL) return true;
}
void LinkedList::insertInto(int value, node* root){
if (root == NULL)
{
node *n = new node(value);
root = n;
}
else if(value <= root->data){
insertInto(value, root->left);
}
else if(value > root->data){
insertInto(value,root->right);
}
}
int main() {
cout<<"I am gonna write the insertion of a binary tree"<<"\n";
LinkedList sample;
if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;
sample.insertInto(5,sample.root);
if(sample.isEmpty()) cout<<"THe tree is empty"<<endl; else cout<<"The tree is NOT empty"<<endl;
return 1;
}
我已经为此工作了很长一段时间,我似乎不明白为什么结果显示树是空的,即使在添加了值 5 之后。另外请提供有关如何改进的提示。谢谢
忽略我对您发布的代码 style/structure 的评论:
void LinkedList::insertInto(int value, node* root){
if (root == NULL)
{
node *n = new node(value);
root = n;
}
您没有在此处通过引用传递 node* root
变量。相反,您正在更改 node* root
的副本以指向您构造的新 node
对象。如果您希望此代码实际更改您从 main 传入的 sample.root
变量的值,则必须通过引用传递 root
。
void LinkedList::insertInto(int value, node* &root){
既然LinkedList::insertInto
无论如何都是一个成员函数,为什么要传入root呢?
您可以访问成员变量 root
,只需使用它即可。如果您仍然希望能够递归地使用它,您可以创建一个仅包含该值的 public 函数,并让该函数调用一个私有版本,该版本还接受一个 node*
作为参数。
这里有一些编码风格的建议,因为你要求它们:
最佳编码实践要求您将 class 的成员变量设为私有,并使用 public 成员函数来操纵 class。这是出于各种不同的原因。一种解释在这里:
https://softwareengineering.stackexchange.com/questions/143736/why-do-we-need-private-variables
所以你的 class(我们称它为 BinaryTree
)看起来像这样:
class BinaryTree{
public:
/* functions */
private:
node *root;
};
因此,我们没有让 class 的用户提供二叉树的根(这没有意义,因为我们知道它),我们只是要求他们插入值,并提供我们自己的根源。
class BinaryTree{
public:
/* other functions */
void insertInto(int value);
private:
void insertInto(int value, node* &n);
node *root;
};
// Public version of the insertInto function
void insertInto(int value) {
insertInto(value, root);
}
// Private helper function for insertInto
void insertInto(int value, node* &n) {
if (n == NULL)
{
n = new node(value);
}
else if(value <= root->data){
insertInto(value, root->left);
}
else if(value > root->data){
insertInto(value,root->right);
}
}
int main() {
BinaryTree sample;
sample.insertInto(5);
}