Question

判断完全二叉树用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

Answer 1

用一个线性表和一个队列，表存放的是边集，队列用于按层次遍历。程序流程如下

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");
}

运行结果

Answer 2

我怎么感觉你的例子应该输出no呢

追问

可是老师给的题目就是这样的，我是复制过来的

追答

你自己画一下这个二叉树呢，5和4两个节点的位置反了。

追问

我只会看它是不是完全二叉树，看着这样的不会画

追答

1
2 3
5 4

这个就是你的二叉树，明明不是完全二叉树嘛

程序的大致架构是这样：

/*
规则：
1.根节点必须存在
2.子节点是根节点的2倍或者2倍+1
3.偶数的子节点须是左子结点，奇数为右
*/
int check_rootexist()
{
//
}
int check_relation()
{
//
}
int check_leftson()
{
//
}
int check()
{
//
check_rootexist
check_relation
check_leftson
}
int main ()
{
while (n-- > 1)
{
check(a, b)
}
printf("yes\n");
return 0;
}

追问

这个头怎么加啊，我不会啊

追答

什么头？
我上面只是写了个我的大致思路，用于判断的。

楼上那哥们好像整的很专业，学习下