本文共 1525 字，大约阅读时间需要 5 分钟。
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
#include using namespace std;typedef long long ll;template struct BiNode{ DataType data; BiNode *lchild, *rchild; BiNode(DataType n){ data=n; lchild=NULL; rchild=NULL; }};template class BiTree{ public: BiTree() { int n,i; cin>>n; int *h,*z; h=new int[n]; z=new int[n]; for(i=0; i >h[i]; } for(i=0; i >z[i]; } root = Creat(h,z,n); } void LeverOrder(); //层序遍历二叉树private: BiNode *Creat(DataType *h,DataType *z,int n); //构造函数调用 BiNode *root; //指向根结点的头指针};template BiNode *BiTree ::Creat(DataType *h,DataType *z,int n){ if(n==0) return NULL; int k=0; while(h[n-1]!=z[k]){ k++; } BiNode *t=new BiNode (h[n-1]); t->lchild=Creat(h,z,k); t->rchild=Creat(h+k,z+k+1,n-1-k); return t;}int c=0;template void BiTree :: LeverOrder( ){ BiNode *Q[100], *q = nullptr; //顺序队列最多100个结点 int front = -1, rear = -1; //队列初始化 if (root == nullptr) return; //二叉树为空，算法结束 Q[++rear] = root; //根指针入队 while (front != rear) //当队列非空时 { q = Q[++front]; if(c==0){ cout << q->data; c=1; }else{ cout <<" "<< q->data; } if (q->lchild != nullptr) Q[++rear] = q->lchild; if (q->rchild != nullptr) Q[++rear] = q->rchild; }}int main( ){ BiTree asd; asd.LeverOrder(); return 0;}
转载地址：http://dtesz.baihongyu.com/