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 or equal to the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.
Output Specification:
For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:
n1 + n2 = n
where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.
Sample Input:
|
1 2 |
9 25 30 42 16 20 20 35 -5 28 |
Sample Output:
|
1 |
2 + 4 = 6 |
偷懒写了递归版……
感觉新增的 1108 – 1105 都有点水……
代码如下：
|
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 |
#include<stdio.h> #include<stdlib.h> int result[2],bottom=0; typedef struct tree_ { int num; int level; struct tree_ *left; struct tree_ *right; } tree; tree *insert(tree *root,int num,int level) { if(level>bottom) { bottom=level; } if(root==NULL) { root=(tree *)malloc(sizeof(tree)); root->left=NULL; root->right=NULL; root->num=num; root->level=level; return root; } if(root->num<num) { root->right=insert(root->right,num,level+1); } else { root->left=insert(root->left,num,level+1); } root->level=level; return root; } void search(tree *root) { if(root==NULL) { return ; } if(root->level==bottom) { result[1]++; } if(root->level+1==bottom) { result[0]++; } search(root->left); search(root->right); return ; } int main() { int i,n,num; tree *root=NULL; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&num); root=insert(root,num,0); } search(root); printf("%d + %d = %d\n",result[1],result[0],result[0]+result[1]); } |