Complete Binary Tree

Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤20) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.

Output Specification:
For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the word and the number.

Sample Input 1:

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -
1
2
3
4
5
6
7
8
9
10

Sample Output 1:

YES 8
1

Sample Input 2:

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -
1
2
3
4
5
6
7
8
9

Sample Output 2:

NO 1
1

题目大意：
判断一棵树是不是完全二叉树，是的话输出YES和最后一个结点，否则输出NO和根节点。

王道书上同样有相同的一道算法题，算法的思路都一样，只是王道书上要求的树是用二叉链表存储结构存储的。

思路：
采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，看其后是否有非空结点。若有，则二叉树不是完全二叉树。

#include
using namespace std;
struct Complete_Binary_Tree
{
    int data;
    int lchild, rchild;
}node[25];
int n;
bool visited[25] = {false};
int turn(string s) {
    int sum = 0;
    for(auto &i:s) sum = sum * 10 + (i - '0');
    return sum;
}
int build_tree() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        string left, right;
        cin >> left >> right;
        node[i].data = i;
        if(left == "-") node[i].lchild = -1;
        else {
            node[i].lchild = turn(left);
            visited[node[i].lchild] = true;
        }
        if(right == "-") node[i].rchild = -1;
        else {
            node[i].rchild = turn(right);
            visited[node[i].rchild] = true;
        }
    }
    for(int i = 0; i < n; i++) {
        if(!visited[i]) return i;//返回根节点
    }
}
int last_node = 0;
bool iscomplete(int root) {
    queue<int>q;
    if(n == 0) return true; // 空树为满二叉树
    q.push(root);
    while (!q.empty())
    {
        int top = q.front();
        q.pop();
        if(top != -1) last_node = top;
        if(top != -1) {
            q.push(node[top].lchild);
            q.push(node[top].rchild);
        } else { // 结点为空，检查其后是否有非空结点
            while(!q.empty()) {
                int temp = q.front();
                q.pop();
                if(temp != -1) return false; // 结点非空，则二叉树为非完全二叉树
            }
        }
    }
    return true;
}
int main() {
    int root = build_tree();
    // for(int i = 0; i < n; i++) cout << node[i].lchild << " " << node[i].rchild << endl;
    // cout << root << endl;
    if(iscomplete(root)) printf("YES %d", last_node);
    else printf("NO %d", root);
    return 0;
}
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