遍歷C中的二叉樹C

Question

我想遍歷C中的二叉樹。我的樹包含一個AST節點（編譯器的抽象語法樹節點）。 ASTnode保留指定給定節點類型的節點類型（即INT OP或CHAR和TYPE，我們不需要關心其他類型），其他成員是左指針和右指針，最後我們存儲。

這裏是穿越代碼：

void traverse(struct ASTNode *root) 
    { 
     if(root->nodeType == OP){ 
      printf("OP \n"); 
      if(root->left != NULL){ 
       printf("left - "); 
       traverse(root->left); 
      } 
      if(root->right != NULL){ 
       printf("right - "); 
       traverse(root->right); 
      } 
      return; 
     } 
     else{ 
      if(root != NULL && root->nodeType == INT) 
      { 
       printf("INT - "); 
       printf("INT: %d\n",root->value); 
      } 
      if(root != NULL && root->nodeType == CHAR) 
      { 
       printf("CHAR - "); 
       printf("CHAR: %c\n",root->chValue); 
      } 
      return; 
     } 
    } 

同時，我們也不能分配左邊或右邊的值恆定的節點，因爲在AST，恆值不包含任何額外的價值。

更新時間：

的問題是在我的主要電話：

int main() 
    { 
     struct ASTNode *node1 = makeCharNode('a'); 
     struct ASTNode *node2 = makeCharNode('b'); 
     struct ASTNode *node10 = makeCharNode('c'); 
     struct ASTNode *node3 = makeINTNode(19); 

     struct decl *d = (struct decl*) malloc(sizeof(struct decl*)); 
     struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*)); 

     struct ASTNode *node4 = makeNode(3,d,node3,node2); 
     struct ASTNode *node5 = makeNode(3,d2,node4,node1); !! 
     traverse(node4); 
    } 

如果我們刪除節點5（這是由!!標記）的代碼工作得很好，否則它給出了一個分段錯誤。

功能上makenode操作：

struct ASTNode *makeNode(int opType,struct decl *resultType,struct ASTNode *left,struct ASTNode *right) 
    { 
     struct ASTNode *node= (struct ASTNode *) malloc(sizeof(struct ASTNode *)); 
     node->nodeType = opType; 
     node->resultType = resultType; 
     node->left = left; 
     node->right = right; 
     return node; 
    } 

    struct ASTNode *makeINTNode(int value) 
    { 
     struct ASTNode *intnode= (struct ASTNode *) malloc(sizeof(struct ASTNode *)); 
     intnode->nodeType = INT; 
     intnode->value = value; 
     return intnode; 
    } 

    struct ASTNode *makeCharNode(char chValue) 
    { 
     struct ASTNode *charNode = (struct ASTNode *) malloc(sizeof(struct ASTNode *)); 
     charNode->nodeType = CHAR; 
     charNode->chValue = chValue; 
     return charNode; 
    } 

Answer 1

你mallocs是錯誤的

struct decl *d = (struct decl*) malloc(sizeof(struct decl*)); 
struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*)); 

需要被

struct decl *d = (struct decl*) malloc(sizeof(struct decl)); 
struct decl *d2 = (struct decl*) malloc(sizeof(struct decl)); 

（或使用sizeof * d代替的sizeof（結構DECL））。在C中，你不需要轉換malloc的返回值，順便說一句。

另外，請確保在訪問它們之前將成員設置爲NULL或其他默認值。 malloc不會將它們設置爲0/NULL。

Answer 2

所有我能看到的是，也許你想要傳遞給printf的前檢查root->value等。

此外，雖然這不會造成錯誤，你可能需要更改

if(root != NULL && root->nodeType == CHAR)

到

else if(root != NULL && root->nodeType == CHAR)

編輯：等待，這裏的東西 - 當你通過root->left遍歷，是價值本身還是指針？該函數需要一個指針。

Answer 3

您不檢查第一個'if'塊中'root'是否爲NULL。我認爲最簡單的辦法是包裝

if(root != NULL) 

圍繞整個事情（除了最後的回報），並擺脫了單獨的「根！= NULL」支票打印INT和CHAR節點時。

分享和享受。

編輯：這裏是我的意思是：

void traverse(struct ASTNode *root) 
    { 
    if(root != NULL) 
    { 
    switch(root->nodeType) 
     { 
     case OP: 
     printf("OP \n"); 

     if(root->left != NULL) 
      { 
      printf("left - "); 
      traverse(root->left); 
      } 

     if(root->right != NULL) 
      { 
      printf("right - "); 
      traverse(root->right); 
      } 
     break; 

     case INT: 
     printf("INT - "); 
     printf("INT: %d\n",root->value); 
     break; 

     case CHAR: 
     printf("CHAR - "); 
     printf("CHAR: %c\n",root->chValue); 
     } 
    } 
    } 

也發生了變化，而不是使用一堆的，如果是一個開關。

請原諒任何語法錯誤：這是我的頭頂，沒有編譯器方便。

Answer 4

makeNode函數需要初始化結構的所有成員。它可能沒有設置一個左/右指針爲NULL？ malloc（）調用不會清零內存。

Ack - 我是盲人。 nos的答案是正確的。不正確的malloc調用。我只是增加了噪音。

Answer 5

您的代碼將在傳遞給traverse（）的第一個NULL節點處發生segfault。

你注意在你的else塊中檢查root != NULL，但到那時你已經取消了它。如果你嘗試解引用一個NULL指針，你會發生段錯誤。

嘗試增加

if (!root) return; 

爲您的第一道防線。

Answer 6

您顯示代碼分配'struct decl'指針;你不會顯示初始化它們的代碼。目前還不清楚爲什麼makeNode（）會初始化它的第二個參數，或者它會怎麼做。這3個含義也不清楚。也不清楚'struct decl'如何集成到ASTnode中。

您可以通過使用特殊情況下，早期處理簡化移動（）：

void traverse(struct ASTNode *root) 
{ 
    if (root == NULL) // Or: assert(root != NULL); 
    return; 
    if (root->nodeType == OP) 
    { 
    printf("OP \n"); 
    if (root->left != NULL) 
    { 
     printf("left - "); 
     traverse(root->left); 
    } 
    if (root->right != NULL) 
    { 
     printf("right - "); 
     traverse(root->right); 
    } 
    } 
    else if (root->nodeType == INT) 
    { 
    printf("INT - "); 
    printf("INT: %d\n", root->value);  
    } 
    else if (root->nodeType == CHAR) 
    { 
    printf("CHAR - "); 
    printf("CHAR: %c\n", root->chValue); 
    } 
    else 
    assert("Unrecognized nodeType" == 0); 
} 

這也與不可能的情況下交易 - 不能識別的節點類型。它也不會崩潰和燃燒，如果一個空指針傳入英寸

但是，這還沒有解釋爲什麼你的代碼崩潰，並沒有崩潰，取決於額外的ASTnode ...我不相信我們有足夠的代碼來確定爲什麼發生這種情況。您是否試過遍歷所有節點（node1，node2，node3，node10）？假設makeCharNode（）和makeINTNode（）函數能夠正常工作，這些應該沒問題，但是這種基本檢查可以保存培根。查看makeNode（）函數的作用可能會有所幫助;它確保節點的所有部分都已正確初始化。