某年研究生复试题之二

根据二叉树的先序和中序序列，设计算法重构出这棵二叉树。（40分）
已知一棵二叉树的先序遍历序列是ABECDFGHIJ，中序遍历序列是EBCDAFHIGJ，请设计一个算法，将这棵二叉树的结构重构出来，并且输出它的三种深度优先遍历的结果（即先序、中序和后序序列）。
====================================
都是挺基础的题目嘛~
先序遍历是NLR，中序遍历是LRN
所以给了一个先序序列，比如题目中那个，那第一个元素（A）肯定就是那个N啦
然后再中序序列中找到N，就能把中序序列劈成两段了，(LEFT)N(RIGHT)
然后就递归，弄到到底了为止，嘿嘿:)
不过自己实现起来还是挺蛋疼的，能力有限唉唉唉
输出只搞了个后序的，其他类似反正。
====================================

#include
#include
#include
#include
using namespace std;
struct Node
{
char value;
Node *pLeft;
Node *pRight;
Node()
{
pLeft = NULL;
pRight = NULL;
}
};
void splitLNR(queue input, queue &left, queue &right, char N)
{
bool flag = false;
while(!input.empty())
{
char currVal = input.front();
if(currVal == N)
{
flag = true;
input.pop();
continue;
}
if(!flag)
{
left.push(currVal);
}
else
{
right.push(currVal);
}
input.pop();
}
}
void splitNLR(queue input, queue &left, queue &right, int pos)
// RIght subseries starts at position = pos
{
int count = 0;
while(!input.empty())
{
char currVal = input.front();
if(count == 0)
{
input.pop();
count++;
continue;
}
else if(count < pos) { left.push(currVal); } else { right.push(currVal); } input.pop(); count++; } } void printLRN(Node *root) { if(root == NULL) return; printLRN(root->pLeft);
printLRN(root->pRight);
cout << root->value << " "; } void run( queue A, queue B, Node* root)
//A: 先序， B：中序
{
if(A.empty())
return;
char N = A.front();
root->value = N;
queue leftB, rightB, leftA, rightA;
splitLNR(B, leftB, rightB, N);
splitNLR(A, leftA, rightA, leftB.size() + 1);
if(leftB.empty() && rightB.empty())
{
//N is the only element
return;
}
if(!leftA.empty())
{
Node *newNode = new Node;
root->pLeft = newNode;
run(leftA, leftB, newNode);
}
if(!rightA.empty())
{
Node *newNode = new Node;
root->pRight = newNode;
run(rightA, rightB, newNode);
}
}
int main()
{
queue inputA, inputB;
char *cNLR = "ABECDFGHIJ";
char *cLNR = "EBCDAFHIGJ";
int i;
for(i=0; i