PAT A1115 Counting Nodes in a BST (30point(s))

Scroll Down

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

题意

解答

#include<iostream>
#include<queue>

using namespace std;

struct Node{
	int key;
	Node *lchild, *rchild;
};

void Insert(Node *&root, int key) 
{
	if (root == NULL) {
		root = new Node();
		root->key = key;
		return;
	}
	if (key <= root->key) Insert(root->lchild, key);
	else Insert(root->rchild, key);
}

int main()
{
	int key, n;
	cin >> n;
	Node *root = NULL;
	for(int i=0;i<n;i++){
		cin >> key;
		Insert(root, key);
	}
	queue<Node*> q;
	Node* p = NULL;
	int currentC = 1, nextC = 0, i = 0, preC = 0;
	int last2 = 0, last1 = 0;
	q.push(root);
	while (!q.empty()) {
		p = q.front();
		q.pop();
		i++;
		if (p->lchild) {
			q.push(p->lchild);
			nextC++;
		}
		if (p->rchild) {
			q.push(p->rchild);
			nextC++;
		}
		if (i == currentC) {
			if (nextC != 0) {
				preC = currentC;
				currentC = nextC;
			}
			nextC = 0;
			i = 0;
		}
	}
	printf("%d + %d = %d", currentC, preC, preC + currentC);
	return 0;
}