4

我正在尝试遍历 C 中的二叉树。我的树包含一个 AST 节点（编译器的抽象语法树节点）。ASTnode保留nodetype指定给定节点的类型（即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;
        }
    }

此外，我们不能为 CONSTANT 节点分配左值或右值，因为在 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);
    }

如果我们删除 node5（由 !! 标记），则代码运行良好，否则会出现分段错误。

作用于 的函数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;
    }
4

6 回答 6

11

你的 malloc 是错误的

 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(struct decl)）。在 C 中，您不需要强制转换 malloc 的返回值，顺便说一句。

此外，请确保在访问之前将成员设置为 NULL 或其他默认值。malloc 不会为您将它们设置为 0/NULL。

于 2009-12-26T16:24:10.253 回答
1

我所能看到的是，也许你想root->value在传递给 printf 之前检查 et al。

此外，虽然这不应该导致错误，但您可能想要更改

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

到

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

编辑：等等，这里有一些东西 - 当你传递root->left遍历时，是值本身还是指针？该函数需要一个指针。

于 2009-12-26T16:16:30.643 回答
1

您没有在第一个“if”块中检查“root”是否为 NULL。我认为最简单的方法是包装

if(root != NULL)

围绕整个事情（最终返回除外），并在打印 INT 和 CHAR 节点时摆脱单独的 'root != NULL' 检查。

分享和享受。

编辑：这就是我的意思：

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); 
      }
    } 
  }

还更改为使用开关而不是一堆 if。

请原谅任何语法错误：这是我的想法，没有方便的编译器。

于 2009-12-26T16:19:39.093 回答
1

makeNode 函数需要初始化结构的所有成员。是否可能没有将左/右指针之一设置为 NULL？malloc() 调用不会将内存归零。

确认 - 我是盲人。否的答案是正确的。不正确的 malloc 调用。我只是在增加噪音。

于 2009-12-26T16:20:14.583 回答
1

您的代码将在传递给 traverse() 的第一个 NULL 节点处发生段错误。

您注意检查root != NULL您的 else 块，但到那时您已经取消引用它。如果您尝试取消引用 NULL 指针，则会出现段错误。

尝试添加

if (!root) return;

作为你的第一行。

于 2009-12-26T16:20:35.363 回答
1

您显示分配“ struct decl”指针的代码；您没有显示初始化它们的代码。不清楚为什么 makeNode() 会初始化它的第二个参数，或者它是如何这样做的。也不清楚 3 是什么意思。也不清楚 ' struct decl' 是如何集成到 ASTnode 中的。

您可以通过及早处理异常情况来简化 traverse() ：

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() 函数的作用可能会有所帮助；它是否确保节点的所有部分都正确初始化。

于 2009-12-26T16:41:55.333 回答