更改二叉搜索树的根指针

Question

我在研究二叉树。我找到了在树中插入节点的代码。这里“root”是类“TreeType”中结构类型的指针变量，作为“private member”。

在这个函数中，“根”是通过引用传递的，所以在“插入”函数中，“树”中的任何变化也会导致“根”的变化。如果我们再次调用插入函数，根将指向最后一个节点还是指向第一个节点？所以，根据我的说法，当它指向最后一个节点时，插入函数将不再工作。有人能帮忙吗？

void Insert(TreeNode*& tree, ItemType item);

void TreeType::InsertItem(ItemType item)
// Calls the recursive function Insert to insert item into tree.
{
Insert(root, item);
}
void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post: item is in tree; search property is maintained.
{
if (tree == NULL)
{// Insertion place found.
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item); // Insert in left subtree.
else
Insert(tree->right, item); // Insert in right subtree.
}

Answer 1

下面的代码可以更好地说明插入代码，它将问题分解为三种情况：

void Insert(TreeNode*& tree, ItemType item)
{
if (tree == NULL)
{
    // Insertion place found.
    tree = new TreeNode;
    tree->right = NULL;
    tree->left = NULL;
    tree->info = item;
    return;
}

if (item < tree->info) {
    if(tree->left == NULL) {
        tree->left = new TreeNode;
    } else {
        Insert(tree->left, item); // Insert in left subtree.
    }
} else {
    if(tree->right == NULL) {
        tree->right = new TreeNode;
    } else {
        Insert(tree->right, item); // Insert in right subtree.
    }
}
}

如您所见，当树为空时，root=NULL。所以第一次它将进入第一个if子句。然后将创建根指针，由于指针是通过引用传递的，这意味着根节点将在堆上创建并从函数返回。根指针的新值将通过引用传递给调用方。因此根指针值将保留在堆内存中。由于后续树构建正在进行中，所有子节点将在不影响根节点的情况下后续构建。

Answer 2

根唯一被改变的时间是如果树是空的，那么它仍然会指向“第一个节点”，这就是最初存在的节点。在所有其他情况下，正在更改的“根”是节点的左或右子指针。