c - 二叉树 - 插入和镜像之间的区别？

Question

我们在 insert/delete 中做了哪些不在 mirror 中的操作？

mirror 我指的是切换树中每个节点的左右子节点。

我问的原因是，当涉及到 insert 时，如果您不保存函数返回的根，则会导致错误。 mirror 则不同。我假设 mirror 会有相同的要求(返回根节点)，但事实并非如此。这是为什么？

如果相关的话，这是我的代码(insert 是为 BST 实现的):

插入:

Node *insert(Node *root,int val)
{
    Node *newNode=NULL;



    if(root==NULL)
    {
        newNode=(Node*) malloc(sizeof(Node));

        newNode->value=val;
        newNode->left=NULL;
        newNode->right=NULL;
        return newNode;
    }

    if(root->value>val)
    {
        root->left=insert(root->left,val);
    }
    else
    {
        root->right=insert(root->right,val);
    }

    return root;

}

镜子:

void mirror(Node *root)
{
    Node *temp_left;
    if(root==NULL)
        return;

    temp_left=root->left;
    root->left=root->right;
    root->right=temp_left;

    mirror(root->left);
    mirror(root->right);

}

Answer 1

注意这行:

root->left=insert(root->left,val);

在这里，您将 insert() 的结果分配给 root->left。你需要 insert() 在这里返回一个 node* 指针，否则我们将不知道 malloc 将新节点放在内存中的什么地方，因此您将无法将节点添加到树中。

另一方面，mirror 只是递归地遍历树并交换一些已经存在的指针。您永远不需要将结果 mirror() 分配给变量。