C++实现
#include <iostream>
#include <queue>
using namespace std;
class Tree
{
public:
Tree(char *in, char *post, int len);
char data;
Tree *Lchild;
Tree *Rchild;
void LevelReverse(int (*func)(int ch));
};
Tree::Tree(char *in, char *post, int len)
{
Lchild = Rchild = NULL;
data = post[len - 1];
if (len > 1)
{
int i = 0;
while (in[i] != data)
{
i++;
}
if (i > 0)
{
Lchild = new Tree(in, post, i);
}
if (len - 1 - i > 0)
{
Rchild = new Tree(in + i + 1, post + i, len - i - 1);
}
}
}
void Tree::LevelReverse(int (*func)(int ch))
{
//通过队列，用广搜实现按层遍历
queue<Tree *>
treeQueue;
func(data);
treeQueue.push(this);
while (!treeQueue.empty())
{
if (treeQueue.front()->Lchild)
{
func(treeQueue.front()->Lchild->data);
treeQueue.push(treeQueue.front()->Lchild);
}
if (treeQueue.front()->Rchild)
{
func(treeQueue.front()->Rchild->data);
treeQueue.push(treeQueue.front()->Rchild);
}
treeQueue.pop();
}
}
int main()
{
char in[1000], post[1000];
gets(in);
gets(post);
Tree root(in, post, strlen(in));
root.LevelReverse(putchar);
putchar('\n');
return 0;
}
