十八、二叉树遍历序列还原

文章目录

• 十八、二叉树遍历序列还原
• • 题目描述
  • 解题思路
  • 上机代码

题目描述

给出二叉树的中序遍历序列和后序遍历序列，编程还原该二叉树。

输入：

​第1行为二叉树的中序遍历序列
第2行为二叉树的后序遍历序列

输出：

二叉树的按层遍历序列

测试输入期待的输出时间限制内存限制额外进程

测试用例 1	badcfeg bdfgeca	abcdefg	1秒	64M	0
测试用例 2	cbdafeg cbdfgea	adebfgc	1秒	64M	0
测试用例 3	edcba edcba	abcde	1秒	64M	0
测试用例 4	bdfgeca gfedcba	abcdefg	1秒	64M	0

解题思路

由后序序列的遍历方式可知，后序序列的最后一个结点一定是二叉树的根结点。通过找到根结点在中序序列中的位置，可以将中序序列分成左右两个序列，左侧序列是根结点的左子树的中序序列，右侧序列是根结点右子树的中序序列。

对于根结点左子树的遍历来说，不管是中序遍历还是后序遍历，因为结点数的相同的，遍历结果的长度也一定相同。可以根据根结点左子树的中序遍历序列的长度，得到后序序列中根结点左子树的后序序列。对根结点的右子树同理，可以得到后序序列中根结点右子树的后序序列。

这样，根结点左右子树的中序和后序遍历序列都一一对应了起来，采用递归的方式即可将整个二叉树的关系搞清楚，并建立起二叉树。

---

对测试用例 2 进行说明

后序序列 cbdfgea 可以知道根结点为 a，从而将中序序列分为 cbd、feg，即根结点的左右子树的中序遍历序列。根节点的左子树的长度为3，可以得到后序序列中的 cbd 为根结点左子树的后序序列。同理 fge是根结点右子树的后序序列。

将中序序列 cbd 和后序序列 cbd 结合，中序序列 feg 和后序序列 fge 结合，可以分别求出根结点的左右子树的根结点，这样递归求解下来，就可以得到整个二叉树的关系了。

上机代码

#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef struct BiTNode {char data;struct BiTNode *lchild;struct BiTNode *rchild; }BiTNode,*BiTree;//找到根结点在序列中的位置 int find(char index, char *array, int len)//待查找的根结点，查找序列，序列长度 {for (int i = 0; i < len; i++){if (array[i] == index)return i;} } //递归建立二叉树 BiTree BuildBiTree(char *center, char *last, int len)//中序序列、后序序列、序列长度 {if (len <= 0)return NULL;BiTree T = new BiTNode;T->data = last[len - 1];//后序序列的最后结点一定是根结点int root = find(last[len - 1], center, len);//找到根结点在中序序列中的位置//根据拆分的序列递归建树T->lchild = BuildBiTree(center, last, root);T->rchild = BuildBiTree(center + root + 1, last + root, len - root - 1);return T; } void bfs(BiTree T) //利用队列进行层次遍历 {BiTree tmp = (BiTree)malloc(sizeof(BiTNode));queue<BiTree>q;q.push(T);while (!q.empty()){tmp = q.front();cout << tmp->data;q.pop();if (tmp->lchild != NULL)q.push(tmp->lchild);if (tmp->rchild != NULL)q.push(tmp->rchild);}cout << endl; } int main() {char *inorder = new char[105]; //中序序列char *postorder = new char[105]; //后序序列int len = 0;BiTree bit = (BiTree)malloc(sizeof(BiTNode));//根据输入序列建树cin >> inorder >> postorder;len = strlen(postorder);bit = BuildBiTree(inorder, postorder, len);//输出层次序列bfs(bit);return 0; }

总结

以上是生活随笔为你收集整理的十八、二叉树遍历序列还原的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。