本文正體字版由OpenCC轉換
分析：輸入二叉樹的前序遍歷、中序便利，求後序遍歷
先建立這棵二叉樹，然後遞歸的輸出它的後續遍歷即可。問題的關鍵在於如何建立這棵二叉樹。在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