树的层次遍历

#include<iostream> #include<queue> using namespace std; //结点权值作为结点编号 int postOrder[31]; //后序遍历结点 int inOrder[31]; //中序遍历结点 int leftNodes[31]; //保存某结点的左子树编号 int rightNodes[31]; //保存某结点的右子树编号 //根据inOrder[L1]到inOrder[R1] 和postOrder[L1]到postOrder[R1]的结点编号 来构建树 //返回根节点 int buildTree(int L1, int R1, int L2, int R2){ if (R1 < L1) //空树 return -1; int root = postOrder[R2]; //后序遍历序列最后一个结点一定是根结点 int p =0; while (inOrder[p] != root) //找到中序遍历序列中对应哪个根结点的结点 p++; int count = p - L1; //左子树结点总数 //p是中序序列的根，从L1到p-1为左子树，对应的后续序列的从L2到L2+count-1 leftNodes[root] = buildTree(L1, p- 1, L2, L2 + count - 1); //中序序列从p+1到R1为右子树，对应的后续序列从L2+count到R2 - 1 ！！因为根节点已经去掉了！！ rightNodes[root] = buildTree(p + 1, R1, L2+count, R2-1); return root; } //层序遍历 //传了个N进去是因为输出格式控制 = = void printVex(int root,int N){ queue<int> q; q.push(root); while (q.size()){ int vex = q.front(); if (N==1) cout << vex; else cout << vex<<" "; q.pop(); if (leftNodes[vex] != -1) q.push(leftNodes[vex]); if (rightNodes[vex] != -1) q.push(rightNodes[vex]); N--; } } int main(){ int N; cin >> N; int index = 0; for (int i = 1; i <= N; i++){ int vex; cin >> vex; postOrder[index++] = vex; } index = 0; for (int j = 1; j <= N; j++){ int vex; cin >> vex; inOrder[index++] = vex; } int root = buildTree(0, N - 1, 0, N - 1); printVex(root,N); return 0; }