C++ 二叉树实现C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20444612/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Binary Tree implementation C++
提问by DELIGUCU
Binary Tree insertion:
二叉树插入：
#include "stdafx.h"
#include <iostream>
using namespace std;
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
struct TreeType {
TreeNode* root;
void insert(TreeNode* tree, int item);
void insertItem(int value) {
insert(root, value);
}
};
void TreeType::insert(TreeNode* tree, int number) {
if (tree == NULL) {
tree = new TreeNode;
tree->left = NULL;
tree->right = NULL;
tree->value = number;
cout << "DONE";
} else if (number < tree->value) {
insert(tree->left, number);
} else {
insert(tree->right, number);
}
}
int main() {
TreeType* MyTree = new TreeType;
MyTree->insertItem(8);
return 0;
}
I am currently learning Data structures in C++ and this is the code that make insertion in binary trees.
我目前正在学习 C++ 中的数据结构，这是在二叉树中进行插入的代码。
After it is compiled, everything looks fine, however when i try to execute this program, it crashed.
编译后，一切看起来都很好，但是当我尝试执行该程序时，它崩溃了。
Can anybody tell me where I am wrong?
谁能告诉我我错在哪里？
回答by Homer6
In your tree constructor, you need to initialize the root pointer to NULL. It's not guaranteed to be initialized as NULL.
在您的树构造函数中，您需要将根指针初始化为 NULL。不能保证初始化为 NULL。
When you compile in linux, you can use gdb to show where the source of the segfault is coming from.
在linux下编译时，可以使用gdb来显示segfault的来源。
Some other notes:
其他一些注意事项：
- You should assign the value back to
rootafter you've allocated the new node. You're not doing that because you're missing one of the fundamentals of c++. That is, it's based on c. And the thing about c is that is strictly a "by-value" function/method calling paradigm. So all parameters in a function call are by value. When you pass in the memory address for root, you're actually copying the value of the pointer. Then, you're only updating the local value. You need to assign it back to root. If you'd like to learn that concept front to back, I highly recommend watching Jerry Cain's Programming Paradigms course at Stanford. - In your main function, you should try to keep the symbol names as lower_case instead of CamelCase. This helps differentiate variables from types (types should stay CamelCase).
- In your TreeType::insert method, you should call the variable tree_node instead of tree. Doing so helps reflect the correct type and avoids confusion.
- Whenever possible, try you use the
this->rootandthis->insertnotation. Not only will it correctly resolve if you accidentally create a locally scopedrootvariable, but it's also clearer to the reader where the data or method is defined. Great coding is about communication. It may only take 100-500ms less for the reader to understand where the symbol points to; however, the tiny savings that you can accumulate in avoiding ambiguities add up into a much clearer piece of software. Your future self (and your colleagues) will thank you. See http://msmvps.com/blogs/jon_skeet/archive/2013/09/21/career-and-skills-advice.aspx
- 您应该
root在分配新节点后重新分配该值。您没有这样做是因为您缺少 C++ 的基础知识之一。也就是说，它基于 c。关于 c 的事情是严格的“按值”函数/方法调用范式。所以函数调用中的所有参数都是按值的。当您为 root 传递内存地址时，您实际上是在复制指针的值。然后，您只更新本地值。您需要将其分配回 root。如果您想从头到尾学习这个概念，我强烈建议您观看斯坦福大学 Jerry Cain 的编程范式课程。 - 在您的主函数中，您应该尝试将符号名称保留为小写而不是驼峰式。这有助于区分变量和类型（类型应该保持 CamelCase）。
- 在您的 TreeType::insert 方法中，您应该调用变量 tree_node 而不是 tree。这样做有助于反映正确的类型并避免混淆。
- 只要有可能，请尝试使用
this->rootandthis->insert表示法。如果您不小心创建了局部作用域root变量，它不仅会正确解析，而且对于定义数据或方法的读者来说也更清楚。伟大的编码是关于沟通的。读者理解符号指向的位置可能只需要少 100-500 毫秒；但是，您可以在避免歧义方面积累的微小节省加起来会变成一个更清晰的软件。你未来的自己（和你的同事）会感谢你。见http://msmvps.com/blogs/jon_skeet/archive/2013/09/21/career-and-skills-advice.aspx
Lastly, I can overstate enough how important learning from the source is. If you're learning c or c++ for the first time, read http://www.amazon.com/The-Programming-Language-4th-Edition/dp/0321563840and http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628. It will save you hours, upon hours, upon hours. After having learned from the source, programming is also A LOT more enjoyable because you understand a good portion of the concepts. And, the truth is, things are more fun when you have a decent level of competence in them.
最后，我可以夸大从源头学习的重要性。如果您是第一次学习 c 或 c++，请阅读http://www.amazon.com/The-Programming-Language-4th-Edition/dp/0321563840和http://www.amazon.com/Programming- Language-2nd-Brian-Kernighan/dp/0131103628。它将为您节省数小时、数小时、数小时的时间。从源代码中学习之后，编程也会变得更加有趣，因为您理解了大部分概念。而且，事实是，当你有足够的能力时，事情会更有趣。
回答by Mike Minaev
Try something like this-
尝试这样的事情 -
struct Node {
int Data;
Node* Left;
Node* Right;
};
Node* Find( Node* node, int value )
{
if( node == NULL )
return NULL;
if( node->Data == value )
return node;
if( node->Data > value )
return Find( node->Left, value );
else
return Find( node->Right, value );
};
void Insert( Node* node, int value )
{
if( node == NULL ) {
node = new Node( value );
return;
}
if( node->Data > value )
Insert( node->Left, value );
else
Insert( node->Right, value );
};
回答by Abhishek Bansal
In your TreeType constructor I think you should explicitly make root point to NULL.
在您的 TreeType 构造函数中，我认为您应该明确地将 root 指向 NULL。
TreeType::TreeType() {
root = NULL;
}
