L2-006 树的遍历

#include <stdio.h>  // 标准输入输出库
#include <stdlib.h> // 标准库，用于动态内存分配

#define MAX_N 30    // 定义最大节点数

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;                    // 节点值
    struct TreeNode *left;      // 左子节点指针
    struct TreeNode *right;     // 右子节点指针
} TreeNode;

// 根据后序和中序遍历构建二叉树
TreeNode* buildTree(int* postorder, int postStart, int postEnd, int* inorder, int inStart, int inEnd) {
    // 如果后序或中序遍历的起始位置大于结束位置，返回空指针
    if (postStart > postEnd || inStart > inEnd) {
        return NULL;
    }

    // 后序遍历的最后一个元素是根节点
    int rootVal = postorder[postEnd];
    // 动态分配内存，创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = rootVal; // 设置根节点的值
    root->left = root->right = NULL; // 初始化左右子节点为空

    // 在中序遍历中找到根节点的位置
    int rootIndex = inStart;
    while (inorder[rootIndex] != rootVal) {
        rootIndex++;
    }

    // 计算左子树的节点数量
    int leftSize = rootIndex - inStart;

    // 递归构建左子树
    root->left = buildTree(postorder, postStart, postStart + leftSize - 1, inorder, inStart, rootIndex - 1);
    // 递归构建右子树
    root->right = buildTree(postorder, postStart + leftSize, postEnd - 1, inorder, rootIndex + 1, inEnd);

    // 返回构建好的树的根节点
    return root;
}

// 层序遍历二叉树
void levelOrder(TreeNode* root) {
    // 如果树为空，直接返回
    if (!root) {
        return;
    }

    // 使用队列进行层序遍历
    TreeNode* queue[MAX_N]; // 定义队列
    int front = 0, rear = 0; // 队列的前后指针
    queue[rear++] = root; // 将根节点入队

    // 当队列不为空时，继续遍历
    while (front < rear) {
        TreeNode* node = queue[front++]; // 出队一个节点
        printf("%d", node->val); // 输出当前节点的值

        // 如果当前节点有左子节点，将其入队
        if (node->left) {
            queue[rear++] = node->left;
        }
        // 如果当前节点有右子节点，将其入队
        if (node->right) {
            queue[rear++] = node->right;
        }

        // 如果队列中还有节点，输出一个空格分隔符
        if (front < rear) {
            printf(" ");
        }
    }
}

int main() {
    int N; // 节点数量
    scanf("%d", &N); // 读取节点数量

    int postorder[MAX_N], inorder[MAX_N]; // 定义后序和中序遍历数组
    // 读取后序遍历序列
    for (int i = 0; i < N; i++) {
        scanf("%d", &postorder[i]);
    }
    // 读取中序遍历序列
    for (int i = 0; i < N; i++) {
        scanf("%d", &inorder[i]);
    }

    // 根据后序和中序遍历构建二叉树
    TreeNode* root = buildTree(postorder, 0, N - 1, inorder, 0, N - 1);

    // 输出层序遍历结果
    levelOrder(root);

    return 0; // 程序正常结束
}