题目要求：
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format "left_index right_index", provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification:
For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input:91 62 3-1 -1-1 45 -1-1 -17 -1-1 8-1 -173 45 11 58 82 25 67 38 42Sample Output:58 25 82 11 38 67 45 73 42题目要求建立一棵给定结构的二叉搜索树，并且进行层序遍历。
因为给定了结构，因此不能采用一般的方法来创建这棵树，题目指定了采用数组存储，数组存储树的一个问题在于不容易判断树是不是空，以前使用链表存储树的时候，可以通过结点是否为NULL来判断，这里给出一种简单易行的办法。
【数组存储树的方法】
首先建立一个比树的结点个数多1的数组TempT，0位置存储数据-1，然后让树T从位置1开始存储，这样，让空树的索引为-1，当访问T[-1]的时候。实际访问的是TempT[0]，而这里存储的数据正好是-1.因此可以通过这样来防止地址越界和方便的的处理。
【元素插入的处理】
因为二叉搜索树的中序遍历是所有元素的升序，因此将要插入的所有元素进行排序，即可得到树的中序遍历结果。
观察数组索引的增加，是根、左、右的顺序进行的，也就是树的先序遍历，对于二叉搜索树，左侧的元素一定小于右侧，因此只需要设计一个计算左子树和右子树元素个数的函数，然后在中序遍历序列中截取，例如第一次截取，，0位置的元素左侧有5个元素，则第6个就是根，后面的就是右子树，然后递归的解决所有子树，完成插入。
【元素的层序遍历问题】
层序遍历和DFS基本是一样的，只需要一个队列，然后进行先序遍历即可。
AC代码如下：
#include <iostream>using namespace std;typedef struct TreeNode *Node;struct TreeNode{int left;int right;int data;};Node T;int *table;typedef struct Queue_struct *Queue;struct Queue_struct{TreeNode Elements[101];int front;int rear;};Queue createQueue(){Queue q = (Queue)malloc(sizeof(Queue_struct));q->front = q->rear = 0;return q;}void EnQueue(Queue q, TreeNode item){if (q->rear >= 100){return;}q->Elements[q->rear++] = item;}TreeNode DeQueue(Queue q){if (q->front == q->rear){exit(0);}return q->Elements[q->front++];}void preOrder(TreeNode node){if (node.left != -2){printf("%d ",node.data);preOrder(T[node.left]);preOrder(T[node.right]);}}void countNodes(TreeNode node, int* count){if (node.left != -2){(*count)++;countNodes(T[node.left], count);countNodes(T[node.right], count);}}int countChilds(TreeNode node){int count = 0;countNodes(node, &count);return count;}int compare(const void* a, const void* b){return *(int*)a – *(int*)b;}void InsetToBST(int start, int end, Node node){if (node->left != -2){int begin = start;int stop = start + countChilds(T[node ->left]);node->data = table[stop];InsetToBST(begin, stop – 1, T + node->left);begin = stop + 1;stop = begin + countChilds(T[node->right]);InsetToBST(begin, stop – 1, T + node->right);}}void MediaOrder(Node T){int count = 0;;Queue q = createQueue();EnQueue(q, T[0]);while (q->front != q->rear){TreeNode t = DeQueue(q);if (count == 0){count = 1;printf("%d", t.data);}else{printf(" %d", t.data);}if (T[t.left].data!=-1){EnQueue(q, T[t.left]);}if (T[t.right].data!=-1){EnQueue(q, T[t.right]);}}printf("\n");}int main(){int N;cin >> N;Node TempTree = (Node)malloc(sizeof(TreeNode)*(N+1));TempTree->left = -2;TempTree->right = -2;TempTree->data = -1;T = TempTree + 1;for (int i = 0; i < N; i++){Node node = T + i;node->data = 0;scanf("%d%d", &node->left, &node->right);}table = (int*)malloc(sizeof(int)*N);for (int i = 0; i < N; i++){scanf("%d", table + i);}qsort(table, N, sizeof(int), compare);InsetToBST(0, N – 1, T + 0);MediaOrder(T);return 0;}
学会技能是小智慧，学会做人是大智慧。
