完全二叉树 数据结构

发布网友 发布时间：2022-04-26 23:59

我来回答

共1个回答

热心网友 时间：2022-06-20 18:26

#include "math.h"
#include "string.h"
#include "stdlib.h"
/*
判断某个节点num是否属于二叉树a[]内的节点,其中len是二叉树数组表示的所有节点个数，
包括左右孩子为空的情况，*index是节点num在二叉树数组中的位置。
*/
int judge(int a[], int len,int *index, int num)
{
    for (int i=0; i<len; i++)
    {
        if (a[i] == num)
        {
*index = i;
return 1;
        }
    }
return 0;
} 

/*
以数组形式创建二叉树,返回数组指针，其中参数NodeNum是二叉树内非空节点个数
*/
int * CreateBinTree(int *NodeNum)
{
    int *a=NULL;
    int x=0,y=0;
    scanf("%d %d",&x,&y);
a = (int *)malloc(sizeof(int)*(x*2+1));
*NodeNum = x;
memset(a,0,sizeof(int)*(x*2+1));
a[0] = y;
int n = x;
for (int i=1; i<n; i++)

{
        scanf("%d %d",&x,&y);
int index=0;
if ( judge(a,n,&index,x) )
{
a[ (index)*2+1 ] = y;
}
else if ( judge(a,n,&index,y) )
{
            a[ (index)*2+2 ] = x;
}
}
    return a;
}

/*
判断是否完全二叉树的依据是某个节点左右孩子不为空，或者全部为空
*/
int isBinTree(int a[], int NodeNum)
{
    for (int i=0; i<(2*NodeNum+1); i++ )
    {
        if (a[i] != 0)
        {
if ( (a[2*i+1]==0)&&(a[2*i+2]!=0) )
{
return 0;
}
if ((a[2*i+1]!=0)&&(a[2*i+2]==0))
{
return 0;
}
        }
    }
}
int main(int argc, char* argv[])
{
        int *a=NULL;
int NodeNum=0;
a = CreateBinTree(&NodeNum);
printf("\nShow:");
for (int i=0; i<2*NodeNum+1; i++)
{
   printf("%d ",a[i]);
}
int rt = isBinTree(a,NodeNum);
if (rt)
{
           printf("\nyes!");
}
else
{
           printf("\nno!");
}

printf("\n");
return 0;
}