Beyond the Void

调用 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->右子树);
	}
}

/*
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;
}