我正在解决二叉树中节点插入的问题。我有以下疑问:
1) 如果我们要插入一个节点,那么我们应该返回一个指向该节点的指针,因为只有这样我们才能访问该节点,对吧?
2) 那我们为什么要返回 root?我们必须相应地返回 root->left
或 root->right
,我哪里错了?
struct node* insert(struct node* root, int data)
{
if (root == NULL) //If the tree is empty, return a new,single node
return newNode(data);
else
{
//Otherwise, recur down the tree
if (data <= root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
}
3) 上面的代码返回的是由于递归而从之前的根改变的根吗?
最佳答案
你误解了返回值。
此insert
函数的返回值是指向现在已将data
插入其中的子树的指针。如果传入的root
为null,则这是一棵新的1节点树;如果传入的root
不为空,则返回值与root
相同。
这使得递归更简单一些。我们简单地递归,直到我们在分支中迎面遇到 nullptr
。然后递归停止,返回值设置父节点的 left
或 right
节点。
要创建一个全新的树,您可以输入:
node* new_tree = insert(nullptr, 7);
将某些内容插入您键入的现有树中:
existing_tree = insert(existing_tree, 7);
或等效
insert(existing_tree, 7);
只要 existing_tree
不为空。
函数的这种“双重使用”(同时创建和修改树)可能会造成混淆,但它使特定的递归使用稍微不那么冗长,并使“空树是 nullptr”和“总是做 existing_tree = insert(existing_tree, val);
”是使空树作为空树起作用的规则。
但是,这是一种非常 C 的做事方式。
更多c++做事的方式是:
std::unique_ptr<node> insert(std::unique_ptr<node> root, int data)
{
if (root == nullptr) //If the tree is empty, return a new,single node
return std::make_unique<node>(data);
else
{
//Otherwise, recur down the tree
if (data <= root->data)
root->left = insert(std::move(root->left), data);
else
root->right = insert(std::move(root->right), data);
return std::move(root);
}
}
数据流入和流出函数的地方更明确,我们假设 node
有一个接受 data
的构造函数。
关于c++ - 指向二叉树中新节点的指针,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52698131/