无法在二叉树中插入新节点

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;
}

当我在主函数中调用函数时，它似乎没有link新节点

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。一旦您 return 退出函数，它的值就会消失。它不会更新您用来调用函数的指针。所以你的树的根仍然是 NULL （或最后一个节点的 left/right 指针）。

为了获得您期望的效果（即您的 p 分配更新根指针或指向最后一个节点的 left/right 的指针），您需要将签名更改为：

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

这将通过引用传递指针 p。修改 p 将具有修改您用来调用该函数的指针的效果，并将承受插入的持久影响。

无法在二叉树中插入新节点

Can't insert a new node in the binary tree

c++

tree

binary-tree