Изменение корневого указателя двоичного дерева поиска

Question

Я изучал двоичные деревья. И я нашел этот код для вставки узла в дерево. Здесь «root» - это указательная переменная типа структуры в классе «TreeType» как «частный член».

В этой функции «корень» передается по ссылке, поэтому в функции «Вставить» любые изменения в «дереве» также приводят к изменению «корня». Если снова вызвать функцию «Вставить», корень будет указывать на последний узел или он укажет на первый узел? Итак, по моему мнению, поскольку он будет указывать на последний узел, функция вставки больше не будет работать. Может ли кто-нибудь помочь в этом?

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

Единственный корень времени получает изменилось, если дерево пусто, так что это будет по-прежнему указывают на «первый узел» есть такая существует в первую очередь. Во всех остальных случаях «корень», который изменяется, является либо левым, либо правым дочерним указателем узла.

Answer 2

Код вставки может быть лучше проиллюстрировать следующим кодом, который раскладывает проблему в трех случаях:

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. Затем будет создан корень, и поскольку указатель передается по ссылке, это означает, что корневой узел будет создан в куче и возвращен из функции. Новое значение корневого указателя будет передано вызывающему через ссылку. Таким образом, значение корневого указателя останется в памяти кучи. По мере последующего построения дерева все дочерние узлы будут построены впоследствии, не затрагивая корневой узел.