从中序遍历和后序遍历序列构造二叉树的C语言实现，一步一步教你

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

农历腊月初四 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

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

源代码获取

给定两个字符串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 ... 每日持续更新中