Невозможно вставить новый узел в двоичное дерево

Question

Я считаю, что моя функция вставки правильная, но похоже, что новый узел не вставлен в дерево. Я не мог понять, где ошибка. Я ценю любую помощь, спасибо.

Существует декларация узла и дерева:

class Node{ 
    int key; 
    Node *right, *left; 
} 

class Tree{ 
public: 
     int init(); 
     Node *root; 
     Node *insert(int key, Node *p); 
}; 

есть функции:

int Tree::init(){ 
    this->root = NULL; return 1; 
} 

Node *Tree::insert(int key, Node *p){ 
    if(p == NULL){ 
    Node *novo = new Node(); 
    novo->key = key; 
    novo->left = NULL; 
    novo->right = NULL; 
    p = novo; 
    } 
    else if(key < p->key){ p->left = insert(key, p->left); } 
    else if(key > p->key){ p->right = insert(key, p->right); } 
    else{ cout << "Error: key already exist" << endl; } 

return p; 
} 

Когда я вызываю функцию в основном, это выглядит, как он не связывает новый Узел

int main() { 
    Tree dictionary; 

    cout << "enter the key"; cin >> key; 

    dictionary.insert(key, dictionary.root); 

    cout << dictionary.root->key; 
} 

Answer 1

В вашей функции insert(), когда дерево пуст или вы достигли последнего узла, вы создаете т.е новый узел:

if(p == NULL){ 
    Node *novo = new Node(); 
    novo->key = key; 
    novo->left = NULL; 
    novo->right = NULL; 
    p = novo;    // ouch !!!! 
    } 

К сожалению, заявление p=novo только обновляет локальный параметр p вашей функции. Его значение исчезнет, ​​как только вы вернетесь из функции. Он не будет обновлять указатель, который вы назвали своей функцией. Таким образом, корень вашего дерева остается NULL (или указатель слева/справа последнего узла).

Чтобы получить эффект, который вы ожидаете (т.е. вашего p распайки обновляет указатель корневого или указатель влево/вправо от последнего узла), вы должны изменить подпись:

Node *insert(int key, Node *& p); // p is passed by reference 

Это будет передать указатель p по ссылке. Затем изменение p будет иметь эффект изменения указателя, который вы использовали для вызова функции, и выдержит длительный эффект вставки.