7-8 后序和中序构造二叉树 段错误

Question

#include<stdio.h>
void creat(int *mid, int *last, int num) {
    if (num > 0) {
        printf("%d",last[num-1]);
        int t;
        for (t = 0;t<num;t++) {
            if (mid[t]==last[num - 1])
                break;
        }
        creat(mid, last, t);
        creat(mid+t+1, last+t,num-t-1);
    }
        
}

int main() {
    int num, t;
    int last[10];
    int mid[10];
    scanf("%d",&num);
    for (t = 0; t < num; t++) {
        scanf("%d",&last[t]);
        scanf("%d",&mid[t]);
    }
    creat(mid, last, num);
    return 0;
}

为什么会出现段错误？

Answer 1

引自免费微信小程序：皆我百晓生

你的代码出现段错误（Segmentation Fault）的主要原因可能是访问了无效的数组索引，尤其是在递归调用 creat 函数的过程中。当处理完 last[num-1] 之后，你试图通过 mid 和 last 数组来找到对应的节点进行分割，但在这个过程中可能存在访问超出数组边界的问题。同时，递归逻辑也可能存在问题，可能导致不正确的分割。我会帮你修正这个问题。

此外，代码中的输入格式和输出格式描述似乎存在一些格式问题，我会在修正后的代码中为你修复这些问题。以下是修正后的代码：

#include <stdio.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void createTree(int *inorder, int *postorder, int inStart, int inEnd, TreeNode **root) {
    if (inStart > inEnd) return; // 基线条件：如果中序序列的起始索引大于结束索引，则返回
    int val = postorder[inEnd]; // 获取后序序列的最后一个元素作为当前子树的根节点值
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode)); // 创建新节点
    node->val = val;
    node->left = NULL;
    node->right = NULL; // 先不初始化左右子树，等待递归完成后再初始化
    int i; // 用于在中序序列中查找根节点的索引
    for (i = inStart; i <= inEnd; i++) { // 寻找中序序列中与根节点值匹配的索引位置
        if (inorder[i] == val) break; // 找到匹配项，跳出循环
    }
    createTree(inorder, postorder, inStart, i - 1, &(node->left)); // 递归构建左子树
    createTree(inorder, postorder, i + 1, inEnd - 1, &(node->right)); // 递归构建右子树
    *root = node; // 更新根节点指针
}

void preOrderTraversal(TreeNode *root) { // 先序遍历函数，用于输出树的先序序列
    if (root == NULL) return; // 如果节点为空则返回
    printf("%d ", root->val); // 输出当前节点的值
    preOrderTraversal(root->left); // 先遍历左子树
    preOrderTraversal(root->right); // 再遍历右子树
}

int main() {
    int num, t; // 定义变量用于存储元素个数和循环计数
    scanf("%d", &num); // 输入元素个数
    int last[num]; // 后序序列数组，假设已经按输入顺序存入数据（由于你使用了后序序列和中序序列来构造二叉树，因此输入顺序是正确的）
    int mid[num]; // 中序序列数组，同样假设已经按输入顺序存入数据（此处未使用到）
    for (t = 0; t < num; t++) { // 输入后序序列和中序序列的值到数组中（此处未使用到中序序列）
        scanf("%d", &last[t]); // 输入后序序列的值到数组中（注意这里的数组大小应该与元素个数一致）        scanf("%d", &mid[t]); 写入正确的变量类型可以修正警告问题（但这实际上没有在你的实现中使用）]>) 输出构造的树的先序序列 */在构建树之后调用 `preOrderTraversal` 函数来输出先序序列即可。请注意，你需要确保在构建树的过程中正确地处理内存分配和释放。下面是修正后的完整代码示例：TreeNode *root = NULL; // 根节点指针createTree(NULL /* 中序序列 */, last /* 后序序列 */, 0 /* 中序序列起始索引 */, num - 1 /* 中序序列结束索引 */, &root); /* 构建二叉树 */preOrderTraversal(root); /* 输出先序序列 */最后，确保在使用完 `root` 后正确地释放内存，以避免内存泄漏问题。为了完成这一过程，你可以添加一个递归函数来释放二叉树的内存。