来张助于理解分治策略的图 分治策略 -- 来源网络简书内代码已上传GitHub:点击我 去GitHub查看代码
数据结构学校OJ作业 --- 树相关
【问题描述】
已知一个二叉树的中序遍历序列和后序遍历序列,求这棵树的前序遍历序列。
【输入形式】
一个树的中序遍历序列 该树后序遍历序列,中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母
【输出形式】
一个树的前序遍历序列
【样例输入】
dbeafcg debfgca
【样例输出】
abdecfg
思路:
-
这题的思路很清晰:读取中序和后序序列 、 利用分治策略递归解决问题。
-
至于怎么读取呢?前序中序...反正不管什么顺序,他们都是等长的,以空格分隔读取下来存在字符串里就好了。
-
分治的思路:因为后序遍历最后一个节点一定是根节点,所以利用确定的根节点在中序遍历中确认左右子树的位置,然后再分别对左右子树确定它们的左右子树,一直划分到不能再划分位置。
-
可以参考 二叉树刷题总结(三) 的105题,那题和这题是一样的,只要学会了分治思想怎么来其实都是一个样。
下面是代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// 读取序列
void TravelToString(char* s1, char* s2){
char c;
// flag用于记录中序后序分界
int flag = 1, i = 0;
// max存储序列长度,用于结束读取
int max = -1;
while(i != max){
scanf("%c", &c);
// 读取完中序序列
if(c == ' ') {
flag = 0;
// 串尾标记
s1[i] = '\0';
max = i;
// 更新i
i = 0;
continue;
}
// 存储
if(flag){
s1[i++] = c;
}else{
s2[i++] = c;
}
}
// 串尾标记
s2[i] = '\0';
}
// 分治策略
void PrintPreorder(char* s1, int len1, char* s2, int len2){
if(len1 == 0) return;
// 获取根节点
char root = s2[len2 - 1];
printf("%c", root);
// 寻找根节点在中序遍历中的位置
int index = -1;
while(s1[++index] != root);
// 继续划分左右子树
PrintPreorder(s1, index, s2, index);
PrintPreorder(s1 + index + 1, len1 - index - 1, s2 + index, len1 - index - 1);
}
int main(){
// 这就是我学校OJ水平, 太真实了~~
char s1[20], s2[20];
int len1, len2;
// 读取 中序遍历、后序遍历序列
TravelToString(s1, s2);
len1 = strlen(s1);
len2 = strlen(s2);
// 分治
PrintPreorder(s1, len1, s2, len2);
return 0;
}
分治的时候要注意的就是 边界问题,传参的时候要仔细考虑考虑,避免出错~~
如果有看不懂的,私信我!!!
~^^
每天进步一点,加油!
END
网友评论