指向二叉树中新节点的指针

Question

我正在解决 在二叉树中插入节点 的问题。我有以下疑惑：

1) 如果我们要插入一个节点，那么我们应该 return 一个指向该节点的指针，因为只有这样我们才能访问该节点，对吗？

2) 那么我们为什么要 return root？必须return root->left or 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) 上面的代码 return 是不是由于递归而与之前的代码发生变化的根？

Answer 1

这个递归插入应该总是return树的根节点。仅仅因为你读到 return root 并不意味着原始函数调用已经执行完毕，它只是意味着第 n 次递归已经完成。递归调用已全部压入堆栈，因此必须在原始调用者收到 returned 值之前全部解析。

您可以通过对插入的值执行 find 返回到插入的节点。

Answer 2

您误解了 return 值。

此 insert 函数的 return 值是指向现在已插入 data 的子树的指针。如果传入的root为null，则这是一棵新的1节点树；如果传入的 root 为非空，则 return 值与 root.

相同

这使得递归更简单一些。我们简单地递归，直到我们运行正面进入分支中的 nullptr 。然后递归停止，return值设置父节点的left或right节点。

要创建一个全新的树，您输入：

node* new_tree = insert(nullptr, 7);

要将内容插入您键入的现有树中：

existing_tree = insert(existing_tree, 7);

或等效

insert(existing_tree, 7);

只要 existing_tree 不为空。

这个 "double use" 函数（创建和修改树）可能会混淆，但它使特定的递归使用不那么冗长，并使 "empty tree is a nullptr" 和 "always do 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.

的构造函数

指向二叉树中新节点的指针

Pointer to a new node in a Binary Tree

c++

binary-tree

binary-search-tree

data-structures

c++11