先行ノードと後継ノードの検索

Question

私はバイナリ検索ツリー内に後継ノードと先行ノードを取得する方法がありますが、私のコードでそのバグを見つけるのに問題があります。次のキーを持つノードを追加します："C"、"B"、および"K"。私は、バイナリ検索ツリーの内容を印刷する場合、私は次のような出力が得られます。

"C" "some data 1" 
"B" "some data 2" 
"K" "some data 3" 

私は"B"を追加すると、それは明らかに何の先行または後続を持っていないので、私はちょうど空の文字列にそれらの設定：

root = root->insert(root, key, data); 
    root->getNextAndPrev(root, prev, next, key); 
    string p; 
    string n; 
    if (!prev) { 
     pred = ""; 
    } 
    else { 
     pred = prev->getKey(); 
    } 
    if (!next) { 
     succ = ""; 
    } 
    else { 
     succ = next->getKey(); 
    } 

    return new Entry(data, succ, pred); 

を

"B"を追加すると、"B"の後継者が"C"で、前任者が期待通りに""であるという出力が得られます。しかし、ツリーに"K"を追加すると、"K"の前身は"C"で、後継者も"C"という出力が得られます。なぜ私は何か後継者がないかどうかを確認するためにチェックしているので、なぜこのエラーが出るのか分かりません（何も来ていません。"K"）空の文字列に設定してください。

マイNodeクラスはinsert()とgetNextAndPrev()メソッドを処理し、ここで私はそれらを実装してきた方法です：

void Node::getNextAndPrev(Node* root, string key) { 
if (!root) return; 

if (root->key == key){ 

    if (root->left != NULL){ 

     Node* tempNode = root->left; 

     while (tempNode->right != NULL) { 
      tempNode = tempNode->right; 
     } 
     prev= tempNode; 
    } 

    if (root->right != NULL){ 

     Node* tempNode = root->right; 

     while (tempNode->left != NULL) { 
      tempNode = tempNode->left; 
     } 
     next = tempNode; 
    } 

} 
if (root->key > key) { 
    next = root; 
    getNextAndPrev(root->left, key); 
} 
else { 
    prev = root; 
    getNextAndPrev(root->right, key); 
} 

}

それは順不同でいくつかのキーを追加して、私のgetNextAndPrevを引き起こすことがあるのはなぜ間違った値を取得するには？

恐らくそれは私のエントリをどのように私のmainに挿入しているかと関係があります。私は次のように設定したループを持っている：

string command = ""; 
Entry* entry = new Entry("","",""); 
string def = ""; 
while (true) { 
    cout << "Enter command: "; 
    getline(cin, command); 
    if (parseCommand(command, "ADD") == 0) { 
     string tempCmd = processCommand(command, 3); 
     string key = tempCmd.substr(0, tempCmd.length() - 4); 
     string data = tempCmd.substr(tempCmd.length() - 4); 
     trim(key); 
     trim(data); 
     def = data; 
     entry = dict->modify(key, data); 
     cout << "added: " << key << " with definition of : " << def << " to the dictionary " << endl; 
    } 

modify()が私のDictionaryクラス内そうのように呼び出されます：

Entry * Dictionary::modify(string key, string data) { 
    Entry * entry = new Entry("","",""); 
    if (root) entry = search(key); 
    //inserting something into the dictionary 
    if (data != "" && !this->root->doesContain(this->root, key)) { 
    root = root->insert(root, key, data); 
    return entry; 
    } 
} 

そして最後に、modify()内部で呼び出される私のsearch()方法：

Entry * Dictionary::search(string key) { 
     if (key == "") { 
     return new Entry("", getSmallestKey(), getLargestKey()); 
     } 

     if (!this->root->doesContain(root, key)) { 
     root->getNextAndPrev(root, key); 
     string prev; 
     string next; 
     if (root->getPrevNode() != NULL) { 
      prev = root->getPrevious(); 
      cout << "Predecessor is " << prev << " root is: " << root->getKey() << endl; 
     } 
     else { 
      prev = ""; 
      cout << "No Predecessor" << endl; 
     } 

     if (root->getNextNode() != NULL) { 
      next = root->getNext(); 
      cout << "Successor is " << next << " root is: " << root->getKey() << endl; 
     } 
     else { 
      next = ""; 
      cout << "No Successor" << endl; 
     } 
     if (next == prev) { 
      if (next < key) { 
      next = ""; 
      } 
      if (prev > key) { 
      prev = ""; 
      } 
     } 
    return new Entry("", next, prev); 
} 

問題を詳細に説明するために、上記の実行結果を以下に示します。

Enter command: ADD "FOO" "D" lookup stuff: root: prev: next: // gets logged out when I insert into dictionary added: "FOO" with a definition of: "D" to the dictionary Enter command: ADD "BIN" "C" No Predecessor Successor is "FOO" root is: "FOO" lookup stuff: root: prev: next: "FOO" added: "BIN" with a definition of: "C" to the dictionary Enter command: ADD "QUUX" "D" Predecessor is "FOO" root is: "FOO" Successor is "FOO" root is: "FOO" lookup stuff: root: prev: "FOO" next: added: "QUUX" with a definition of: "D" to the dictionary Enter command: ADD "BAZ" "N" Predecessor is "FOO" root is: "FOO" Successor is "BIN" root is: "FOO" lookup stuff: root: prev: "FOO" next: "BIN" added: "BAZ" with a definition of: "N" to the dictionary

辞書にBAZを追加するとき、前任者と後継者が場違い今、なぜ私が理解することはできません。

Enter command: ADD "BAZ" "N" Predecessor is "FOO" root is: "FOO" Successor is "BIN" root is: "FOO"

Answer 1

私はあなたのノードのコンストラクタ

new Node(key, d) 

を願っています

は、leftフィールドとrightフィールドをNULLに設定します。

successorとpredecessorインオーダートラバーサルサクセサと先行機を意味すると思います。あなたのコードは私にとってまったくいいと思われます。

唯一の可能性は、共通変数prevと次のを使って、前身と後継者を得ることです。したがって、異なるノードに異なる変数を使用してみてください。

Node *prevK,*nextK; 

をし、これらの変数を持つ関数を呼び出すgetNextAndPrev()：あなたはノードBのための後継者とpredecssorを得て行われた後

、新しい変数を定義します。