完全二叉树 数据结构第一行有2个整数n(0 < n < 1024)和r(1
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/08 11:44:29
完全二叉树 数据结构第一行有2个整数n(0 < n < 1024)和r(1
完全二叉树 数据结构
第一行有2个整数n(0 < n < 1024)和r(1
完全二叉树 数据结构第一行有2个整数n(0 < n < 1024)和r(1
#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;
}