1115 Counting Nodes in a BST (30分)

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:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

题目描述：二叉搜索树的特点有：

1）左子结点的值小于或等于根节点的值

2）右子结点的值大于根节点的值

3）所有左子树和右子树都是一个二叉搜索树

现在给出一组数，插入二叉搜索树中，求倒数第一层、倒数第二层的结点数，n1和n2，最后输出n1+n2。

解题思路：利用结构体建一棵二叉搜索树，再利用bfs将树的每一层结点分别存入vector数组中，很快就能得到结果了。写程序要有意识的将程序分块，不能将所有代码都写在主程序。

#include<bits/stdc++.h>
using namespace std;
int n, k;
const int maxn = 1e4+5;
vector<int> v[maxn];
struct node{
	int num;
	node *l, *r;
	node(){
		l = r = NULL;
	}
};
node* build(node *tree, int x){
	if(tree==NULL){
		tree = new node();
		tree->num = x;
		tree->l = tree->r = NULL;
	}
	else if(tree->num<x){
		tree->r = build(tree->r,x);
	}
	else tree->l = build(tree->l,x);
	return tree;
}

void bfs(node *tree){
	int cnt = 0;
	queue<pair<node*,int> > q;
	pair<node*,int> t, tt;
	t.first = tree;
	t.second = 0;
	q.push(t);
	while(!q.empty()){
		t = q.front(); q.pop();
		cnt = t.second;
		v[t.second].push_back(t.first->num);
		if(t.first->l!=NULL){
			tt.first = t.first->l;
			tt.second = t.second+1;
			q.push(tt);
		}
		if(t.first->r!=NULL){
			tt.first = t.first->r;
			tt.second = t.second+1;
			q.push(tt);
		}
	}
	int n1 = v[cnt].size(), n2 = v[cnt-1].size();
	printf("%d + %d = %d\n", n1, n2, n1+n2);
}

int main()
{
	node *tree = NULL;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &k);
		tree = build(tree,k);
	}
	bfs(tree);
	return 0;
}