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 (≤) which is the size of the input sequence. Then given in the next line are the N integers in [ 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

题意：

　　按照给出的序列构建一棵BST，然后找出这颗BST最后两层的结点个数，进行输出。

思路：

　　构建的时候可以用while循环来进行插入，找到插入节点的父节点，如果插入的值大于父节点的值的话则root->right = new Node();而不能先进行root = root->right; 然后再root = new Node();如果这样做的话只是单纯的建立一个结点，并没有将父节点的指针指到该节点上。

　　层次遍历的时候，每一层结束的时候添加一个哨兵，用来表明该层已经查找完毕。用一个数组存储每一层的元素个数，最后在输出。

Code：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef struct Node* node;
 6 
 7 struct Node {
 8     int val;
 9     node left;
10     node right;
11     Node(int v) {
12         val = v;
13         left = NULL;
14         right = NULL;
15     }
16 };
17 
18 void levelTravelTree(node root) {
19     queue<node> que;
20     que.push(root);
21     que.push(NULL);
22     vector<int> v(1005);
23     int count = 0, index = 1;
24     while (!que.empty()) {
25         node q = que.front();
26         que.pop();
27         if (q == NULL) {
28             que.push(NULL);
29             v[index++] = count;
30             count = 0;
31             if (que.size() == 1) break;
32         } else {
33             if (q->left) que.push(q->left);
34             if (q->right) que.push(q->right);
35             count++;
36         }
37     }
38     cout << v[index - 1] << " + " << v[index - 2] << " = "
39          << v[index - 2] + v[index - 1] << endl;
40 }
41 
42 int main() {
43     int n, v;
44     cin >> n;
45     node root = NULL;
46     for (int i = 0; i < n; ++i) {
47         cin >> v;
48         node temp = root;
49         while (temp != NULL)
50             if (v > temp->val && temp->right != NULL)
51                 temp = temp->right;
52             else if (v <= temp->val && temp->left != NULL)
53                 temp = temp->left;
54             else
55                 break;
56         if (root == NULL)
57             root = new Node(v);
58         else if (v > temp->val)
59             temp->right = new Node(v);
60         else
61             temp->left = new Node(v);
62     }
63 
64     levelTravelTree(root);
65 
66     return 0;
67 }