本文共 1026 字，大约阅读时间需要 3 分钟。
给出一个完全二叉搜索树的键值序列，要求输出层序输出
完全二叉搜索树的根节点是可以唯一确定的，所以一开始排序一下，再用dfs即可。这题我思路是想到了，但是生成根节点的地方写的有点问题，然后要输出层序是可以用dfs中序遍历再加一个数组直接输出的，这里可以学习一下。
#include #include #include #include #include #include #include #include #include #include #include #define lowbit(i) ((i)&(-i))using namespace std;const int INF = 0xfffff;const int maxn = 2055;int num[maxn],res[maxn];int n;void dfs(int l, int r,int pos) { if (l > r) return; int n = r - l + 1; int exp = log(n+1) / log(2); int last = n - (pow(2, exp) - 1); int root = l + (pow(2, exp - 1)-1) + min(last, (int)pow(2, exp - 1)); //cout << exp<<" "< < << endl; res[pos] = root; dfs(l, root-1,2*pos+1); dfs(root+1, r,2*pos+2);}int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } sort(num, num + n); dfs(0, n - 1,0); for (int i = 0; i < n-1; i++) printf("%d ", num[res[i]]); printf("%d\n", num[res[n - 1]]); return 0;}
转载于:https://www.cnblogs.com/seasonal/p/10343621.html