学习工控知识，就来工控小新

农历腊月初四 2024/1/ 16

往期推荐

2024年1月13日，每日一分钟练习C语言，学习路上不能停

2024年1月12日，每日一分钟练习C语言，学习路上不能停

每日一练

/ Daily Exercises

给定一棵树的中序遍历和后序遍历序列，要求用C语言编写一个程序，根据这两个序列构造出原来的二叉树，并输出其前序遍历序列。假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3

/ \

9 20

/ \

15 7

并输出其前序遍历序列为 [3,9,20,15,7]。

题目分析

要解决这个问题，我们需要了解二叉树的遍历方式有哪些，以及它们之间的关系。

二叉树的遍历方式主要有三种：前序遍历、中序遍历和后序遍历。它们的定义如下：

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

根据这些定义，我们可以发现一个规律：后序遍历的最后一个元素一定是根节点。这是因为后序遍历的顺序是先左后右再根，所以最后一个元素就是最后访问的根节点。

利用这个规律，我们可以根据后序遍历序列确定根节点的值，然后在中序遍历序列中找到根节点的位置，这样就可以将中序遍历序列分成两部分：左子树的中序遍历和右子树的中序遍历。同理，我们也可以将后序遍历序列分成两部分：左子树的后序遍历和右子树的后序遍历。

这样，我们就可以递归地构造左子树和右子树，最后将它们连接到根节点上，就得到了原来的二叉树。

程序展示

根据上述分析，我们可以用C语言实现如下的算法：

定义一个结构体，表示二叉树的节点，包含值、左孩子和右孩子三个字段。

定义一个函数，根据中序遍历和后序遍历序列构造二叉树，并返回根节点的指针。

如果后序遍历序列为空，说明是空树，返回NULL。如果后序遍历序列只有一个元素，说明是叶子节点，创建一个新节点并返回。否则，取后序遍历序列的最后一个元素作为根节点的值，创建一个新节点。在中序遍历序列中找到根节点的值的位置，作为切割点，将中序遍历序列分成左右两部分。根据切割点，将后序遍历序列也分成左右两部分，注意去掉最后一个元素，因为它已经作为根节点使用了。递归地构造左子树和右子树，并将它们连接到根节点上。返回根节点的指针。

定义一个函数，根据前序遍历二叉树，并输出其序列。

如果根节点为空，返回。否则，输出根节点的值，然后递归地遍历左子树和右子树。

#include <stdio.h>#include <stdlib.h>// 定义二叉树的节点结构体typedef struct TreeNode {    int val; // 节点的值    struct TreeNode *left; // 左孩子的指针    struct TreeNode *right; // 右孩子的指针} TreeNode;// 根据中序遍历和后序遍历序列构造二叉树，并返回根节点的指针TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){    // 如果后序遍历序列为空，说明是空树，返回NULL    if (postorderSize == 0) return NULL;    // 如果后序遍历序列只有一个元素，说明是叶子节点，创建一个新节点并返回    if (postorderSize == 1) {        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); // 分配内存空间        node->val = postorder[0]; // 赋值        node->left = NULL; // 左孩子为空        node->right = NULL; // 右孩子为空        return node;    }    // 否则，取后序遍历序列的最后一个元素作为根节点的值，创建一个新节点    int rootValue = postorder[postorderSize - 1];    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));    root->val = rootValue;    // 在中序遍历序列中找到根节点的值的位置，作为切割点，将中序遍历序列分成左右两部分    int delimiterIndex;    for (delimiterIndex = 0; delimiterIndex < inorderSize; delimiterIndex++)   {        if (inorder[delimiterIndex] == rootValue) break;    }    // 根据切割点，将后序遍历序列也分成左右两部分，注意去掉最后一个元素，因为它已经作为根节点使用了    int leftInorderSize = delimiterIndex; // 左子树的中序遍历序列的长度    int rightInorderSize = inorderSize - delimiterIndex - 1; // 右子树的中序遍历序列的长度    int leftPostorderSize = leftInorderSize; // 左子树的后序遍历序列的长度    int rightPostorderSize = rightInorderSize; // 右子树的后序遍历序列的长度    // 递归地构造左子树和右子树，并将它们连接到根节点上    root->left = buildTree(inorder, leftInorderSize, postorder, leftPostorderSize);    root->right = buildTree(inorder + leftInorderSize + 1, rightInorderSize, postorder + leftPostorderSize, rightPostorderSize);    // 返回根节点的指针    return root;}// 根据前序遍历二叉树，并输出其序列void preorderTraversal(TreeNode* root) {    // 如果根节点为空，返回    if (root == NULL) return;    // 否则，输出根节点的值，然后递归地遍历左子树和右子树    printf("%d ", root->val);    preorderTraversal(root->left);    preorderTraversal(root->right);}// 测试int main() {    // 输入中序遍历和后序遍历序列    int inorder[] = {9,3,15,20,7};    int postorder[] = {9,15,7,20,3};    int size = 5;    // 构造二叉树    TreeNode* root = buildTree(inorder, size, postorder, size);    // 输出前序遍历序列    printf("前序遍历序列为：");    preorderTraversal(root);    printf("\n");    // 释放内存空间    free(root);    return 0;}

程序测试

运行上述代码，在VC6.0的环境下，可以得到如下的输出：

前序遍历序列为：3 9 20 15 7

这与题目给出的结果一致，说明我们的算法是正确的。

源代码获取

#软件下载通道#

我用夸克网盘分享了「20240114」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。

链接：

(链接和提取码建议复制粘贴，手动输入容易出现错误）

#支持一下#

分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓

谢谢大家！

下期题目

给定两个字符串s和t，要求用C语言编写一个程序，返回s中包含t所有字符的最小子串。如果s中不存在这样的子串，则返回空字符串""。注意，如果s中存在这样的子串，我们保证它是唯一的答案。

例如，给出

s = “ADOBECODEBANC”

t = “ABC”

返回"BANC"

给出

s = “a”

t = “a”

返回"a"

提示：

1 <= s.length, t.length <= 10^5

s和t由英文字母组成

点赞加关注，学习不迷路

微信公众号｜工控小新

EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中

#学习C语言#