1. 判斷完全二叉樹用C語言編寫
用一個線性表和一個隊列，表存放的是邊集，隊列用於按層次遍歷。程序流程如下
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
");
else
printf("no
");
}
運行結果
