189 8069 5689
在已知中序的前提下，任意知道前序或后序皆可得到唯一的二叉树
假若一个中序序列为：ABEDFCHG
又知前序序列为：CBADEFGH
由于前序序列是按照根左右来进行遍历的
所以前序序列的第一个一定是二叉树的根结点！
即：
然后中序序列是按照左根右来进行遍历的
所以中序序列的根一定将左右子树进行了分离
先不管ABEDF哪个是根，反正他们都是作为C的左子树的一个结点
HG则作为C的右子树
即：
接下来前序序列的下一个又是一个子根，所以重复前面的操作得到：
接下来在中序中A的左右已经没有更后的结点了也就说明它没有左右子树(属于叶子结点)
在中序中(ABEDFCHG), A的左边没有元素，A的右边是B，但是B是在前面的，
所以B不会作为A的子树，故A的左右都没有元素，得出A是叶子结点的结论最终成图：
首先假若有一个中序序列为：ABEDFCHG
又知前序序列为：CBADEFGH
那么我们先分析后序遍历的需求，后序是根据左右根来遍历的
所以我们先要找根的左子树结点，再根据左子树结点找其左子树结点，直到左子树结点为空
然后再找返回去根节点找其右子树，重复上述内容(找右子树的左子树)
所以根据我们的分析得出，这个题可以使用递归来解决
递归思想：把规模大的、较难解决的问题变成规模小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
三个使用条件：
1、可以将一个大问题转为小问题
2、可以通过转化过程使得问题得到解决
3、有一个明确的结束递归的条件根据上图我们可以写出代码
首先找出根节点(第一个根节点是C)
然后左子树是：ABEDF，右子树为HG
然后再根据左子树中找到根节点B(通过中序的下一位来判断)
我们可以每记录了一次根节点之后可以将对应的根节点清除，这样后面就不用特别处理了
这里提供一种清除方法
清除前序遍历的根节点：tpreor.erase(tpreor.begin());
清除中序遍历的根节点：tinfor.erase(temp, 1);
( temp 为 tinfor.find(root) -->root为每一次的根节点 root = tpreor[0]);
又或者可以利用下标来进行操作，只不过使用清除的方法更加明显实质一点
利用下标的话就不用进行清除了，每次只需要改变下标即可然后在遍历左子树来重复前面的操作
直到左子树都执行结束后再对右子树进行同样的操作
具体实现为：
traversal(left_tpreor, left_tinfor);
traversal(right_tpreor, right_tinfor);
若左右子树都遍历结束后再进行输出根节点
cout<< root; //因为是后序遍历(只有左子树和右子树到头了再输出根结点)完整代码：
#include#includeusing namespace std;
string preor, infor;
//前序后序
void traversal(string tpreor, string tinfor){
if(tinfor.empty()) return; //这时候中序的元素都找完了，就可以返回程序了
char root = tpreor[0]; //取根节点
int temp = tinfor.find(root); //从中序中找根结点
tpreor.erase(tpreor.begin()); //清除前序最前面的字符
tinfor.erase(temp, 1); //清除中序的根结点
string left_tpreor = tpreor.substr(0, temp); //记录左子树
string left_tinfor = tinfor.substr(0, temp);
string right_tpreor = tpreor.substr(temp); //记录右子树
string right_tinfor = tinfor.substr(temp);
traversal(left_tpreor, left_tinfor); //操作左子树
traversal(right_tpreor, right_tinfor); //操作右子树
cout<< root; //左子树和右子树都遍历完了后就可以输出了
}
int main()
{
cin >>infor >>preor;
traversal(preor, infor);
return 0;
} 未完待续…
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧