判断完全二叉树用C语言编写
题目描述
假如对二叉树T和具有相同高度的满二叉树编号，如果T与满二叉树相同编号的节点位置相同，那么称二叉树T是一棵完全二叉树。现在根据边的连接情况判断一棵树是否是完全二叉树。
输入要求
第一行有2个整数n(0 < n < 1024)和r(1<=r<=n), 表示结点数和树根，接下来n-1行每行有2个整数a,b (1 <= a,b <= n)表示a结点和b结点有一条边相连，如果a是b的根结点，则b是a的左子结点，如果b是a的根结点，则a是b的右子结点（数据保证是一棵树而不是一座森林)
输出要求
如果是完全二叉树 输出yes 否则输出no
假如输入
5 1
1 2
3 1
4 2
2 5
应当输出
yes
用一个线性表和一个队列，表存放的是边集，队列用于按层次遍历。程序流程如下
1 初始化空表、空队；
2 输入结点数、指定根结点，输入边到表中；
3 根结点进队；
4 将队首出队到p；
5 若表为空，返回1（真）。不空则在表中查找第一项等于p的边i。若找到，将边i的第二项进队，从表中删除边i。若没有找到，则返回0（假）。
6 若表为空，返回1（真）。不空则在表中查找第二项等于p的边i。若找到，将边i的第一项进队，从表中删除边i。若没有找到，则返回0（假）。
7 跳到4。
补充提供一个相应的程序代码如下，你可以试试
#include <stdio.h>
#define N 1024
void main( )
{
short list[N][2], queue[N], listLength = 0, front = 0, rear = 0, r, n, i, p;/*1 初始化空表，空队*/
char flag; /*flag是判断结果标识*/
scanf("%d%d", &n, &r); /*2 输入结点数、指定根结点，输入边到表中*/
for(i = 0; i < n - 1; i++)
scanf("%d%d", &list[i][0], &list[i][1]);
listLength = n - 1;
queue[rear++] = r; /*3 根结点进队*/
while(1) {
p = queue[front++]; /*4 将队首出队到p*/
if(listLength == 0) { /*5 如果表为空，则返回1（真）*/
flag = 1;
break;
}
for(i = 0; i < listLength && list[i][0] != p; i++); /*寻找第一项等于p的边i*/
if(i == listLength) { /*如果没有找到，返回0（假）*/
flag = 0;
break;
}
queue[rear++] = list[i][1]; /*将边i的第二项进队*/
for(; i < listLength - 1; i++) /*删除边i*/
list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];
listLength--;
if(listLength == 0) { /*6 若表为空，返回1（真）*/
flag = 1;
break;
}
for(i = 0; i < listLength && list[i][1] != p; i++); /*在表中查找第二项等于p的边i*/
if(i == listLength) { /*如果没有找到，返回0（假）*/
flag = 0;
break;
}
queue[rear++] = list[i][0]; /*将边i的第一项进队*/
for(; i < listLength - 1; i++) /*删除边i*/
list[i][0] = list[i + 1][0], list[i][1] = list[i + 1][1];
listLength--;
} /*7 跳到4*/
if(flag)
printf("yes\n");
else
printf("no\n");
}
运行结果
