c++ - 指向二叉树中新节点的指针

Question

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

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) 上面的代码返回的是由于递归而从之前的根改变的根吗？

Answer 1

你误解了返回值。

此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 的构造函数。