有沒有人在這個BST代碼中看到是什麼導致了分段錯誤？

Question

#include <iostream> 

using namespace std; 

#define YES 1 
#define NO 0 

class tree 
{ 
    private: 

    public: 
     struct leaf 
     { 
      int data; 
      leaf *l; 
      leaf *r; 
     }; 
     struct leaf *p; 

     tree(); 
     ~tree(); 
     void destruct(leaf *q); 
     tree(tree& a); 
     void findparent(int n,int &found,leaf* &parent); 
     void findfordel(int n,int &found,leaf *&parent,leaf* &x); 
     void add(int n); 
     void transverse(); 
     void in(leaf *q); 
     void pre(leaf *q); 
     void post(leaf *q); 
     void del(int n); 
     leaf* createBST(int *preOrder, int* inOrder, int len); 

}; 

tree::tree() 
{ 
    p=NULL; 
} 

tree::~tree() 
{ 
    destruct(p); 
} 

void tree::destruct(leaf *q) 
{ 
    if(q!=NULL) 
    { 
     destruct(q->l); 
     del(q->data); 
     destruct(q->r); 
    } 
} 
void tree::findparent(int n,int &found,leaf *&parent) 
{ 
    leaf *q; 
    found=NO; 
    parent=NULL; 

    if(p==NULL) 
     return; 

    q=p; 
    while(q!=NULL) 
    { 
     if(q->data==n) 
     { 
      found=YES; 
      return; 
     } 
     if(q->data>n) 
     { 
      parent=q; 
      q=q->l; 
     } 
     else 
     { 
      parent=q; 
      q=q->r; 
     } 
    } 
} 

void tree::add(int n) 
{ 
    int found; 
    leaf *t,*parent; 
    findparent(n,found,parent); 
    if(found==YES) 
     cout<<"\nSuch a Node Exists"; 
    else 
    { 
     t=new leaf; 
     t->data=n; 
     t->l=NULL; 
     t->r=NULL; 

     if(parent==NULL) 
      p=t; 
     else 
      parent->data > n ? parent->l=t : parent->r=t; 
    } 
} 

void tree::transverse() 
{ 
    int c; 
    cout<<"\n1.InOrder\n2.Preorder\n3.Postorder\nChoice: "; 
    cin>>c; 
    switch(c) 
    { 
     case 1: 
      in(p); 
      break; 

     case 2: 
      pre(p); 
      break; 

     case 3: 
      post(p); 
      break; 
    } 
} 

void tree::in(leaf *q) 
{ 
    if(q!=NULL) 
    { 
     in(q->l); 
     cout<<"\t"<<q->data<<endl; 
     in(q->r); 
    } 

} 

void tree::pre(leaf *q) 
{ 
    if(q!=NULL) 
    { 
     cout<<"\t"<<q->data<<endl; 
     pre(q->l); 
     pre(q->r); 
    } 

} 

void tree::post(leaf *q) 
{ 
    if(q!=NULL) 
    { 
     post(q->l); 
     post(q->r); 
     cout<<"\t"<<q->data<<endl; 
    } 

} 

void tree::findfordel(int n,int &found,leaf *&parent,leaf *&x) 
{ 
    leaf *q; 
    found=0; 
    parent=NULL; 
    if(p==NULL) 
     return; 

    q=p; 
    while(q!=NULL) 
    { 
     if(q->data==n) 
     { 
      found=1; 
      x=q; 
      return; 
     } 
     if(q->data>n) 
     { 
      parent=q; 
      q=q->l; 
     } 
     else 
     { 
      parent=q; 
      q=q->r; 
     } 
    } 
} 

void tree::del(int num) 
{ 
    leaf *parent,*x,*xsucc; 
    int found; 

    // If EMPTY TREE 
    if(p==NULL) 
    { 
     cout<<"\nTree is Empty"; 
     return; 
    } 
    parent=x=NULL; 
    findfordel(num,found,parent,x); 
    if(found==0) 
    { 
     cout<<"\nNode to be deleted NOT FOUND"; 
     return; 
    } 

    // If the node to be deleted has 2 leaves 
    if(x->l != NULL && x->r != NULL) 
    { 
     parent=x; 
     xsucc=x->r; 

     while(xsucc->l != NULL) 
     { 
      parent=xsucc; 
      xsucc=xsucc->l; 
     } 
     x->data=xsucc->data; 
     x=xsucc; 
    } 

    // if the node to be deleted has no child 
    if(x->l == NULL && x->r == NULL) 
    { 
     if(parent->r == x) 
      parent->r=NULL; 
     else 
      parent->l=NULL; 

     delete x; 
     return; 
    } 

    // if node has only right leaf 
    if(x->l == NULL && x->r != NULL) 
    { 
     if(parent->l == x) 
      parent->l=x->r; 
     else 
      parent->r=x->r; 

     delete x; 
     return; 
    } 

    // if node to be deleted has only left child 
    if(x->l != NULL && x->r == NULL) 
    { 
     if(parent->l == x) 
      parent->l=x->l; 
     else 
      parent->r=x->l; 

     delete x; 
     return; 
    } 
} 


tree::leaf* tree::createBST(int *preOrder, int* inOrder, int len) 
{ 
    int i; 
    tree::leaf *bst = new tree::leaf; 
// tree bst; 
    if(len < 0) 
     bst = NULL; 
     return bst; 

    bst->data = *preOrder; 
    for(i = 0; i < len; i++) 
     if(*(inOrder + i) == *preOrder) 
     break; 
    bst->l = createBST(preOrder + 1, inOrder, i); 
    bst->r = createBST(preOrder + i +1, inOrder + i + 1, len-i-1); 
    return bst; 

} 

int main() 
{ 
/* tree t; 
    int data[]={32,16,34,1,87,13,7,18,14,19,23,24,41,5,53}; 
    for (int iter=0; iter<15; iter++) 
    { 
     t.add(data[iter]); 
    } 
    t.transverse(); 
    t.del(16); 
    t.transverse(); 
    t.del(41); 
    t.tranverse(); 
*/ 

    tree bst; 
    int pre_data[] = {20,8,4,12,10,14,22}; 
    int in_data[] = {4,8,10,12,14,20,22}; 
    bst.p = bst.createBST(pre_data, in_data, 7); 
    bst.transverse(); 

    return 0; 
} 

***************修改日期：***************************

編譯無錯誤。但運行後出現分段錯誤。

在gcc下運行它。

Answer 1

tree::leaf* tree::createBST(int *preOrder, int* inOrder, int len) 
{ 
    int i; 
    tree::leaf *bst = new tree::leaf; 
    // tree bst; 
    if(len < 0) 
     bst = NULL; 
    return bst; // This doesn't come under `if` statement. Nothing gets executed 
       // after this statement. So, returning a leaf whose members are 
       // not initialized at all. 

    // .... 

} 

您現在正在收集它main() -

bst.p = bst.createBST(pre_data, in_data, 7); 

的bst.p（即，L，R，數據）的成員，不被分配任何值。但是您正在請求任何致電in(..), pre(..), post(..)的人以及分段錯誤。

Answer 2

由於馬赫什的評論暗示，你createBST方法並不實際修改tree對象調用它。所以你的樹開始空了，通過調用createBST並非非空;因爲你遍歷了一棵空樹，所以樹遍歷不了。