1.题目
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
- -
- -
Sample Output 1:
YES 8
Sample Input 2:
8
- -
4 5
0 6
- -
2 3
- 7
- -
- -
Sample Output 2:
NO 12.题目分析
最通俗的讲，完全二叉树其实就是层序遍历时，必须从左到右节点都不是NULL，直至结束。如果存在一个节点为NULL，而之后又有非NULL的节点，就不是二叉树。
于是我的判断方法就是即使节点是NULL也放入队列，再输出的时候遇到NULL判断已经输出的个数是不是总节点的个数，不是的话就不是完全二叉树。
使用20之后的一个位置存放-1，表示NULL
致命婴幼儿错误：节点编号可能为两位数………………
3.代码
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
struct node
{
int data;
int left;
int right;
}list[30],output,output2;
int mark[30];
int counts = 0;
bool ok = true;
int judge(int head,int n)
{
queue<node>out;
out.push(list[head]);
while (!out.empty())
{
output = out.front();
out.pop();
if (output.data == -1)
{
if (counts < n) { ok = false; return -1; }
else return output2.data;
}
counts++;
out.push(list[output.left]);
out.push(list[output.right]);
output2 = output;//记录上一个output的值，当最后遍历完后，output变为最后的NULL（-1），output2就是所求的最后一个节点的值
}
}
int main()
{
int n,head;
string a, b;
list[25].data = -1;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
list[i].data = i;
cin >> a >> b;
if (a != "-") { list[i].left = stoi(a); mark[list[i].left] = 1; }
else list[i].left = 25;
if (b != "-") { list[i].right = stoi(b); mark[list[i].right] = 1;}
else list[i].right = 25;
}
for (int i = 0; i < n; i++)
if (mark[i] == 0)head = i;
int c = judge(head, n);
if (ok)printf("%s %d
", "YES", c);
else printf("%s %d
", "NO", list[head]);
}