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.
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:
|
1 2 3 4 5 6 7 8 9 10 11 |
9 1 6 2 3 -1 -1 -1 4 5 -1 -1 -1 7 -1 -1 8 -1 -1 73 45 11 58 82 25 67 38 42 |
Sample Output:
|
1 |
58 25 82 11 38 67 45 73 42 |
一道 30 分的水题，首先将数字序列按增序排序，然后用中序遍历对每个节点编号，这样对这个 BST 中序遍历的结果就与该序列一致了（建立了映射关系），然后直接层序遍历就可以了。
（还有一种思路就是，根据某个节点的左子树的节点个数来确定某个节点的数值为多少，分治的思路，类似快排的主元确定的方法）
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include<stdio.h> #include<stdlib.h> typedef struct tree_ { int number; struct tree_ *left; struct tree_ *right; } tree; typedef struct queue_ { int size; int capacity; int front; int rear; void **data; } queue; #define is_queue_empty(X) (!((X)->size)) queue *init_queue(int n) { queue *temp; temp=(queue *)malloc(sizeof(queue)); temp->size=0; temp->capacity=n; temp->front=0; temp->rear=-1; temp->data=(void **)malloc(n*sizeof(void *)); return temp; } int enqueue(queue *q,void *data) { if(q->size==q->capacity) { return 1; } q->size++; q->rear=(q->rear+1)%q->capacity; q->data[q->rear]=data; return 0; } int dequeue(queue *q,void **data) { if(q->size==0) { *data=NULL; return 1; } q->size--; *data=q->data[q->front]; q->front=(q->front+1)%q->capacity; return 0; } int delete_queue(queue *q) { free(q->data); free(q); return 0; } void level_order(tree *t,int *sequence) { queue *q; tree *temp; int flag=0; q=init_queue(10); enqueue(q,t); while(!is_queue_empty(q)) { dequeue(q,(void **)&temp); if(flag==0) { printf("%d",sequence[temp->number]); flag=1; } else { printf(" %d",sequence[temp->number]); } if(temp->left!=NULL) { enqueue(q,temp->left); } if(temp->right!=NULL) { enqueue(q,temp->right); } } printf("\n"); } void in_order_r(tree *t,int *count) { if(t==NULL) { return ; } in_order_r(t->left,count); t->number=*count; (*count)++; in_order_r(t->right,count); } int compare(const void *a,const void *b) { return *(int *)a-*(int *)b; } int main() { tree t[100]; int i,n,left,right,sequence[100],count=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&left,&right); t[i].left=left==-1?NULL:t+left; t[i].right=right==-1?NULL:t+right; } for(i=0;i<n;i++) { scanf("%d",sequence+i); } qsort(sequence,n,sizeof(int),compare); in_order_r(t,&count); level_order(t,sequence); } |