C
/ / B G
/ \ /
A D H
/ E F
第一行: 树的中序遍历
第二行: 同样的树的前序遍历
单独的一行表示该树的后序遍历。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; //前序:根左右 //中序:左根右 //后序:左右根 //其实大家可以这么记忆,前中后对应的其实是根所在的位置 //脑袋里有画面了就不会忘了哈哈哈 string a,b;//a是前序,b是中序 void work(string a,string b) { if(a.empty()) return ; char root=a[0]; //取到前序序列的首字母,即根节点 int k=b.find(root); //找到中序序列中根节点的位置 a.erase(a.begin()); //删去前序序列中的根节点 string leftpre=a.substr(0,k); //从0开始切割k个 string rightpre=a.substr(k); //从k开始切割到最后 string leftinor=b.substr(0,k); //从0开始切割k个 string rightinor=b.substr(k+1); //从k+1开始切割到最后 work(leftpre,leftinor);//先左子树 work(rightpre,rightinor);//再右子树 printf("%c",root); } int main() { cin>>b>>a; work(a,b); putchar(‘\n‘); return 0; }
原文:https://www.cnblogs.com/zust-lms/p/12650668.html