CBT

CBT"/>

CBT

Tips：

对于一个完全二叉树的层序遍历而言，其中的任何一个结点的编号为x（根结点编号为1），其左孩子结点编号为2x，右孩子结点编号为2x+1。而中序遍历就是将所有元素由小到大排列。

今天在PAT上做的一个题目（A1064：Complete Binary Search Tree），题目是给定一组数据，求出其CBT的层序遍历。

即先虚构一个CBT，然后中序遍历这个CBT（一定为顺序结构），然后从最左到最右依次填写数据的最小值到最大值（现将这组数据由小到大依次排列）。

下面即为代码部分：

#define maxn 1000
int n;
int num = 0;struct Node {int data;//int now;int child_l;int child_r;
}node[maxn],level_order[maxn];bool comp(Node a, Node b) {return a.data < b.data;
}void in_order(int root) {if (root > n) return;in_order(2 * root);level_order[root - 1].data = node[num++].data;in_order(2 * root + 1);return;
}int main(){scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &node[i].data);sort(node, node + n, comp);in_order(1);for (int i = 0; i < n; i++) {printf("%d ", level_order[i].data);}system("pause");return 0;
}