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

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

当我调用main中的函数时，看起来它没有链接新节点

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 将具有修改您用来调用该函数的指针的效果，并将承受插入的持久影响。