バイナリツリーでは、オーバーフローの原因でスタックオーバーフローが発生する

Question

さて、私は正しく（すべて7000）の値（ツリーの構造として15値を書いています）を読み込み中の読み込みメソッドがあり、エラーは発生しません。

しかし、バイナリツリーの出力に関しては、私はいくつかのウェブサイトに記載されている方法を使用しています。

私はエラーがスタックオーバーフローであり、私は再帰呼び出しのために仮定していると決して壊れていないが、私はなぜこれが動作しないのか分かりません。

ご協力いただきありがとうございます。

以下に記載するコード：

// Read 
void BinaryTreeStorage::read(ifstream& _fin) 
{ 
     // Get first line with number of names in it 
     string numberOfNamesString; 
     getline(_fin, numberOfNamesString); 

     // Loop through all the names 
     string line; 
     int num = 0; 
     while (!_fin.eof()) 
     { 
       getline(_fin, line); 
       if (line != "") 
       { 
         // Insert Value Here 
         if (root != NULL) 
         { 
           insert(line, root); 
         } 
         else 
         { 
           insert(line); 
         } 
       } 
     } 
} 

// Write 
void BinaryTreeStorage::write(ofstream& _out) const 
{ 
     inorderPrint(_out, root); 
} 

// inorderPrint 
void BinaryTreeStorage::inorderPrint(ofstream& _out, node *_root) const 
{ 
     if (_root != NULL) 
     { 
       // Inorder 
       inorderPrint(_out, root->left); 
       _out << root->nodeValue; 
       cout << root->nodeValue << " "; 
       inorderPrint(_out, root->right); 
     } 
} 

// Insert if root is null 
void BinaryTreeStorage::insert(string _nodeValueIn) 
{ 
    if(root!=NULL) 
     insert(_nodeValueIn, root); 
    else 
    { 
     root=new node; 
     root->nodeValue=_nodeValueIn; 
     root->left=NULL; 
     root->right=NULL; 
    } 
} 

// Insert when root is not null 
void BinaryTreeStorage::insert(string _nodeValueIn, node *leaf) 
{ 
    if(_nodeValueIn< leaf->nodeValue) 
    { 
     if(leaf->left!=NULL) 
      insert(_nodeValueIn, leaf->left); 
     else 
     { 
      leaf->left=new node; 
      leaf->left->nodeValue=_nodeValueIn; 
      leaf->left->left=NULL; //Sets the left child of the child node to null 
      leaf->left->right=NULL; //Sets the right child of the child node to null 
     } 
    } 
    else if(_nodeValueIn>=leaf->nodeValue) 
    { 
     if(leaf->right!=NULL) 
      insert(_nodeValueIn, leaf->right); 
     else 
     { 
      leaf->right=new node; 
      leaf->right->nodeValue=_nodeValueIn; 
      leaf->right->left=NULL; //Sets the left child of the child node to null 
      leaf->right->right=NULL; //Sets the right child of the child node to null 
     } 
    } 
} 

Answer 1

void BinaryTreeStorage::inorderPrint(ofstream& _out, node *_root) const 
{ 
     if (_root != NULL) 
     { 
       // Inorder 
       inorderPrint(_out, root->left); 

、私は_rootが定義されていますが、あなたの呼び出し（上記の最後の行）にrootを使用している見ることができます。私はそれが無限ループを引き起こしていると思います。

Answer 2

にあなたがあなたのツリーノードを構築し、あなたは左と右のポインタがNULLに初期化されていることを確認しましたか？上記のコードで

Answer 3

コールツリーの深さはinorderPrintで、ツリー自体の深さと同じです。あなたは木のバランスを保つことを試みないように見えるので、深さは木の大きさと同じくらい大きくなることがあります。

これを修正する方法はいくつかあります。ツリーが常にバランスを保っていることを確認して、深さがツリーのサイズと対数的に増加するようにすることができます。または、ノードを繰り返し訪問することができるように、ツリーthreadedを作成することもできます。代わりにルートにあなたは常にループ：

Answer 4

あなたがBinaryTreeStorage :: inorderPrintのバグ、 あなたのparam意図どこが使用されていない_rootを持っています。

ヒント：類似の名前を使用しないでください！

ヒント：入れ子になったテンプレートでstd ::を頻繁に書かない限り、を使用してを使用してバグを回避してください。

ヒント：名前の先頭または末尾に_を使用しないでください。

ヒント：NULLと比較しないでください。if（n！= NULL）ではなくif（n）を記述してください。

ヒント：必要に応じていないときではない巣ブロックを実行します。

void BinaryTreeStorage::inorderPrint(std::ofstream& out, node *n) const 
{ 
    if(!n) return; 

    inorderPrint(out, n->left); 
    out << n->nodeValue; // no separator?? 
    std::cout << n->nodeValue << " "; 
    inorderPrint(out, n->right); 
}