C++使用指针的段错误二叉树

Question

我想出了我的二叉树实现，它确保特定级别中的所有可填充位置都被填充(即在进入下一个级别之前，级别 k 的节点数必须为 2^k)。不幸的是我遇到了段错误。

#include <iostream>
#include <math.h>
#define ll long long int
using namespace std;

struct node
{
  int value=0;
  node* left=NULL;
  node* right=NULL;
  int height=0;
  int numnodes();

  node()
  {
  }

   node(int val,node* l=NULL,node* r=NULL) : value(val),left(l),right(r)
 {}


 int getheight();

 node* operator=(node* n)
 {
  this->value=n->value;
  this->right=n->right;
  this->left=n->left;


  }
  }*binrooter;

   int node::numnodes()
   {

   if(this->left==NULL && this->right==NULL)
   return 0;

   return this->left->numnodes()+this->right->numnodes()+1;

   }

   int node::getheight()
   {
    return max(this->left->getheight(),this->right->getheight())+1;
   }



 node* insertbintree(node* binrooter,ll num)
{

 if(binrooter==NULL)
 return new node(num);

 if(binrooter->value==num)
 return NULL;

 if(binrooter->left==NULL)
 {
  cout<<"Inserting left"<<endl;
  binrooter->left=new node(num);
  }
 else
 if(binrooter->right==NULL)
 {
  cout<<"Inserting right"<<endl;
  binrooter->right=new node(num);
  }
  else
  {
  int k=binrooter->getheight();
  int numchild=pow(2,k);
  if(binrooter->numnodes()==numchild-1)
  numchild=pow(2,k+1);      

  if(binrooter->left->numnodes()>numchild/2)
  {
   cout<<"Traversing right"<<endl;
   binrooter->right=insertbintree(binrooter->right,num);
   }
   else
  {
   cout<<"Traversing left"<<endl;
   binrooter->left=insertbintree(binrooter->left,num);
   }
   }

   return binrooter;

   }


   void insertbintree(ll num)
 { 

  binrooter=insertbintree(binrooter,num);

 }




  void print(node *root)
{
 if(root!=NULL)
{
 print(root->left);
 cout<<root->value<<" ";
 print(root->right);
}
}



 int main()
   {
   ll num=0;
  do
   {
  cout<<endl<<"Enter the element to be inserted or enter -1"<<endl;
  cin>>num;
  if(num==-1)
 {
  break;
 }
  insertbintree(num);

 }
 while(num!=-1);

 cout<<"printing tree in sorted order"<<endl;
 print(rooter);

}

问题是，如果我尝试插入 3 个以上的节点，则会出现段错误。我有点发现错误出在使用 getheight() 插入左子树或右子树的某个地方，但我无法准确指出错误

Answer 1

您的 getheight 函数是递归的。你已经给了它没有停止的情况。它将沿着树递归，直到遇到空值。

在进行递归调用之前，您必须针对 !null 测试 this->left && this->right