分析：输入二叉树的前序遍历、中序便利，求后序遍历
先建立这棵二叉树，然后递归的输出它的后续遍历即可。问题的关键在于如何建立这棵二叉树。在NOIP初赛中，经常有这样的题目。手算不算难，写成程序实现就需要编程的基本功了。
采取递归的方法建立二叉树。首先取前序遍历的首元素当作二叉树的跟，当前元素为根。把前序遍历中的当前元素当作中序遍历的分割点，中序便利分割点前面的元素一定在当前元素的左子树，分割点后面元素一定在当前元素的右子树。然后加入下一个顶点，再把它当作分割点。如此递归的进行，直到二叉树建立完成。
基本框架
调用 create(0,元素总数-1,根节点);
void create(long L,long R,Node *C)
{
E=下一个元素();
if (没有下一个元素)
return;
else
{
if (E在C左边)
create(L,分割点-1,C->左子树);
if (E在C右边)
create(分割点+1,R,C->右子树);
}
}
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: heritage LANG: C++
Compiling… Compile: OK
Executing… Test 1: TEST OK [0.011 secs, 2840 KB] Test 2: TEST OK [0.000 secs, 2840 KB] Test 3: TEST OK [0.000 secs, 2840 KB] Test 4: TEST OK [0.000 secs, 2840 KB] Test 5: TEST OK [0.000 secs, 2844 KB] Test 6: TEST OK [0.000 secs, 2840 KB] Test 7: TEST OK [0.000 secs, 2844 KB] Test 8: TEST OK [0.011 secs, 2844 KB] Test 9: TEST OK [0.000 secs, 2840 KB]
All tests OK.
YOUR PROGRAM (‘heritage’) WORKED FIRST TIME! That’s fantastic – and a rare thing. Please accept these special automated congratulations.
/*
ID: cmykrgb1
PROG: heritage
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
class Node
{
public:
Node()
{
left=right=0;
letter=0;
position=0;
}
Node *left,*right;
char letter;
long position;
};
ifstream fi("heritage.in");
ofstream fo("heritage.out");
Node *root;
char fs[26],ms[26];
long cnt=0,cur=1;
void scan(Node *N)
{
if (N->left) scan(N->left);
if (N->right) scan(N->right);
fo << N->letter;
}
void init()
{
char c;
int i;
while (c!=10 && c!=13)
ms[cnt++]=c=fi.get();
cnt--;
while (c==10 && c==13) c=fi.get();
for (i=0;i<cnt;i++)
fs[i]=fi.get();
root=new Node;
root->letter=fs[0];
for (i=0;i<cnt;i++)
if (ms[i]==fs[0])
{
root->position=i;
break;
}
}
char getnextelement()
{
if (cur>=cnt)
return -1;
else
return fs[cur++];
}
void create(long L,long R,Node *C)
{
char E;
int i;
bool found;
while (1)
{
found=false;
E=getnextelement();
if (E==-1)
return;
else
{
for (i=L;i<=C->position-1;i++)
if (ms[i]==E)
{
C->left=new Node;
C->left->letter=E;
C->left->position=i;
create(L,C->position-1,C->left);
found=true;
break;
}
if (!found)
for (i=C->position+1;i<=R;i++)
if (ms[i]==E)
{
C->right=new Node;
C->right->letter=E;
C->right->position=i;
create(C->position+1,R,C->right);
found=true;
break;
}
if (!found)
{
cur--;
return;
}
}
}
}
void print()
{
scan(root);
fo << endl;
fi.close();
fo.close();
}
int main()
{
init();
create(0,cnt-1,root);
print();
return 0;
}
上次修改时间 2017-02-03