バイナリツリーのサンプル実装が多数の値に対して機能しない

Question

最近バイナリツリーを実装しようとしていますが、1000未満の値で動作するようですが、その後はスタックオーバーフローエラーが発生します

例えば

#include<iostream> 
#include<math.h> 

using namespace std; 
struct Node{ 
    long long int val; 
    Node *left; 
    Node *right; 
}; 
struct BinaryTree{ 
    Node *head = (Node*) malloc(sizeof(Node)); 
    bool headSet = false; 
    Node* findLast(Node *asgn,int val){ 
     if (val > asgn->val){ 
      if (asgn->right != NULL) 
       asgn = findLast(asgn->right, val); 
      else 
       return asgn; 
     } 
     else{ 
      if (asgn->left != NULL) 
       asgn = findLast(asgn->left, val); 
      else 
       return asgn; 
     } 
     return asgn; 
    } 
    void insert(long long int vals){ 
     if (headSet){ 
      Node *asgn = (Node*) malloc(sizeof(Node)); 
      asgn = findLast(head,vals); 
      Node *fix = (Node*)malloc(sizeof(Node)); 
      fix->val = vals; 
      fix->left = NULL; 
      fix->right = NULL; 
      if (vals > asgn->val){ 
       asgn->right = fix; 
       asgn->left = NULL; 
      } 
      else{ 
       asgn->right = NULL; 
       asgn->left = fix; 
      } 
     } 
     else{ 
      head->val = vals; 
      head->right = NULL; 
      head->left = NULL; 
      headSet = true; 
     } 
    } 
}; 
int main(){ 
    BinaryTree a; 
    for (long long int i = 0; i < 100;i++) 
    a.insert(i); 

    return 0; 
} 

： - 私は

for (long long int i = 0; i < 100;i++) 
    a.insert(i); 

for (long long int i = 0; i < 10000;i++) 
    a.insert(i); 

に変更した場合それは私にエラーを与える。私はスタックがオーバーフローするところで、なぜこれが起こっているのか分かりません。

Answer 1

スタックオーバーフローは、findLastメソッドから発生します。バイナリツリーが大きすぎると、再帰が非常に多くなり、コールスタックが1ポイントオーバーフローします。検索に関する情報を何らかの構造体に格納し、スタックがいっぱいにならないように動的に割り当てて、非再帰的メソッドに変換する必要があります。

P.Cでは、mallocの代わりにmallocをC++に、deleteを使用して割り当てられたメモリをクリアすると、現在メモリがリークしています。

Answer 2

反復バージョン：

Node* findLast(Node *asgn,int val){ 
    while (1) 
    { 
    if (val > asgn->val) { 
     if (asgn->right != NULL) 
     asgn = asgn->right; 
     else 
     return asgn; 
    } 
    else { 
     if (asgn->left != NULL) 
     asgn = asgn->left; 
     else 
     return asgn; 
    } 
    } 
} 

簡単には、そうではありませんか？

そしてinsertの修正バージョンは：

void insert(long long int vals){ 
    if (headSet){ 
     // Node *asgn = (Node*) malloc(sizeof(Node)); // removed 
     Node *asgn = findLast(head,vals);    // line changed slighty 
     Node *fix = (Node*)malloc(sizeof(Node)); 
     fix->val = vals; 
     fix->left = NULL; 
     fix->right = NULL; 

     if (vals > asgn->val){ 
      asgn->right = fix; 
      //asgn->left = NULL;  // removed 
     } 
     else{ 
      //asgn->right = NULL;  // removed 
      asgn->left = fix; 
     } 
    } 
    else{ 
     head->val = vals; 
     head->right = NULL; 
     head->left = NULL; 
     headSet = true; 
    } 
} 

Answer 3

これは、次のような答えではありません。私はちょうどマイケル・ワルツの修正を元のコードの補遺としてコードの変更を提案したい。

struct BinaryTree{ 
    Node *head = (Node *)NULL; 
    Node* findLast(Node *asgn,int val){ // Courtesy of Michael Walz 
     while (1){ 
      if (val > asgn->val){ 
       if (asgn->right != NULL) 
        asgn = asgn->right; 
       else 
        return asgn; 
      } 
      else{ 
       if (asgn->left != NULL) 
        asgn = asgn->left; 
       else 
        return asgn; 
      } 
     } 
    } 
    void insert(long long int vals){ 
     Node *fix = (Node*)malloc(sizeof(Node)); 
     fix->val = vals; 
     fix->left = NULL; 
     fix->right = NULL; 
     if (head != NULL){ 
      Node *asgn = findLast(head,vals); 
      if (vals > asgn->val){ 
       asgn->right = fix; 
      } 
      else{ 
       asgn->left = fix; 
      } 
     } 
     else{ 
      head = fix; 
     } 
    } 
}