首先了解什么是二叉树重建:
我们知道, 二叉树的遍历有三种, 前序, 中序, 后序.
我们可以根据其中的任意两种遍历得到的序列, 求出这颗二叉树另一种遍历序列~
如给出前序与中序
前:4231756
中:3214576
求其后序遍历(3125674)
思路: 前序遍历中的第一个字符, 毫无疑问肯定是根结点! (在上面给出的前序中, 第一个字符是4)
根据而在中序中, 该根结点是一个分水岭, 它将中序序列变成了两半, 左一半是根结点的左儿子部分(321), 右一半是右儿子部分(576)
由于要求的是后序序列, 我们得到的根节点, 事实上是要放在最后的, 我们可以用一个ans数组保存(稍后体会)
接着, 我们要对第一个根结点4的左儿子部分进行剖析, 把左儿子部分也建成树, 同理, 稍后把右儿子部分建成树~(递归!)
理解了上面的思路后, 看看代码实现的过程
#include<stdio.h>
#include<string.h>
//n表示待查序列长度, s1是前序序列, s2是中序序列, s是ans数组的指针
void build(int n, char *s1, char *s2, char *s) {
if(n <= 0)
return;
int p = strchr(s2, s1[0]) - s2; //根据前序, 在中序中找到根节点(可用上面给出的数据模拟, 假设第一个根节点是4)
build(p, s1+1, s2, s); //左儿子部分, 试着理解: 前序s1的第一个4找到后, 接下来的s1+1是左儿子部分的根结点(即2), p是左儿子的长度
build(n-1-p, s1+p+1, s2+p+1, s+p); //右儿子部分, 长度为n-p-1, 是总长度减左树再减根结点1个(即4), s1+p+1 and s2+p+1 同理
s[n-1] = s1[0]; //由于求后序遍历, 所以最后将开头得到的根结点, 放在答案数组的最后~
}
int main() {
char str1[30], str2[30];
char ans[30];
int len;
while(scanf("%s%s", str1, str2) != EOF) {
len = strlen(str1);
build(len, str1, str2, ans);
ans[len] = '\0';
puts(ans);
}
return 0;
}
再看看由中序和后序求前序:
数据还是原先的数据:
中:3214576
后:3125674
求其前序遍历(4231756)
思路转化一下, 可以先由后序的最后一个字符可知根结点.
注意点:
不同与前面由前序中序的重建, 所求后序的保存顺序是 左子树 -> 右子树 -> 根
因此, 在上面求后序的时候, 是在把左子树和右子树都递归好了后, 再最后把根放在答案数组的最后面
而在根据中序和后续求前序的过程中, 我们前序的保存顺序是 根 -> 左子树 -> 右子数
所以, 我们一开始求得根结点后就要保存下来, 再去递归左右子树!
看代码理解:
#include<stdio.h>
#include<string.h>
int pos;
void build(int n, char *s1, char *s2, char *s) {
if(n <= 0)
return ;
int p = strchr(s1, s2[n-1]) - s1; //找根
s[0] = s2[n-1]; //先保存根节点! 还是放在答案数组的开头! 体会和上面保存方式的不一样!
build(p, s1, s2, s+1); //左子树, 与上面同理, 但是在中序结构(左-根-右)和后序结构(左-右-根)中, 左树都是在开头, 于是s1 s2都从开头继续递归
build(n-p-1, s1+p+1, s2+p, s+p+1); //右子树, 根据中序结构, 在找到根后, s1要减去左树长度(p), 再减去根长度(1), 而后序s2只要减去左树长度
}
int main() {
char str1[50];
char str2[50];
while(scanf("%s%s", str1, str2) != EOF) {
char ch, ans[50];
int len = strlen(str1);
pos = 0;
build(len, str1, str2, ans);
ans[len] = '\0';
puts(ans);
}
return 0;
}
看完以上两个示例, 不知道你们有没有找出点规律的蛛丝马迹, 看不懂的话仔细的揣摩两遍, 就懂了
这里有些很有规律的东西, 记下后可以当初一个伪模板
求后序时, 递归函数的顺序是, 递归左子树 -> 递归右子树 -> 保存根 (和后序的结构一样, 是左-右-根)
求前序时, 递归函数的顺序是, 保存根 -> 递归左子树 -> 递归右子树 (同理, 和前序的结构一样)
不难, 最后还有根据前序、后续求中序的代码, 但是这两种顺序求出的树是不唯一的, 但是也能敲~
分享到:
相关推荐
绝对超值,具有二叉树的基本特征………………
python 四种方法解析重建二叉树,七种方法遍历二叉树 四种方法解析重建二叉树包括: 1、通过对象实例的左右儿子方法重建 2、通过键盘输入先序遍历重建 3、通过先序遍历的列表重建 4、通过层序遍历列表重建 七种方法...
C语言实现二叉树的重建,VC环境下调试,完整源码
输入二叉树的前序、中序遍历序列,输出二叉树层序遍历的结果。
对于二叉树T,可以递归定义它的先序遍历、中序遍历和后序遍历如下: PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=...
功能完善,有容错能力,先序和中序建立二叉树,中序和后序建立二叉树,包括二叉树的遍历操作,下载肯定不会后悔
前序和中序重建二叉树并包含父节点
这是一个根据前序和中序恢复原来二叉树的java代码,很多不足的地方,希望大家指正
c++分治实现二叉树的重建,并且判断是否同构。完整代码。
重建二叉树.md
基于C++的数据结构:二叉树前中后序遍历+重建+输出 以前课程作业写的代码
基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、...
数据结构课程设计报告(二叉树的重建和数字对应英文单词)
剑指offer面试题(7)——重建二叉树整体工程代码,C++语言实现。
重建二叉树1
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回...
本文实例讲述了Python实现重建二叉树的三种方法。分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串...
数算的二叉树的POJ作业,分别有:二叉树1_二叉树的操作;...二叉树3_由中根序列和后根序列重建二叉树;二叉树4_表达式.表达式树.表达式求值;二叉树5_Huffman编码树;二叉树6_二叉搜索树;二叉树7_实现堆结构
只要学懂了链表,二叉树并不难理解,链表只有一个指向,二叉树有左右两个指向,关于前序、中序、后续遍历顺序网上有很多介绍,可以仔细看看,这里就不放链接了,自己动手丰衣足食,只需要了解的是只要中序和(前序或...