C++ 递归地将元素插入二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3116626/
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
Recursively Insert Element Into A Binary Tree
提问by IAE
So I finished my List exercise and went ahead with Binary Trees. My code thus far:
所以我完成了我的列表练习并继续使用二叉树。到目前为止我的代码：
Tree.h
树.h
#include "Node.h"
class Tree
{
private:
int mCount;
Node *root;
public:
Tree();
~Tree();
void insert(int, Node *);
};
Tree.cpp
树.cpp
void Tree::insert(int data, Node *node)
{
if( root == 0 )
{
Node *temp = new Node;
temp->setData(100);
temp->setRight(0);
temp->setLeft(0);
root = temp;
}
else
{
if( data > root->getData() )
return insert( data, root->getRight() );
else
return insert( data, root->getLeft() );
}
}
main.cpp
主程序
int main(int argc, char** argv)
{
Tree *tree = new Tree;
tree->insert( 100, 0 );
std::cin.get();
return 0;
}
I hope this is sufficient code. Nodeand Treeare two separate classes. I'm having difficulties wrapping my head around the recursion.
我希望这是足够的代码。Node并且Tree是两个独立的类。我在递归时遇到了困难。
I have Node *rootdefined in my Tree class to have a root node at the top of the tree. However, the way I see it, when I call tree->insertinsert in main, I don't have to specify any node. The root from the Tree class will do all the looking. However, when I'm in the code and need to recur, then I am suddenly a parameter short, as shown above.
我Node *root在 Tree 类中定义了在树的顶部有一个根节点。但是，在我看来，当我tree->insert在 main 中调用insert 时，我不必指定任何节点。Tree 类的根将完成所有查找。但是，当我在代码中并且需要重复时，那么我突然一个参数短，如上所示。
My solution was to just place the parameter Node *nodein the argument list for insert()anyway and call it with a 0from main. I would also need to call tree->display(0);as parameter for Node *nodeas well.
我的解决方案是将参数Node *node放在参数列表中insert()，并使用0from main调用它。我还需要调用tree->display(0);作为参数Node *node。
This seems hackish. Am I missing something obvious?
这看起来很hackish。我错过了一些明显的东西吗？
回答by utnapistim
A few points:
几点：
First, don't use Node**. That err "uglifies" your code. Use Node*&instead (see answers here) if you really need to.
首先，不要使用Node**. 那个错误“丑化”了你的代码。如果您确实需要，请Node*&改用（请参阅此处的答案）。
Second, you do not need a recursive call (unless you want to use one).
其次，您不需要递归调用（除非您想使用一个）。
Non-recursive insert method:
非递归插入方法：
void Tree::insert(int data)
{
if(!root)
{
root = new Node(data); // Node constructor should receive
// the data value and init internal value from it
// it should also set left and right pointers to 0
return;
}
Node* insertIterator = root;
Node* parent = 0;
while(insertIterator)
{
parent = insertIterator;
insertIterator = data < insertIterator->getData()
? insertIterator->getLeft()
: insertIterator->getRight();
}
if(data < parent->getData())
parent->setLeft( new Node(data) );
else
parent->setRight( new Node(data) );
}
If you douse a recursive method, use a recursive method that finds the insertion point, instead of a recursive method that performs the insertion. Basically, replace the while loop in the code above with a separate method (FindInsertionPointin my code below):
如果确实使用递归方法，请使用查找插入点的递归方法，而不是执行插入的递归方法。基本上，用一个单独的方法（FindInsertionPoint在我下面的代码中）替换上面代码中的 while 循环：
Node* Tree::FindInsertionPoint(int data, Node * parent) // this should be private
{
Node* insertPoint = data < parent.getData()
? parent->getLeft()
: parent->getRight();
return insertPoint
? FindInsertionPoint(data, insertPoint)
: parent;
}
void Tree::Insert(int data) // this should be public
{
if(!root)
{
root = new Node(data);
return;
}
Node* parent = FindInsertionPoint(data, root);
if(data < parent.getData())
parent->setLeft(new Node(data)); // see comment on Node constructor above
else
parent->setRight(new Node(data)); // see comment on Node constructor above
}
Edit:
编辑：
I'm having difficulties wrapping my head around the recursion.
我在递归时遇到了困难。
Look at it like this: to find the insertion point, you know that you need to insert as a child of the left or the right subnode. To insert to the left, you need to insert as a child of the left or the right subnodeof the left child of the current node. That is, if you insert to the left, call the find the insertion pointpart for the left child; otherwise, call the find the insertion pointfor the right subnode.
像这样看：要找到插入点，您知道需要作为左子节点或右子节点的子节点插入。要向左插入，需要作为当前节点的左子节点的左子节点或右子节点插入。即如果向左插入，则调用查找左孩子的插入点部分；否则，调用查找右子节点的插入点。
What you need to do to define a recursive algorithm:
定义递归算法需要做什么：
identify the algorithm as it applies to a part of your data (in this case, you need to insert as a child of the left or the right subnode).
identify the stopping condition (when is the algorithm stopping?). If you do not, you get infinite recursion and a stackoverflowerror :).
identify the variable part of the algorithm (this should tell you what parameters your recursive function will have).
识别算法，因为它适用于您的数据的一部分（在这种情况下，您需要作为左子节点或右子节点的子节点插入）。
确定停止条件（算法何时停止？）。如果你不这样做，你会得到无限递归和计算器溢出错误:)。
确定算法的可变部分（这应该告诉您递归函数将具有哪些参数）。
回答by Péter T?r?k
You are currently not using the nodeparameter at all in Tree::insert, which effectively means that it will recurse infinitely if you already have a root node.
您目前根本没有使用nodein 参数Tree::insert，这实际上意味着如果您已经有一个根节点，它将无限递归。
The best solution would be to define a public insert method without node parameter, which calls another, private insert method with the root parameter, which in turn recursively calls itself. This way your API is clean, not allowing its clients to insert elements directly (and incorrectly) into subtrees.
最好的解决方案是定义一个没有节点参数的公共插入方法，该方法调用另一个具有根参数的私有插入方法，该方法依次递归调用自身。通过这种方式，您的 API 是干净的，不允许其客户端直接（并且错误地）将元素插入子树中。
Note that the parameter itself must be changed to Node**Node*&, since at the point of insertion, you want to modify the pointer in the parent node.
请注意，参数本身必须更改为，因为在插入点，您希望修改父节点中的指针。Node**Node*&
[Update]Also it would be recommended to add a constructor to Nodewhich takes the data value and initializes its left and right pointers to 0. This simplifies the caller code noticeably. [/Update]
[更新]此外，建议添加一个构造函数，Node该构造函数接受数据值并将其左右指针初始化为 0。这显着简化了调用者代码。[/更新]
So the final result would look something like this:
所以最终的结果应该是这样的：
void Tree::insert(int data)
{
return insert( data, root );
}
void Tree::insert(int data, Node *&node)
{
if( node == 0 )
{
node = new Node(data);
}
else
{
if( data > node->getData() )
return insert( data, node->getRight() );
else
return insert( data, node->getLeft() );
}
}
回答by stinky472
Péter gave a perfectly nice example. Only thing I see is that temp->setData(100) should be temp->setData(data);
彼得举了一个非常好的例子。我唯一看到的是 temp->setData(100) 应该是 temp->setData(data);
However, I want to focus on this part:
但是，我想重点关注这一部分：
I'm having difficulties wrapping my head around the recursion.
我在递归时遇到了困难。
When you're first introduced to recursion, it can be a little hard to get your mind working that way. We tend to want to think of algorithms as a whole with an ordered list of sequential steps. The best way to get your mind thinking about it is to draw this out. Do it enough and it'll become second nature.
当您第一次接触递归时，让您的大脑以这种方式工作可能有点困难。我们倾向于将算法视为一个具有顺序步骤的有序列表的整体。让你的头脑思考它的最好方法是把它画出来。做得足够多，它就会成为第二天性。
Let's consider Péter's example (ignoring the one slight omission of correcting the setData line). We only have two very simple situations:
让我们考虑 Péter 的例子（忽略纠正 setData 行的一个轻微遗漏）。我们只有两种非常简单的情况：
1) We're calling insert on a node that exists.In this case, we compare the value we are inserting to the value of the node. If it's greater than the node value, we insert to the right child, otherwise to the left. Now you just repeat the process on the child to which you are inserting.
1）我们在存在的节点上调用插入。在这种情况下，我们将插入的值与节点的值进行比较。如果它大于节点值，我们插入到右孩子，否则到左边。现在，您只需在要插入的子节点上重复该过程。
2) We're calling insert on a node that doesn't exist.In this case, we create the node and set its value to the insertion value. The end: recursion is finished. This is called the base case or general solution because it is where we stop.
2）我们在一个不存在的节点上调用插入。在这种情况下，我们创建节点并将其值设置为插入值。结束：递归结束。这被称为基本情况或一般解决方案，因为这是我们停止的地方。
That's it - it's actually quite simple. The trick is not to think about what's happening to the tree as a whole, but just one node at a time, and consider all the cases with that one given node. When you can get your mind thinking this way, we find there's only two cases (three if you want to be pedantic, but two general situations).
就是这样 - 它实际上很简单。诀窍不是考虑整个树发生了什么，而一次只考虑一个节点，并考虑该给定节点的所有情况。当你可以这样思考时，我们发现只有两种情况（如果你想学究，三种情况，但两种一般情况）。
