解法一:建树
#include <iostream> #include <string> #include<algorithm> #include<queue> #include<string.h> using namespace std; typedef int ElementType; typedef struct TNode* Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; }; int num[1010] = { 0 }; BinTree NewNode(ElementType X) { BinTree tmp = (BinTree)malloc(sizeof(struct TNode)); tmp->Data = X; tmp->Left = tmp->Right = NULL; return tmp; } BinTree buildCBT(int begin,int end) { BinTree root; int nodes = end - begin + 1; int n = 1; if (!nodes) return nullptr; if (nodes == 1) { root = new TNode(); root->Data = num[end]; root->Left = root->Right = nullptr; } else { while (2 * n <= nodes) n *= 2; int tmp = nodes - n + 1;//得到最后一层结点的数量 if (tmp <= n / 2)//只在左子树 n = n / 2 - 1;//右子树结点数量 else n = n / 2 - 1 + (tmp - n / 2);//右子数结点数量 root = new TNode(); root->Data = num[end - n]; root->Left = buildCBT(begin, end - n - 1); root->Right = buildCBT(end - n +1, end); } return root; } void LevelOrder(BinTree CBT,int N) { BinTree tmp = CBT; queue<BinTree> q; if (CBT) { q.push(tmp); while (!q.empty()) { tmp = q.front(); if (tmp->Left) q.push(tmp->Left); if (tmp->Right) q.push(tmp->Right); q.pop(); cout << tmp->Data; if (N-1 > 0) { cout << " "; N--; } } } } int main() { int N; int i; BinTree CBT = NULL; cin >> N; for (i = 0; i < N; i++) { cin >> num[i]; } sort(num, num + N); CBT = buildCBT(0, N-1); LevelOrder(CBT, N); return 0; }解法二：完全二叉树中序与层序遍历的关系 对完全二叉树的中序遍历结果从root=0做中序遍历可以得到层序遍历结果。参观大佬代码
#include <iostream> #include <algorithm> using namespace std; int in[1010], level[1010], n, t = 0; void inOrder(int root) { if (root >= n) return ; inOrder(root * 2 + 1); level[root] = in[t++]; inOrder(root * 2 + 2); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &in[i]); sort(in, in + n); inOrder(0); printf("%d", level[0]); for (int i = 1; i < n; i++) printf(" %d", level[i]); return 0; }