首先,我们看看前序、中序、后序遍历的特性:
前序遍历:
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历:
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历:
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点
好了,先说说用前序遍历和中序遍历求后序遍历
假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf
前序遍历是先访问根节点,然后再访问子树的,而中序遍历则先访问左子树再访问根节点
那么把前序的 a 取出来,然后查找 a 在中序遍历中的位置就得到 dgb a echf
那么我们就知道 dgb 是左子树 echf 是右子树,因为数量要吻合
所以前序中相应的 dbg 是左子树 cefh 是右子树
然后就变成了一个递归的过程,具体代码如下:
#include <iostream>
#include <string>
using namespace std;
int find(const string &str, char c)
{
for (int i = 0; i < str.size(); ++ i)
if (c == str[i])
return i;
return -1;
}
bool PreMid(const string &pre, const string &mid)
{
if (pre.size() == 0)
return false;
if (pre.size() == 1)
{
cout << pre;
return true;
}
//根节点是第一个元素
int k = find(mid, pre[0]);
string pretmp = pre.substr(1, k);
string midtmp = mid.substr(0, k);
PreMid(pretmp, midtmp);
pretmp = pre.substr(k + 1, pre.size() - k - 1);
midtmp = mid.substr(k + 1, mid.size() - k - 1);
PreMid(pretmp, midtmp);
//变成后序遍历要最后输出节点的值
cout << pre[0];
}
int main()
{
string pre, mid;
while (cin >> pre >> mid)
{
PreMid(pre, mid);
cout << endl;
}
}
而已知后序遍历和中序遍历求前序遍历的过程差不多,但由于后序遍历是最后才访问根节点的
所以要从后开始搜索,例如上面的例子,后序遍历为 gbdehfca,中序遍历为 dgbaechf
后序遍历中的最后一个元素是根节点,a,然后查找中序中a的位置
把中序遍历分成 dgb a echf,而因为节点个数要对应
后序遍历分为 gbd ehfc a,gbd为左子树,ehfc为右子树,这样又可以递归计算了
其他一些附带的代码上面已经有,这里就不重复贴了,具体代码如下:
bool BackMid(const string &back, const string &mid)
{
if (back.size() == 0)
return false;
if (back.size() == 1)
{
cout << back;
return true;
}
//根节点是最后一个元素
int k = find(mid, back[back.size() - 1]);
//变成前序遍历要先输出节点的值
cout << back[back.size() - 1];
string backTmp = back.substr(0, k);
string midTmp = mid.substr(0, k);
BackMid(backTmp, midTmp);
backTmp = back.substr(k, back.size() - k - 1);
midTmp = mid.substr(k + 1, mid.size() - k - 1);
BackMid(backTmp, midTmp);
}
分享到:
相关推荐
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历.pdf
数据结构 C/C++ 数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历
二叉树已知前序和中序遍历,求后序遍历,C++代码已编译通过,可直接运行
C语言,数据结构课程,知道中序和后序遍历,画二叉树和写出前序遍历。
已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树; (2)证明构造正确(即分别以前序和中序遍历该树,将得到的结果与给出的序列进行比较)。 (3)对该二叉树进行后序遍历,...
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
只有二叉树中每个节点度为 2 或者 0 的时候,已知前序遍历序列和后序遍历序列,才能唯一地确定一颗二叉树,如果二叉树中存在度为 1 的节点时是无法唯一地确定一棵
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
1、深度优先遍历 2、广度优先遍历 3、求深度 4、已知二叉树前序中序,还原二叉树 5、已知前序和中序,求后序
js代码-二叉树迭代法后序遍历
C++源码,可在VC6.0环境下直接运行,核心代码非常经典,不到10行且易懂。
二叉搜索树(排序二叉树),树的遍历(前序、中序、后序)【数据结构和算法入门7】
已知前序中序 构造二叉树,并求后序遍历 判断是否为平衡二叉树
自己写的递归三种遍历,利用栈的非递归三种遍历。
二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。 比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先...