

このサイトでの質問は初めてです。質問文に分かりにくい部分がありましたら、申し訳ありません。  
C++で二分木探索を作ろうとしています。デバックをしたところ、  
「class cell *insert2」の else if 以降でsegmentation faultが出てしまいました。  
質問にお答え頂けると助かります！

[code]

    #include<iostream>
    #include<cstring>
    using namespace std;
    
    
    template<typename T>class table {
      class cell{
        public:
        const char *key;
        const T binding;
        cell * left;
        cell * right;
        cell(char *k, T v) : key(k), binding(v),left(NULL),right(NULL) {}
      };
      public:
    
      class cell *root;
    
      /* 新しいnodeの製作 */
    
      /* operator() の定義 */
      void operator()(char *key){
        if(search(root,key) == NULL){
            cout << "あります。" << endl;       
        }else{
            cout << "ありません。" << endl;
        }
        return;
      }
    
    /* insertの定義 */
    /*１個のオーバーロード*/
      void insert(char *key, T binding){
        root = insert2(root,key,binding);
        return;
      }
        
    /* operator -= の定義 */
      void operator-=(char *key){
        if(search(root,key) == NULL){
            cout << "存在しません。" << endl;
        }else{
            root = dele(root,key);
        }
        return;
      }
    
    /*表示*/
      void print(int indent){
        print_tree(root,indent);
        return;
      }
    
      private:
      class cell *make_node (char* key, T binding, class cell *left, class cell *right) {
      class cell *new_node;
      new_node = new cell(key,binding);
      new_node->left = left;
      new_node->right = right;
      return new_node;
      }
    
    /*１個のオーバーロード*/
      class cell *insert2(class cell * tree, char* key, T binding) {
      if (tree == NULL){ tree = make_node(key, binding, NULL, NULL);}
      else if (strcmp(tree->key, key) > 0){ tree->left = insert2(tree->left, key, binding);}
      else if (strcmp(tree->key, key) < 0){ tree->right = insert2(tree->right, key, binding);}
    
      return tree;
      }
    
      class cell *search(class cell * tree, char* key) {
      if (tree == NULL) return NULL;
      else if (strcmp(tree->key, key) > 0) return search(tree->left, key);
      else if (strcmp(tree->key, key) < 0) return search(tree->right, key);
      else return tree;
      }
    
      class cell *dele(class cell * tree, char* key) {
      class cell *p, *c;
    
      if (tree == NULL) return NULL;
      else if (strcmp(tree->key, key) > 0) {
        tree->left = dele(tree->left, key);
        return tree;
      }
      else if (strcmp(tree->key, key) < 0) {
        tree->right = dele(tree->right, key);
        return tree;
      }
      else {
        if (tree->left == NULL) return tree->right;
        if (tree->right == NULL) return tree->left;
        for ( p = tree, c = tree->right; c->left != NULL; p = c, c = c->left);
        if (p == tree) 
          p->right = c->right;
        else
          p->left = c->right;
        c->left = tree->left;
        c->right = tree->right;
        free(tree);
        return c;
      }
      }
    
      void print_tree(class cell *tree, int indent) {
      int i;
    
      if (tree == NULL) return;
      for(i = 0; i < indent; i++) 
      cout<< "\t" ;
      cout <<"+" << tree->key <<":" << tree->binding <<endl;
      print_tree(tree->left, indent+1);
      print_tree(tree->right, indent+1);
      }
      
    };
    
    int main() {
      table<int>table1;
        struct cell *root = NULL;
    
    
      table1.insert("akashi", 65);
      table1.insert("watanabe", 70);
      table1.insert("tomizawa", 80);
      table1.insert("tahata", 55);
      table1.insert("takimoto", 90);
      table1.insert("Miyamoto", 80);
      table1.insert("iriyama", 60);
      table1.insert("katsurada", 40);
      table1.insert("noguchi", 40);
      table1.insert("sato", 95);
      table1.insert("matsuzawa", 20);
      table1.print(0);
      table1("tahata");
      table1-=("tahata");
      table1.print(0);
      table1("tahata");
    }
    
[/code]


CC BY-SA 4.0
2022-07-05T16:27:54.230
89779
2022-07-06T00:24:01.790
2022-07-05T16:40:29.763
3060
53380
question
c++
C++ で二分木探索のコード作成中にsegmentation faultが出てしまいます。


質問としては「何故segmentation
faultが出る(発生する)のか教えて欲しい」とか、「何処をどう修正すれば良いのか教えて欲しい」と言ったところでしょうか？

以下のような感じに最初の`table1.insert(...)`を呼び出した先でエラーが発生していますね。

[code]

    int main() {
      table<int>table1;
        struct cell *root = NULL;
    
      table1.insert("akashi", 65);
    
[/code]

↓

[code]

    template<typename T>class table {
    ...
      class cell *root;
    ...
    /* insertの定義 */
    /*１個のオーバーロード*/
      void insert(char *key, T binding){
        root = insert2(root,key,binding);
        return;
      }
    
[/code]

↓

[code]

    /*１個のオーバーロード*/
      class cell *insert2(class cell * tree, char* key, T binding) {
      if (tree == NULL){ tree = make_node(key, binding, NULL, NULL);}
      else if (strcmp(tree->key, key) > 0){ tree->left = insert2(tree->left, key, binding);}  // ←ここでエラー
      else if (strcmp(tree->key, key) < 0){ tree->right = insert2(tree->right, key, binding);}
    
      return tree;
      }
    
[/code]

デバッガで実行したとしても、単にエラーが発生したことだけを見ているのでは、観察眼が不足していると言えるでしょう。  
デバッガ上で何へのアクセスでsegmentation faultが発生したのか表示されているか、あるいはエラーが発生して停止した時点で調査が出来るはずです。

現象としてはこの時点でパラメータとして渡されたtree(ポインタ)の値が異常で、そこにアクセスしようとしてエラーになっています。  
そしてtreeパラメータには呼び出し元でrootが指定されていて、それは良く見ると1度も初期化されていないことが分かります。

もしかしたら`int main()`の2行目`struct cell *root =
NULL;`で初期化のつもりだったのかもしれませんが、これでは`table<int>table1;`とは何の関係も無い変数を定義して初期化しているだけです。  
この行の位置で記述するなら、`table1.root = NULL;`となるでしょう。

より良いのは、`template<typename T>class table {...}`にコンストラクタを定義して、その中で`class cell
*root;`に`NULL`を設定することのはずです。


CC BY-SA 4.0
2022-07-06T00:24:01.790
89780
2022-07-06T00:24:01.790
26370
89779
answer