C语言递归二叉树后序命题计算器段错误排查求助

问题根源 #

createTreeFromExpression()函数存在两个核心逻辑错误：

1. 无边界检查：未判断当前索引是否超出表达式字符串长度，导致递归到字符串末尾后仍继续访问无效内存，触发野指针。
2. 子节点创建逻辑错误：
   • 操作数T/F是叶子节点，不应创建子节点，但原代码强制递归创建左右子节点；
   • 单目运算符N（非）仅需右子节点，原代码却同时创建左右子节点；
   • 上述错误导致树结构中出现大量无效空节点，后续postOrderEval()访问这些节点时触发段错误。

修正后的完整代码 #

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

#define MAX_EXPRESSION_SIZE 100
#define TRUE 1
#define FALSE 0

typedef enum {not, and, or, true, false} logical;

typedef struct treeNode *treePtr;

typedef struct treeNode {
    treePtr left_child;
    logical data;
    short int value;
    treePtr right_child;
} node;

/**Evaluates the binary tree of truth values and operators in post-order*/
void postOrderEval(treePtr node) {
    if (node) {
        postOrderEval(node->left_child);
        postOrderEval(node->right_child);
        switch (node->data){
            case not:   node->value = !node->right_child->value;
                        break;
            case and:   node->value = node->right_child->value
                                      && node->left_child->value;
                        break;
            case or:    node->value = node->right_child->value
                                      || node->left_child->value;
                        break;
            case true:  node->value = TRUE; break;
            case false: node->value = FALSE; break;
        }//end switch
    }//end if
}

treePtr createTreeFromExpression(const char *expression, int *index) {
    // 边界检查：索引超出字符串长度，返回NULL
    if (expression[*index] == '\0') {
        return NULL;
    }

    treePtr newNode = (treePtr)malloc(sizeof(node));
    if (!newNode) {
        return NULL;
    }

    // 初始化节点数据
    switch (expression[*index]) {
        case 'N': newNode->data = not; break;
        case 'A': newNode->data = and; break;
        case 'O': newNode->data = or; break;
        case 'T': newNode->data = true; break;
        case 'F': newNode->data = false; break;
        default: free(newNode); return NULL;
    }
    (*index)++;  // 移动到下一个字符

    // 根据节点类型创建对应子节点
    switch (newNode->data) {
        case true:
        case false:
            // 操作数是叶子节点，无左右子节点
            newNode->left_child = NULL;
            newNode->right_child = NULL;
            break;
        case not:
            // 非运算符是单目，仅需右子节点
            newNode->left_child = NULL;
            newNode->right_child = createTreeFromExpression(expression, index);
            break;
        case and:
        case or:
            // 与/或是双目，需要左右子节点
            newNode->left_child = createTreeFromExpression(expression, index);
            newNode->right_child = createTreeFromExpression(expression, index);
            break;
    }

    return newNode;
}

void printExpression(treePtr node) {
    if (node) {
        switch (node->data) {
            case not:  printf("N"); break;
            case and:  printf("A"); break;
            case or:  printf("O"); break;
            case true: printf("T"); break;
            case false: printf("F"); break;
        }
        printExpression(node->left_child);
        printExpression(node->right_child);
    }
}

//Driver code
int main() {
    char expression[MAX_EXPRESSION_SIZE];
    printf("Enter a propositional expression without space or newline.\n");
    printf("Press ENTER when you're done. \n");

    scanf("%s", expression);
    
    int index = 0;
    treePtr root = createTreeFromExpression(expression, &index);

    // Print the original and swapped post-order traversals
    printf("Proposition in post-order: ");
    printExpression(root);
    printf("\n");

    // Evaluate the expression
    postOrderEval(root);

    // Display the result
    printf("Propositional Tree result: %s\n", (root->value == TRUE) ? "TRUE" : "FALSE");

    return 0;
}

关键修正点说明 #

1. 添加边界检查：在函数开头判断expression[*index] == '\0'，避免访问字符串末尾后的无效内存。
2. 区分节点类型创建子节点：
   • T/F：直接将左右子节点设为NULL，终止递归；
   • N：仅创建右子节点，符合单目运算符的结构；
   • A/O：创建左右两个子节点，匹配双目运算符需求。

测试验证 #

• 输入FFA：预期输出FALSE，修正后程序正常运行并输出正确结果；
• 输入TFANTA：预期输出TRUE，修正后程序正常输出；
• 输入NTFANFTAO：预期输出TRUE，修正后程序正常输出。

内容的提问来源于stack exchange，提问作者benhpark