首页 > 代码库 > [复试机试]已知中序遍历和后序遍历,求前序遍历
[复试机试]已知中序遍历和后序遍历,求前序遍历
#include<iostream> #include<stack> #include<string> using namespace std; typedef struct no { char data; struct no *lchild,*rchild; }*node; void create(node &root,string sa,string sb)///根据中/后序遍历,建树 { if(sa.length() == 0) return ; root = new no(); root->data = http://www.mamicode.com/sb[sb.length()-1]; root->lchild = root->rchild = NULL; int len = sa.length(); string inl,inr,pol,por; for(int i = 0;i < len;i ++){ if(sa[i] == root->data){ inr = sa.substr(i+1,len-i-1); inl = sa.substr(0,i); break; } } //cout<<inl<<"----"<<inr<<endl; int l1 = inl.length(),l2 = inr.length(); pol = sb.substr(0,l1);///小心啊,多+1,少+1,导致半个小时找bug por = sb.substr(l1,l2); //cout<<pol<<"******"<<por<<endl; create(root->lchild,inl,pol);///递归建树 create(root->rchild,inr,por); } void pre(node & sa){ if(sa != NULL){ cout<<sa->data; pre(sa->lchild); pre(sa->rchild); } } int main() { string in,post; cout<<"输入中缀表达式:"<<endl; cin>>in; cout<<"输入后缀表达式:"<<endl; cin>>post; node head; head=new no(); create(head,in,post); cout<<"前缀表达式为:"<<endl; pre(head); cout<<endl; }
[复试机试]已知中序遍历和后序遍历,求前序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。