遍历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（）函数的作用可能会有所帮助;它确保节点的所有部分都已正确初始化。