C++でツリーにノードをアタッチする（参照とポインタのヘルプ）

Question

私はクラスのためのバランシングバイナリツリーを作成していますが、C++でポインターと参照を使う方法について混乱しています。ツリーに実際にノードが追加されていないため、currが新しいNodeに切り替えられただけなので、以下のコードではsegfaultが発生します。新しい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

ダブルポインタで行うことができます。ただ、ここで編集で編集し、 - 私はこれがあなたのためにトリックを行うべきだと思いますが、それを試していない

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

：あなたが変更する必要がある最後のノード参照curが実際に（C++の場合のポイントをする）を参照してください私はいくつかの簡単なコーディングエラーがあった場合、私を許してください。

Node* trailingNode = NULL; 
Node* curr = NULL; 

2）明示的にwhileループにNULLをチェックする必要はありません：insert(curr, input)への呼び出しは、常にで呼び出され

while(curr){ 

3）

Answer 2

1）はNULLへのポインタを初期化しますNULLポインタ！そして、たとえそれがNULLでないとしても、ポインタはまだそれを取り出したノードとの関係がない通常のポインタです。それを参照しても問題は解決しません。代わりに、新しいノードを作成し、trailingNodeの左または右のいずれかに割り当て、f.eする必要があります。：

if (!curr->right) { 
    curr->right = new Node (input); 
    break; // exit while 
} 

Answer 3

ポインタは、Javaでの参照またはint型に似た値の型、です。

参照によって変数を渡すと、その変数のエイリアスが作成されるため、関数内の値を変更できます。 insert(curr, input);を実行すると、ポインタ変数currの値が変更され、新しく作成されたノードをポイントします。

Node curr; 

if([...]) { 
    [...] 
    curr = curr.left; 
} 
else { 
    [...] 
    curr=curr.right; 
} 
[...] 
curr = new Node(); 

これで実際には何もツリーに挿入されないことがわかりました。ここで、同じ値（同じオブジェクトを指す）をそのメンバと同じにする代わりに、実際にleftまたはrightというノードのメンバを示す変数を使用するには、メンバ（フィールド）自体へのポインタが必要です - メンバーが 'Nodeへのポインタ'型であるため、メンバへのポインタは（Nodeへのポインタ）、またはC++表記Node**のポインタでなければなりません。

ここで、関数への 'ポインタへのポインタ'を渡すと、参照されたleftまたはrightメンバの値を変更することができます。これは、currの値を変更する必要がないことを意味します（したがって、参照として渡します）。同じleftまたはrightメンバー（またはBalancedTreeオブジェクトのrootメンバー）を指します。値は新しく作成された要素を指すように変更されます。

Answer 4

我々は、以下のツリーを持っており、値3挿入しようとする場合：掲載さwhileループが完了した後に（NがNULLある）

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

を：

• trailingNodeを指していますNode値あり4
• currはNULL（th ）値4で

をNodeの枝を残した電子は、insert()はcurrに新しいNodeを割り当てますが、値4とNodeの左側の枝にそれを付けることはありません。

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

あなたは木が空のときにケースを処理する必要があります：あなたはinsert()への呼び出しを変更することができます添付する

。これが達成できる他の方法がありますが、うまくいけばポイントあなたは正しい方向になります。