功能模块设计

基于C语言实现的完全二叉树，包含以下功能模块：

初始化二叉树
创建节点
根据输入数据创建任意结构二叉树
插入数据至二叉树中（自动放在第一个空指针处）
先根遍历（基于深度优先并借助递归实现）
中根遍历（基于深度优先并借助递归实现）
后根遍历（基于深度优先并借助递归实现）
层次遍历（基于广度优先并借助队列实现）
获取叶子节点个数
获取节点总个数
获取二叉树深度

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXNODE 1000

//二叉树的节点数据结构
//节点数据域
typedef int ElemType;
typedef struct BitNode
{
	ElemType data;
	//指针域，包含左右孩子两个指针
	struct BitNode* lchild, * rchild;
} BitNode, * BitTree;

//1.创建节点
BitNode* CreateNode(ElemType data);
//2.初始化二叉树
void InitBitTree(BitTree* bt);
//3.根据输入数据创建任意结构二叉树
void CreateBitTree(BitTree* T);
//4.插入数据至二叉树中（自动放在第一个空指针处）
void Insert(BitTree* bt, ElemType data);
//5.先根遍历（基于深度优先并借助递归实现）
void PreOrder(BitTree bt);
//6.中根遍历（基于深度优先并借助递归实现）
void InOrder(BitTree bt);
//7.后根遍历（基于深度优先并借助递归实现）
void PostOrder(BitTree bt);
//8.层次遍历（基于广度优先并借助队列实现）
void LevelOrder(BitTree bt);
//9.获取叶子节点个数
int CountLeaf(BitTree bt);
//10.获取节点总个数
int CountNode(BitTree bt);
//11.获取二叉树深度
int Depth(BitTree bt);

int main(void)
{
	BitTree bt = NULL;
	InitBitTree(&bt);
	ElemType data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int i = 0;
	printf("创建完全二叉树！\n");
	for (i = 0; i < 9; i++)
	{
		Insert(&bt, data[i]);
	}
	//先序遍历
	printf("先根遍历结果：");
	PreOrder(bt);
	printf("\n");
	//中序遍历
	printf("中根遍历结果：");
	InOrder(bt);
	printf("\n");
	//后序遍历
	printf("后根遍历结果：");
	PostOrder(bt);
	printf("\n");
	//层次遍历
	printf("层次遍历结果：");
	LevelOrder(bt);
	printf("\n");
	printf("节点总个数：%d\n", CountNode(bt));
	printf("叶子节点个数：%d\n", CountLeaf(bt));
	printf("二叉树深度：%d\n", Depth(bt));
	return 0;
}


//功能1 创建节点
BitNode* CreateNode(ElemType data)
{
	BitNode* node = (BitNode*)malloc(sizeof(BitNode));
	node->data = data;
	node->lchild = node->rchild = NULL;
	return node;
}

//功能2 初始化二叉树
void InitBitTree(BitTree* bt)
{
	*bt = NULL;
}

//功能3 根据输入数据创建任意结构二叉树
void CreateBitTree(BitTree* T)
{
	int ch = 0;
	scanf("%d", &ch);
	if (ch == -1) T = NULL;
	else
	{
		*T = CreateNode(ch);
		CreateBitTree(&(*T)->lchild);
		CreateBitTree(&(*T)->rchild);
	}
}

//功能4 插入数据至二叉树中（自动放在第一个空指针处），可创建完全二叉树
void Insert(BitTree* bt, ElemType data)
{
	BitNode* node = CreateNode(data);
	if (*bt == NULL) *bt = node;
	else
	{
		BitTree Queue[MAXNODE];
		int front = 0, rear = 0;
		Queue[rear++] = *bt;
		while (front != rear)
		{
			BitTree temp = Queue[front++];
			if (temp->lchild)
			{
				Queue[rear++] = temp->lchild;
			}
			else
			{
				temp->lchild = node;
				return;
			}
			if (temp->rchild)
			{
				Queue[rear++] = temp->rchild;
			}
			else
			{
				temp->rchild = node;
				return;
			}
		}
	}
}

//功能5 先根遍历（基于深度优先并借助递归实现）
void PreOrder(BitTree bt)
{
	if (bt)
	{
		printf("%-4d", bt->data);
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}

//功能6 中根遍历（基于深度优先并借助递归实现）
void InOrder(BitTree bt)
{
	if (bt)
	{
		InOrder(bt->lchild);
		printf("%-4d", bt->data);
		InOrder(bt->rchild);
	}
}

//功能7 后根遍历（基于深度优先并借助递归实现）
void PostOrder(BitTree bt)
{
	if (bt)
	{
		PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		printf("%-4d", bt->data);
	}
}

//功能8 层次遍历（基于广度优先并借助队列实现）
void LevelOrder(BitTree bt)
{
	if (bt == NULL) return;
	BitTree Queue[MAXNODE];
	int front = 0, rear = 0;
	Queue[rear++] = bt;
	while (rear != front)
	{
		if (Queue[front]->lchild)
		{
			Queue[rear++] = Queue[front]->lchild;
		}
		if (Queue[front]->rchild)
		{
			Queue[rear++] = Queue[front]->rchild;
		}
		printf("%-4d", Queue[front++]->data);
	}
}

//功能9 获取叶子节点个数
int CountLeaf(BitTree bt)
{
	if (bt == NULL) return 0;
	if (bt->lchild == NULL && bt->rchild == NULL) return 1;
	return CountLeaf(bt->lchild) + CountLeaf(bt->rchild);
}

//功能10 获取节点总个数
int CountNode(BitTree bt)
{
	if (bt == NULL) return 0;
	return CountNode(bt->lchild) + CountNode(bt->rchild) + 1;
}

//功能11 获取二叉树深度
int Depth(BitTree bt)
{
	if (bt == NULL) return 0;
	int m = Depth(bt->lchild);
	int n = Depth(bt->rchild);
	return m > n ? m + 1 : n + 1;
}