网络推广网站,网站淘宝客 没备案怎么做,黑白灰网站,专业的网站优化公司1. 已知中序和后序#xff0c;求前序
1.1 题目
题目描述#xff1a;给一棵二叉树的中序和后序排列#xff0c;求它的先序排列。
输入描述#xff1a;共两行#xff0c;均为大写字母组成的字符串#xff0c;分别表示一棵二叉树的中序和后序
输入#xff1a;BADC BDCA…1. 已知中序和后序求前序
1.1 题目
题目描述给一棵二叉树的中序和后序排列求它的先序排列。
输入描述共两行均为大写字母组成的字符串分别表示一棵二叉树的中序和后序
输入BADC BDCA
输出ABCD
1.2 思想
中序排列 B D A E C F
后续排列D B E F C A
1. 根据后续遍历最后一个元素为这个树的根
2. 根据中序遍历根节点会把整个序列分成两部分左边为左子树右边为右子树
3. 在左子树和右子树中又可以进行递归处理方法和刚开始一样
1.3 模拟实现
#includeiostream
using namespace std;
string s1,s2;//操作的范围用l1,r1,l2,r2标记
void dfs(int l1, int r1, int l2, int r2)
{//递归结束if (l1 r1) return;//先序遍历先输出根节点cout s2[r2];//根据后续遍历从中序遍历中找到根节点int q l1;while (s1[q] ! s2[r2]) q;//对左右子树递归注意标记的范围dfs(l1, q - 1, l2, l2 q - l1 - 1);dfs(q 1, r1, l2 q - l1, r2-1);
}int main()
{cin s1 s2;//先操作最初序列dfs(0, s1.size()-1, 0, s2.size()-1);return 0;
}
2. 已知中序和先序求后序
2.1 题目
题目描述给一棵二叉树的中序和先序排列求它的后序排列。
输入描述共两行均为大写字母组成的字符串分别表示一棵二叉树的中序和先序
输入ABEDFCHG CBADEFGH
输出AEFDBHGC
2.2 思想
中序排列 ABEDFCHG
先续排列 CBADEFGH
1. 根据先续遍历第一个元素为这个树的根
2. 根据中序遍历根节点会把整个序列分成两部分左边为左子树右边为右子树
3. 在左子树和右子树中又可以进行递归处理方法和刚开始一样
2.3 模拟实现
#includeiostream
using namespace std;
string s1, s2;void dfs(int r1, int l1, int r2, int l2)
{//递归结束条件if (r1 l1) return;//找到中序排列的根节点int p r1;while (s1[p] ! s2[r2]) p;//递归注意左、右子树的下标位置dfs(r1, p - 1, r2 1, r2 p - r1 );dfs(p 1, l1, r2 p - r11, l2);cout s2[r2];}int main()
{cin s1 s2;//标记初始序列dfs(0, s1.size() - 1, 0, s2.size()-1);return 0;
}
