对于二叉树，如果这棵树的节点排布是按行从上到下，每行从左到右挨个放置，中间不会有空闲的节点。则我们称之为完全二叉树。
注：这棵树的根节点的值一定是1
对于二叉树，如果这棵树的节点排布是按行从上到下，每行从左到右挨个放置，中间不会有空闲的节点。则我们称之为完全二叉树。
注：这棵树的根节点的值一定是1
输入数字正整数n （1≤n≤201≤n≤20）
接下来n行，每行为两个数字(a,b)和一个字符c(L 或者 R)，如果字符c是L，则表示b是a的左子节点；如果字符c是R，则表示b是a的右子节点。 (1≤a,b≤30001≤a,b≤3000)
判断这棵树是否为完全二叉树，如果是则输出Yes，否则输出No
5
1 2 L
1 3 R
2 4 L
2 5 R
3 6 L
Yes
样例解释：样例所描述的二叉树结构如下
很显然这是一个完全二叉树。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 #include <cstdlib> 9 #include <iomanip> 10 #include <cmath> 11 #include <cassert> 12 #include <ctime> 13 #include <map> 14 #include <set> 15 using namespace std; 16 typedef long long ll; 17 const int N =3500*2; 18 queue<int> que; 19 int n,x,y,flag=1; 20 char c; 21 struct Nod{ 22 int l=0; 23 int r =0; 24 }nod[N]; 25 bool bfs(int sta) 26 { 27 28 que.push(sta); 29 while(!que.empty()) 30 { 31 int top = que.front(); 32 que.pop(); 33 if(!flag&&nod[top].l!=0)//flag==0时一定是叶子节点了 34 return 0; 35 if(nod[top].l==0&&nod[top].r!=0)//不可能左边没有右边有 36 return 0; 37 if(nod[top].l==0||nod[top].r==0) 38 { 39 flag = 0; 40 } 41 if(nod[top].l!=0) 42 que.push(nod[top].l); 43 if(nod[top].r!=0) 44 que.push(nod[top].r); 45 46 } 47 return 1; 48 } 49 int main() 50 { 51 scanf("%d",&n); 52 while(n--) 53 { 54 scanf("%d%d",&x,&y); 55 cin>>c; 56 if(c==‘L‘) 57 { 58 nod[x].l=y; 59 } 60 else 61 { 62 nod[x].r=y; 63 } 64 } 65 if(bfs(1)) 66 printf("Yes\n"); 67 else 68 printf("No\n"); 69 return 0; 70 }
原文：https://www.cnblogs.com/tingtin/p/10050777.html