二叉樹 - 分段故障

-1

#include <stdio.h> 
#include <stdlib.h> 

typedef struct nod{ 
    int data; 
    struct nod *left,*right; 
}NOD; 

NOD * generate(NOD * root) 
{ 
    NOD *r,*p; 
    int d=-1,value,line,position,i,f,v; 
    if(root==NULL) 
    { 
     do{ 
      printf("Would you like to create the root node?\n\n1 - yes\n0 - no\n"); 
      scanf("%d",&d); 
      switch(d) 
      { 
       case 1: 
        printf("Value="); 
        scanf("%d",&value); 
        root=add_root(value); 
        break; 
       case 0: 
        return NULL; 
        break; 
       default: 
        printf("Command unrecognized!\n"); 
        break; 
      } 
     } while(d==-1); 
     if(root!=NULL) 
       printf("Root node successfully created!\n"); 
     else 
      printf("Error: could not create root node!\n"); 
     d=-1; 
     do{ 
      printf("Continue adding nodes?\n\n1 - yes\n0 - no\n"); 
      scanf("%d",&d); 
      switch(d) 
      { 
       case 1: 
        printf("Insert the line and the position of the node you wish to add (root node has line=0, position=0)\nLine="); 
        scanf("%d",&line); 
        printf("Position (less or equal with 2^$line-1)="); 
        scanf("%d",&position); 
        printf("Value="); 
        scanf("%d",&value); 
        r=p=root; 
        for(i=line-1;i=0;i--) 
        { 
         f=power(2,i); 
         if(position & f == f) // if the i-(st,nd,rd,th) bit of "position" is 1, then (position & f == f) is true and *r will go right 
         { 
          p=r; 
          r=r->right; 
          v=1; 
         } 
         else 
         { 
          p=r; 
          r=r->left; 
          v=0; 
         } 
        } 
        if(v==0) 
         p=add_left(&r,value); 
        if(v==1) 
         p=add_right(&r,value); 

        break; 
       case 0: 
        return root; 
        break; 
       default: 
        printf("Command unrecognized!\n"); 
        break; 
      } 
     } while(d==-1); 
    } 
    else 
    { 
     ... 
    } 

NOD * add_left(NOD **p,int value) 
{ 
    NOD * r; 
    r=malloc(sizeof(NOD)); 
    r->data=value; 
    r->left=NULL; 
    r->right=NULL; 
    (*p)->left=r; 
    return r; 
} 

NOD * add_right(NOD **p,int value) 
{ 
    NOD * r; 
    r=malloc(sizeof(NOD)); 
    r->data=value; 
    r->left=NULL; 
    r->right=NULL; 
    (*p)->right=r; 
    return r; 
} 

NOD * add_root(int value) 
{ 
    NOD * x; 
    x=malloc(sizeof(NOD)); 
    x->data=value; 
    x->left=NULL; 
    x->right=NULL; 
    return x; 
} 

} 
int main() { 
    NOD *root=NULL; 
    root=generate(root); 
    return 0; 
}

我試圖做的是創建一個二叉樹的程序，但我不斷收到SIGSEGV段錯誤，我不明白爲什麼。你能告訴我我做錯了什麼嗎？二叉樹 - 分段故障

if(position & f == f) // if the i-(st,nd,rd,th) bit of "*position*" is 1, 
         // then (position & f == f) is true and *r will go right

您對這部分有什麼看法？

線是樹的級別（根部具有線= 0）
位置是節點的位置從左至右（根部具有位置= 0）

來源

2012-05-27 Cristi

請儘量縮小問題，並使用調試器。就目前而言，這是很多代碼，可能會導致對C的基本原理的一些基本誤解，或者可能是一個簡單的錯誤。 –

您已經加粗一個有爭議的部分：

if(position & f == f)

==比&更高的優先級，從而使被解析爲

if(position & (f == f))

和相同if (position & 1)，不是你想要的。

此外，你打錯了循環條件

for(i=line-1;i=0;i--)

測試也許應該是i >= 0，否則永遠不會執行循環（i = 0是取值爲0的分配）。

如果這些是固定的，執行循環，在第一次迭代r之後是一個空指針，那麼下一個循環迭代導致r = r->right;崩潰，或者，如果所述循環迭代只有一次，add_left(&r,value);（或add_right）解引用一個空指針在倒數第二行試圖訪問其left指針（RESP right）：

NOD * add_left(NOD **p,int value) 
{ 
    NOD * r; 
    r=malloc(sizeof(NOD)); 
    r->data=value; 
    r->left=NULL; 
    r->right=NULL; 
    (*p)->left=r;   // *p == NULL here 
    return r; 
}

來源

2012-05-27 23:52:30

Agree.The編譯器在'＆' 錯誤警告警告C4554：'＆'：檢查可能的錯誤的運算符優先級;用括號說明優先順序 – 2012-05-28 00:03:55

謝謝！但是我認爲r在r = p = root時被初始化; – Cristi

@克里斯蒂哦，對了，忽略了代碼的牆上。但是，一旦你多次調用'r = r-> right'，你就有一個未初始化的指針。 –

在這一行

for(i=line-1;i=0;i--)

我覺得你的意思

for(i=line-1;i!=0;i--)

否則循環將不會執行（i=0評估爲false）。這導致v具有未定義的值（因爲它從未初始化）。雖然這很可能不會導致段錯誤，但當您覆蓋根的左/右子樹時，會導致內存泄漏。

此外，默認switch分支不改變d掃描值，這意味着你繼續用NULL根（錯誤的分支，對於root != NULL檢查）不會退出功能）

來源

2012-05-28 00:23:26 Attila

二叉樹 - 分段故障

回答

相關問題