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

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() 到 return 一个 node* 指针，否则我们将不知道 malloc 将新节点放在内存中的何处，因此您将无法将节点添加到树中。

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

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

Binary Trees - difference between insert and mirror?

c

binary-tree

pointers