二叉树遍历

#include<iostream>
#include<string>
using namespace std;
struct node//定义一个二叉树的节点信息，此节点包含两个指针和一个字符
{
	node* lchid;//指向左孩子
	node* rchid;//指向右孩子
	char c;
}tree[55];
string f,m;//定义string类保存输入的两个序列
int cnt; //下标，用来标记新创建节点
node* creat()//创建新的节点返回的是指向这个新节点的指针
{
	
	tree[cnt].lchid = tree[cnt].rchid = NULL;
	return &tree[cnt++];
}
void postorder(node*T)//后序遍历，函数参数为指向根节点的指针
{
	if (T->lchid != NULL)//左孩子不空，则一直递归调用函数遍历到左孩子为空，然后一层一层回溯
		postorder(T->lchid);
	if (T->rchid != NULL)//右孩子不空，则一直递归调用函数遍历到右孩子为空，然后一层一层回溯
		postorder(T->rchid);
	cout << T->c;//打印节点字符信息
}
node* bf(int s1, int e1, int s2, int e2)//递归还原建造二叉树
{
	node* ret = creat();//一个新的节点指针指向新创建的节点；
	ret->c = f[s1];//节点的值为前序遍历的范围内的第一个节点的节点
	int rootx;
	for (int j = s2; j <=e2; j++)//找到这个节点在中序遍历中的位置
	{
		if (m[j] == f[s1])
		{
			rootx = j;
			break;
		}
	}
	if (rootx != s2)//如果这个位置不是在中序遍历范围的左端点,即意味着它有左孩子
	{
		ret->lchid = bf(s1 + 1, s1 + rootx - s2, s2, rootx - 1);//则，刚创建的ret的左孩子指针指向下一个递归建造的节点，当递归跳出当前函数时，
	}//由return ret这句函数返回这个节点信息，然后被ret->lchid指向，完成建立
	if (rootx != e2)//同理
	{
		ret->rchid = bf(s1 + rootx - s2+1, e1, rootx+1, e2);//同时注意这里的遍历范围，其实写s1+1，e1在有些没啥时间复杂度要求的地方可以，但是有要求就要按照代码中给出的范围写，不然会超时
	}
	return ret;
}
int main()
{
	while (cin >> f >> m)
	{
		cnt = 0;
		int len1 = f.length();
		int len2 = m.length();
		node* t = bf(0, len1-1, 0, len2-1);//一开始的遍历范围，前序:0-len-1,后：0-len-2;
		postorder(t);
		cout << endl;
	}
}