将二叉树保存到动态指针数组中

把二叉树的结点按从上到下、从左到右依次编号为0、1、2、3......(空指针也要占一个编号）。

则如果某个结点的编号是i，根据二叉树的性质有：

它的左孩子的编号是2*i+1；

它的右孩子的编号是2*i+2；

可以据此把二叉树保存到一个数组中，这里是保存到了一个动态指针数组中。

下面是代码部分：

//这个是测试用数据，输入-1表示孩子为空指针
//69 25 74 -1 -1 83 -1 -1 10 88 -1 -1 115 -1 -1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct BtNode
{
	int data;
	struct BtNode *left,*right;
};

typedef struct BtNode **PtPt;

void createbt(PtPt *ptarr,int root,int *plen)
{
	int data,newlen;
	
	if(root>=*plen)
	{
		newlen=(*plen)*2;
		*ptarr=(PtPt)realloc(*ptarr,newlen*sizeof(struct BtNode*));
		memset(*ptarr+(*plen),0,(newlen-*plen)*sizeof(struct BtNode*));
		*plen=newlen;
	}
	scanf("%d",&data);
	if(data==-1)
	{
		return;
	}
	(*ptarr)[root]=(struct BtNode*)malloc(sizeof(struct BtNode));
	(*ptarr)[root]->data=data;
	createbt(ptarr,2*root+1,plen);
	createbt(ptarr,2*root+2,plen);
}

void preorder(PtPt arr,int root,int len)
{
	if(root<len && arr[root])
	{
		printf("%d ",arr[root]->data);
		preorder(arr,2*root+1,len);
		preorder(arr,2*root+2,len);
	}
}

void midorder(PtPt arr,int root,int len)
{
	if(root<len && arr[root])
	{
		midorder(arr,2*root+1,len);
		printf("%d ",arr[root]->data);
		midorder(arr,2*root+2,len);
	}
}

void postorder(PtPt arr,int root,int len)
{
	if(root<len && arr[root])
	{
		postorder(arr,2*root+1,len);
		postorder(arr,2*root+2,len);
		printf("%d ",arr[root]->data);
	}
}

int countdeep(PtPt arr,int root,int len)
{
	int leftdeep,rightdeep;
	
	if(root<len && arr[root])
	{
		leftdeep=countdeep(arr,2*root+1,len);
		rightdeep=countdeep(arr,2*root+2,len);
		return 1+(leftdeep>rightdeep?leftdeep:rightdeep);
	}
	return 0;
}

void cengorder(PtPt arr,int len)
{
	int i;
	
	for(i=0;i<len;i++)
	{
		if(arr[i])
		{
			printf("%d ",arr[i]->data);
		}
	}
}

void freebt(PtPt arr,int len)
{
	for(len--;len>0;len--)
	{
		if(arr[len])
		{
			free(arr[len]);
		}
	}
	free(arr);
}

int main()
{
	int root=0,len=1;
	PtPt arr=(PtPt)calloc(len,sizeof(struct BtNode*));
	
	memset(arr,0,len*sizeof(struct BtNode*));
	
	printf("请输入二叉树的各结点的值(空指针输入-1)：");
	createbt(&arr,root,&len);
	
	printf("先序遍历：");
	preorder(arr,root,len);
	printf("\n");
	
	printf("中序遍历：");
	midorder(arr,root,len);
	printf("\n");
		
	printf("后序遍历：");
	postorder(arr,root,len);
	printf("\n");
	
	printf("按层遍历：");
	cengorder(arr,len);
	printf("\n");
	
	printf("树的深度是：%d\n",countdeep(arr,root,len));
	
	freebt(arr,len);
	
	return 0;
}

结果显示：