1064. Complete Binary Search Tree (30)

2019-11-08 18:29:29

字体：大中小

来源：转载

供稿：网友

先对输入数据排序。然后用中序建立CBT（用数组存储节点），最后层序输出即可

#include<iostream>#include<vector>#include<algorithm>#include<queue>#PRagma warning(disable:4996)using namespace std;int N;int cnt =0;vector<int> sq,resault;//sq为排好序的输入，resault存储CBT，为方便讨论，resault[0]为空void InorderTraverse(int index){ if (index * 2 <= N) InorderTraverse(index * 2); resault[index] = sq[cnt++]; if (index * 2 + 1 <= N)InorderTraverse(index * 2 + 1);}int main(){ cin >> N; sq.resize(N); for (int i = 0;i < N;i++) scanf("%d", &sq[i]); sort(sq.begin(), sq.end()); resault.resize(N+1); InorderTraverse(1); queue<int> ceng; ceng.push(1); int flag = 0; while (!ceng.empty()) { int now = ceng.front(); if (flag == 0) { printf("%d", resault[now]);flag = 1; } else printf(" %d", resault[now]); ceng.pop(); if (now * 2 <= N) ceng.push(now * 2); if (now * 2 + 1 <= N) ceng.push(now * 2 + 1); } cout << endl;}

上一篇：POJ1222-EXTENDED LIGHTS OUT-反转

下一篇：c_str()