题解：构建二叉树并进行层序遍历

问题描述

给定二叉树的前序遍历和中序遍历，要求构建出原始的二叉树，并输出该二叉树的层序遍历。

思路分析

1. 二叉树的构建

前序遍历：首先访问根节点，然后访问左子树，最后访问右子树。
中序遍历：首先访问左子树，然后访问根节点，最后访问右子树。

根据前序遍历的第一个元素可以确定根节点，并利用中序遍历找到根节点在其中的位置，从而将中序遍历序列分为左右子树部分。接着递归处理左右子树，最终构建出完整的二叉树。

2. 二叉树的层序遍历

层序遍历使用队列进行遍历。首先将根节点入队，然后循环出队并访问当前节点，同时将该节点的左右子节点入队，直到队列为空。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 35;

struct node {
    int data;
    int left, right; // 使用数组存储左右子节点的下标
};

int n, pre[N], in[N], cnt = 0;
node tree[N]; // 存储二叉树节点的数组

// 构建二叉树的函数
int create(int prel, int prer, int inl, int inr) {
    if (prel > prer)
        return -1;  // 返回-1表示没有节点
    int rootIndex = prel;
    int rootValue = pre[rootIndex];
    int k = inl;
    // 在中序遍历中找到根节点的位置
    while (in[k] != rootValue) k++;
    int numleft = k - inl;
    int leftChild = create(prel + numleft + 1, prer, k + 1, inr); // 构建左子树
    int rightChild = create(prel + 1, prel + numleft, inl, k - 1); // 构建右子树

    tree[rootIndex].data = rootValue;
    tree[rootIndex].left = leftChild;
    tree[rootIndex].right = rightChild;
    return rootIndex;
}

// 层序遍历二叉树
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        printf("%d", tree[now].data);
        if (++cnt < n)
            printf(" ");
        // 将左右子节点入队
        if (tree[now].left != -1)
            q.push(tree[now].left);
        if (tree[now].right != -1)
            q.push(tree[now].right);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
    int root = create(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

代码解析

node 结构体

struct node {
    int data;
    int left, right; // 使用数组存储左右子节点的下标
};

我们使用结构体 node 来表示二叉树的每个节点。每个节点包含：

data：节点的值 left：左子节点的下标 right：右子节点的下标 left 和 right 的值为 -1 时表示该子节点不存在。

create 函数

int create(int prel, int prer, int inl, int inr) {
    if (prel > prer)
        return -1;  // 返回-1表示没有节点
    int rootIndex = prel;
    int rootValue = pre[rootIndex];
    int k = inl;
    while (in[k] != rootValue) k++;
    int numleft = k - inl;
    int leftChild = create(prel + numleft + 1, prer, k + 1, inr); // 构建左子树
    int rightChild = create(prel + 1, prel + numleft, inl, k - 1); // 构建右子树

    tree[rootIndex].data = rootValue;
    tree[rootIndex].left = leftChild;
    tree[rootIndex].right = rightChild;
    return rootIndex;
}

该函数通过递归方式根据前序和中序遍历结果构建二叉树。具体步骤：

从前序遍历中选择根节点。在中序遍历中找到根节点的位置，将序列分为左子树和右子树。对左子树和右子树递归调用 create 函数构建其左右子节点。 3. bfs 函数

void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        printf("%d", tree[now].data);
        if (++cnt < n)
            printf(" ");
        if (tree[now].left != -1)
            q.push(tree[now].left);
        if (tree[now].right != -1)
            q.push(tree[now].right);
    }
}

该函数实现层序遍历，使用队列模拟。步骤如下：

将根节点加入队列。依次访问队列中的节点，输出节点的值。若当前节点有左子节点，将左子节点加入队列；若有右子节点，则将右子节点加入队列。重复直到队列为空。 4. 主函数

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
    int root = create(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

主函数中：

输入节点数量 n，然后输入前序和中序遍历序列。调用 create 函数构建二叉树。调用 bfs 函数输出层序遍历结果。总结本题的关键是通过前序和中序遍历来构建二叉树，然后通过层序遍历输出二叉树的结果。通过递归构建树和队列进行层序遍历是常见的树形问题解法。