Segmentation fault appears during code creation for binary tree search in C++.

This is the first time I have asked a question on this site.I am sorry if there is anything difficult to understand in the questionnaire.😔
I'm trying to create a binary tree search in C++.After debacking,
The segmentation fault appears after else if of class cell*insert2.
I would appreciate it if you could answer my question!

#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,Tv): key(k), binding(v), left(NULL), right(NULL){}
  };
  public:

  class cell* root;

  /* Create a new node*/

  /* Define operator()*/
  void operator() (char*key) {
    if(search(root,key)==NULL){
        cout<<"Yes." <<endl;       
    } else {
        cout<<" None." <<endl;
    }
    return;
  }

/* US>Defining insert*/
/* 1 overload*/
  void insert(char*key,T binding) {
    root=insert2(root, key, binding);
    return;
  }
    
/* operator-= definition*/
  void operator-=(char*key){
    if(search(root,key)==NULL){
        cout<<"It does not exist." <<endl;
    } else {
        root=dele(root,key);
    }
    return;
  }

/*View*/
  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;
  }

/* 1 overload*/
  class cell * insert 2 (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)returnNULL;
  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)returnNULL;
  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) {
  inti;

  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;
    structure 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");
}

c++

2022-09-30 19:39

1 Answers

As for the questions, did you say, "Please tell me why the segmentation fault comes out?" or "Please tell me where and how to correct it?"

The error occurred when I called the first table1.insert(...) in the following way:

int main(){
  table<int>table1;
    structure cell*root=NULL;

  table1.insert("akashi", 65);

↓

template<typename T>class table{
...
  class cell* root;
...
/* US>Defining insert*/
/* 1 overload*/
  void insert(char*key,T binding) {
    root=insert2(root, key, binding);
    return;
  }

↓

/* 1 overload*/
  class cell * insert 2 (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);} // ← Error here
  else if(strcmp(tree->key,key)<0) {tree->right=insert2(tree->right,key,binding);}

  return tree;
  }

Even if you run it on a debugger, if you're just looking at the error, you're not very observant.
You should be able to investigate what access on the debugger caused the segmentation fault, or when an error occurs and stops.

The symptom is that the tree (pointer) value passed as a parameter at this time is abnormal, and I am trying to access it with an error.
And the tree parameter specifies root at the caller, which, if you look closely, has never been initialized.

You may have intended to initialize in the second line of intmain(), structure cell*root=NULL;, but this is just defining and initializing variables that have nothing to do with table<int>table1;.
If you write from this line, it should be table1.root=NULL;.

The better way to do this is to define the constructor in template<typename T>class table {...}, where class cell*root; is set to NULL.

2022-09-30 19:39

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656