c++ - 在 C++ 中将节点附加到树(引用和指针帮助。)

Question

我正在为类编写平衡二叉树，但我对如何在 C++ 中使用指针和引用(直接来自 Java)感到困惑。下面的代码导致段错误，因为实际上没有节点被添加到树中，curr 刚刚被切换到新的 Node。我将如何着手使新的 Node 到达 curr 在树上指向的位置，而不是仅仅重新分配 curr？

void BalancedTree::insert(int input)
{
    cout << "Insert started\n"; //DEBUG
    Node* trailingNode;
    Node* curr;

    curr = this->root;

    while(curr != NULL){
        cout << "Addloop\n";    //Debug
        if(input < curr->data){     //input smaller than current
            cout << "Left\n"; //DEBUG
            trailingNode = curr;
            curr = curr->left;
        }else{                      //input larger than current node
            cout << "Right\n"; //DEBUG
            trailingNode = curr;
            curr = curr->right;
        }
    }   

    insert(curr, input);
    cout << "test" << endl; 
    cout << root->data << " added\n";   //DEBUG
//  curr->parent = trailingNode;    //Set the parent

    size++;                         //Increase size
}

//Helper method
void BalancedTree::insert(Node*& curr, int input)
{
    curr = new Node(input);
}

Answer 1

如果我们有以下树并尝试插入值 3:

             2
            / \
       1 <--   --> 4
      / \         / \
     N   N       N   N

(N is NULL) 在 while 循环完成后:

• trailingNode 指向值为 4
的 Node
• curr 为NULL(Node 的左分支，值为4)

然后 insert() 将一个新的 Node 分配给 curr 但永远不会将其附加到 Node 的左分支code> 的值为 4。

要附加，您可以更改对 insert() 的调用:

insert(input < trailingNode->data ?
           trailingNode->left :
           trailingNode->right,
       input);

您需要处理树为空的情况。还有其他方法可以实现这一目标，但希望这会为您指明正确的方向。