ランダムなノードを作成するバイナリツリークラス

Question

私は抽象的なディクショナリクラスから継承するクラスとしてテンプレートバイナリツリーディクショナリを実装しています。私が理解できない追加機能に問題があります。

基本的に私のツリーには、キーと値の両方を持つノードとその親、左の子、および右の子へのポインタがあります。ノードのためのコードが

struct bNode { 
    K key; 
    V value; 
    bNode* left; 
    bNode* right; 
    bNode* parent; 
}; 

（私が知っているのshared_ptrを使用すると、生のポインタよりも良いですが、それがこのプロジェクトのために必要ではなかった） ある木もメンバーポインタbNode* rootを持っています。

ツリーをテストするために、ツリーに要素を追加し、それぞれの後にdisplayを呼び出します。これまでのところ、空のリストを表示すると、1つの要素と2つの要素を持つリストを表示するのと同様に、正しく動作します。しかし 私は第三の追加、および表示を呼び出し、それが壊れる...

ここで追加機能のためのコード

void add(K key, V value) override { 
    // if list is empty, create new root node 
    if (!root){ 
     root = new bNode; 
     root->key = key; 
     root->value = value; 
     return; 
    } 
    bNode* node = root; 
    // travel down tree, checking each node on the way 
    while (true){ 
     // if node exists with passed-in key, change value to passed-in value 
     if (node->key == key){ 
      node->value = value; 
      return; 
     } 
     // if key <or> node and node has a left/right child, travel left/right branch 
     // if node doesn't have a left/right child, create one and pass in key 
     if (key < node->key){ 
      if (node->left){ 
       node = node->left; 
      } else { 
       node->left = new bNode; 
       node->left->parent = node; 
       node->left->key = key; 
       node->left->value = value; 
       return; 
      } 
     } else { 
      if (node->right){ 
       node = node->right; 
      } else { 
       node->right = new bNode; 
       node->right->parent = node; 
       node->right->key = key; 
       node->right->value = value; 
       return; 
      } 
     } 
    } 
} 

ここに表示が

void display() const override { 
    if (!root){ 
     return; 
    } 
    displayHelper(root); 
    cout << endl; 
} 

、ここ

displayHelperだだです

void displayHelper(bNode* node) const { 
    cout << "(" << node->key << ", " << node->value << ") "; 
    if (node->left){ 
     cout << "displaying left... <" << node->key << "> "; 
     displayHelper(node->left); 
    } 
    if (node->right){ 
     cout << "displaying right... <" << node->key << "> "; 
     displayHelper(node->right); 
    } 
} 

「右に表示する」と「左に表示する」という行関数が別のノードを表示しようとしていない限り、実行しないでください。これは、最初の2つのノードを表示した後、すべて期待どおりに機能しました。しかし、3番目のノードでは、その要素が表示され、 "left < * 3番目のノードのキー> ..."と表示され、クラッシュしてセグメント化エラーが発生します。

私が知る限り、これは何らかの理由でコードが実行されているように、葉ノードであるべき3番目の追加ノードには実際に子があり、その後にメンバー変数を読み込もうとするとクラッシュする存在しないノードの場合

バグの原因を突き止めることはできません。なぜなら、これはすべて非常に単純なコードなのですから！どんな助けでも大歓迎です！

EDIT： ここに問題を示すコードスニペットがあります。

BSTDictionary<string, int> t; 
t.display(); 
t.add("e", 5); 
t.display(); 
t.add("b", 20); 
t.display(); 
t.add("c", 12); 
t.display(); 
return 0; 

実行は、出力が

（E、5）

のように見えるとき（E、5）（B、20）

（（E）...左に表示（c）

プロセスが-1073741819（0xC0000005）の実行を返しました。時間：1.993秒

（c、12）を含むノードの左の子は存在しないはずですが、コンパイラは存在するかのように実行しようとしています。

Answer 1

オブジェクト内のすべてのリーフノードポインタを、すぐに意味のあるものに割り当てる場合を除き、nullptrに初期化する必要があります。