Question

4、已知一颗二叉树S的前序遍历和中序遍历序列,请编程输出二叉树S的后续遍历序列。 需求 文字描述算法思路

尤其 是树如何确定那部分如何编程！原理都懂 程序不会写！！

Answer 1

其实原理很简单的，你是搞Noi的吧？
二叉树的因为它特殊的体系，根是1（算是第一层），第二层是2,3，第三层是4 5 6 7 那么用2^n就可以限制和确定每个叶子节点的位置，用一维数组就可以了。循环控制上没什么难度，自己实现就OK。
接下来，如果只说遍历的话，这里写个伪代码，h代表当前根，a代表左节点，b代表右，f是递归函数，前序是这样的
write（h）；
f（a）；
f（b）；
中序就是：
f（a）；
write（h）；
f（b）；
根据这个 你可以自己画一个二叉树来实际的走一下，因为这样打印出来只会改变左节点打印的位置（他们会随机的插到右节点的中间），然后你就可以确定了。

最后把你模拟程序走的步骤按照想法实现，没问题的……

Answer 2

你好，这是清华大学计算机专业某一年的复试题目，我在杭电的ACM网站上给你找到了AC代码，
如果你仔细研读，应该可以解决你的问题，但是我想说，这绝对是一个难题！

#include<iostream>
using namespace std;

int len;
struct BTreeNode
{
int data;
BTreeNode*lchild;
BTreeNode*rchild;
BTreeNode*parent;
};
struct BinaryTree
{

BTreeNode*Parent;
int leaf,num;
int Degree_ONE_CNT;
int Degree_TWO_CNT;
void init();
// void Destroy();
void GetLString(string str,char Sep,string& p,string& mid);
BTreeNode*Root;
BinaryTree(){init();}
BTreeNode*CreateBypremid(int* pre,int* in,int n);
void AfterOrder(BTreeNode*root);
void Get_Degree();

};
void BinaryTree::Get_Degree()
{
// cout<<n<<" "<<leaf<<" "<<Degree_ONE_CNT<<" "<<Degree_TWO_CNT<<endl;
}
void BinaryTree::init()
{
Parent=new BTreeNode;
Root=new BTreeNode;
Parent->lchild=NULL;
Parent->rchild=NULL;
Root->lchild=NULL;
Root->rchild=NULL;
Root->parent=NULL;
leaf=0;
Degree_ONE_CNT=0;
Degree_TWO_CNT=0;
num=0;

}
void BinaryTree::AfterOrder(BTreeNode*root)
{
int IsLeaf=0;
if(root->lchild != NULL)
{
IsLeaf++;
AfterOrder(root->lchild);
}
if(root->rchild != NULL)
{
IsLeaf++;
AfterOrder(root->rchild);
}
if(IsLeaf == 0)
{
leaf++;
}
else if(IsLeaf == 1)
{
Degree_ONE_CNT++;
}
else if(IsLeaf == 2)
{
Degree_TWO_CNT++;
}
num++;
if(num == len)
cout<<root->data<<endl;
else
cout<<root->data<<' ';

}
BTreeNode* BinaryTree::CreateBypremid(int* pre,int* in,int n)
{

if( n == 0) return NULL;
int root=pre[0];
int i;
for(i=0;i<n;i++)
{
if(in == root) break;
}
int *preLeft=pre+1;
int *preRight=pre+i+1;
int *inLeft=in;
int *inRight=in+i+1;
BTreeNode*left =CreateBypremid(preLeft,inLeft,i);
BTreeNode*right =CreateBypremid(preRight,inRight,n-i-1);
BTreeNode*p =new BTreeNode;
p->data=root;
p->lchild=left;
p->rchild=right;
if(n == len)Root=p;
return p;
}
int main()
{

while(true)
{

if(!(cin>>len)) break;
int *pre=new int [len];
int *in=new int [len];
for(int i=0; i<len; i++)
{
cin>>pre;
}
for(int j=0; j<len; j++)
{
cin>>in[j];
}
BinaryTree BT;
BT.CreateBypremid(pre,in,len);
BT.AfterOrder(BT.Root);
}

return 0;
}