首页 文章

为什么这个移植函数适用于二叉搜索树？

提问于
浏览 次
0

在CLRS中的二叉搜索树章节中，我遇到了移植函数，它将节点 u 替换为节点 v ，并在父元素中进行了适当的更改 . 这是我为移植功能编写的代码：

void transplant(Node* root, Node* u, Node* v)
{
    if(u->parent == NULL)
        root = v;
    else if(u == u->parent->left)
        u->parent->left = v;
    else
        u->parent->right = v;
    if(v != NULL)
        v->parent = u->parent;
}

它's not that I don'了解这是如何工作的，但这就是为什么这样做 . 当我进行函数调用时，我基本上是向函数发送指针 root ， u ， v 的副本？所以函数中所做的更改实际上不应该反映在root上，除非我返回它或使用指针指针类型，但它实际上改变了原始根 . 我将root定义为全局变量，这会改变什么吗？

c binary-search-tree

1 回答

  • 0

    如果 u->parent 是 NULL ，则该函数将不起作用，在这种情况下，只有局部变量 root 设置为 v ，函数外部无法访问任何内容 .

    如果 u->parent != NULL ，则 u->parent->left 和 u->parent->right 是 u->parent 指向的 Node 的成员，并且这些成员将被覆盖，因此更改在 main 中可见 .

    回复于

相关问题