在C中遍历二叉树

Question

我正在尝试遍历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;
    }

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(struct decl)).在C中,您不需要转换malloc,btw的返回值.

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