【数据结构】二叉树初阶——超详解！！！（包含二叉树的实现）

zore

发布于 2025-12-30 18:59:19

2450

文章被收录于专栏：C/C++ 专栏C/C++ 专栏

前言

往期我们的学习中讲到了顺序表、链表、栈以及队列等数据结构 它们可以帮我们解决很多问题，而类似的数据结构还有很多 今天，我们就来聊聊——二叉树

一、树是什么？

1. 树的定义

树：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。有一个特殊的结点，称为根结点，根结点没有前驱结点除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

2. 一些常见术语

这就是一个常见的树：

以下还有一些常见的术语：(如图） 结点的度：一个结点含有的子树的个数称为该结点的度；（A的度为6） 叶结点或终端结点：度为0的结点称为叶结点；（B、H、P......为叶结点） 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；（A为B的父结点） 子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；（B为A的子结点） 树的高度或深度：树中结点的最大层次；（该树高度为4）

二、二叉树

1. 二叉树是什么？

二叉树 就是一种特殊的树，其树的度最大为 2 也就是说，一个结点最多有两个分叉 而在日常生活中，由于树的结构复杂很少用，所以最实用的是二叉树，其只有最多两个分叉

2. 二叉树的组成

二叉树 由一个根结点加上两棵别称为左子树和右子树的二叉树组成 且注意二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

如图，就是一个二叉树：

其组成就是：

2. 特殊的二叉树

二叉树有两种特殊情况： 满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树 也就是说，如果一个二叉树的层数为 K ，且结点总数是 2 ^ k - 1 ，则它就是满二叉树。 完全二叉树： 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1 至 n的结点一一对应时称之为完全二叉树 要注意的是满二叉树是一种特殊的完全二叉树 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的

如下图，分别是满二叉树和完全二叉树：

要注意，完全二叉树的编号是连续的，中间断开则不是完全二叉树 如下图的树就不是完全二叉树：

3. 二叉树的顺序存储（完全二叉树）

对于一个完全二叉树的存储，前面也提到完全二叉树的编号是连续的 所以，对于完全二叉树来说，我们可以用数组来进行存储，用下标来进行编号 二叉树顺序存储在物理上是一个数组，而在逻辑上是一颗二叉树

如图，一个逻辑结构（我们人为想象的），一个物理结构（真实存储的）：

4. 二叉树的一些性质

1. 若规定根结点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2 ^ ( k - 1 ) 个结点 2. 若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2 ^ h - 1 3. 对任何一棵二叉树, 如果度为 0 其叶结点个数为 n₀ , 度为 2 的分支结点个数为 n₂ ，则有 n₀ = n₂ + 1 4. 若规定根结点的层数为 1，具有n个结点的满二叉树的深度，h = log₂( n + 1 )

最后一点，也是最重要的一点：

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号 （前面提到过） 存在：

若父亲在数组中下标为i，则该父亲的左孩子下标为 2 * i + 1；左孩子下标为2 * i + 2
若孩子在数组中下标为i，则该孩子的父亲下标为（ i - 1）/ 2 注意：前提是这些小标所对应的值存在！！！

以上的性质都是一些数学的基本常识，小编在这里也不过多的介绍 感兴趣的可以自己推导推导哦

三、二叉树的实现（重点！！！）

1. 二叉树的链式存储（非完全二叉树）

前面我们说到存储完全二叉树可以用数组来进行，是因为完全二叉树的编号是连续的 而非完全二叉树却不是如此，若强行用数组来存储会浪费大量的空间

如图：

那么除了数组，我们还可以用什么来储存二叉树呢？ 我们会想到链式存储

链式存储 故名思意，就是用链表来表示一颗二叉树，用链来指示元素的逻辑关系 通常的方法 创建一链表，使每个结点由三个域组成，数据域和左右指针域 左右指针分别用来给出该结点左孩子和右孩子所在结点的地址（下面会提到）

2. 实现思路

知道了用链式存储，现在就可以开始实现代码了

与单链表的实现类似，二叉树中的每一个节点有以下三个成员： 1. 节点中存储的数据 2. 指向节点左孩子的指针 3. 指向节点右孩子的指针

3. 代码实现

本文以创建一个 char 类型的二叉树为例

（1）创建头文件&源文件

之前在讲解扫雷游戏中我就提到: 在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱

详见【C语言】扫雷游戏详解（包含递归，变色，记录时间等）

如图: 创建了一个 “ BTNode.h "头文件 用于存放用来放函数的声明和一些库函数的头文件 创建了一个 “BTNode.c "源文件 用于用来放函数的定义(二叉树的主体) 还有一个 ” Test.c "源文件 用于测试实现的二叉树的运行效果 （其他的后面会说）

（2）定义二叉树（定义）

首先我们要定义一个二叉树 这里之前讲过，创建一个类似链表的结构 每个结点里面包含三个成员： 节点中存储的数据指向左孩子的指针指向右孩子的指针

代码演示：（内有注释） （在头文件“ BTNode.h "中写）

//重定义，方便修改类型
typedef char BTDataType;

//表示每个节点的类型
typedef struct BinaryTreeNode
{
	BTDataType data;            //节点中存储的数据
	struct BinaryTreeNode* left;//指向左孩子的指针
	struct BinaryTreeNode* right;//指向右孩子的指针
}BTNode;

在定义二叉树的代码中，有两个需要注意的点：

本文是以 char 类型为例，但如果以后要将二叉树中的元素类型修改成 int 类型或是其他类型一个一个修改就很麻烦 所以我们重定义char类型为BTDataType,并将接下来代码中的char类型全部写成BTDataType 这是为了方便我们以后对类型进行修改，仅需将char改为其他类型即可
在定义二叉树的同时重定义二叉树的变量名为 BTNode方便以后使用

（3）构建二叉树

小编这里通过一个前序遍历的数组"ABD##E#H##CF##G##"来构建了二叉树 要先有一个二叉树，才能对二叉树进行操作 （关于怎么构建的不重要，大家也可以将一个一个结点进行插入但这不是重点！！！重点是之后二叉树的实现！！！）

代码演示：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* ch, int* pi)
{
	if (ch[*pi] == '#')
	{
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = ch[(*pi)++];

	newnode->left = BinaryTreeCreate(ch, pi);
	(*pi)++;
	newnode->right = BinaryTreeCreate(ch, pi);
	return newnode;
}

（4）二叉树遍历（前中后序）

要想对二叉树进行操作，肯定少不了遍历二叉树但是要怎么遍历是个问题，这里一共有4种： 前序遍历、中序遍历、后序遍历、层序遍历 这四种遍历主要在于遍历顺序的不一样，我们一一来拆解

前序

前序遍历是指遍历时先遍历根、接着左子树、最后右子树

还要注意，这个遍历是递归进行的!!!

当遍历完根后，开始遍历左子树，就以左子树为起始位置，继续从根遍历、接着左子树、最后右子树，以此循环，直到全部遍历结束

代码演示： （内有注释，自行查看）

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	//当遍历到空就返回
	if (root == NULL)
	{
		return;
	}

	//打印根，然后递归遍历左子树、右子树
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

中序

中序遍历原理与前序遍历一样，只是遍历的顺序不一样 中序遍历是指遍历时先遍历左子树、接着根、最后右子树

代码演示： （内有注释，自行查看）

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	//当遍历到空就返回
	if (root == NULL)
	{
		return;
	}

	//递归遍历左子树、打印根、递归遍历右子树
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

后序

后序遍历原理与前序遍历也一样，只是遍历的顺序不一样 后序遍历是指遍历时先遍历右子树、接着左子树、最后根

代码演示： （内有注释，自行查看）

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	//当遍历到空就返回
	if (root == NULL)
	{
		return;
	}

	//递归遍历左子树、递归遍历右子树、打印根
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

（5）二叉树的层序遍历

这里看到小编特意把层序遍历与前三个遍历分开写，也可以看出层序的不一样了也确实，层序遍历与前三种遍历差了很多

首先，层序遍历是什么？ 层序层序，就是一层一层的遍历 比如下图的二叉树：

该二叉树层序遍历的结果就是【1，2，3，4，5，6，7】也就是一层一层遍历，这就是层序遍历 那又要该怎么写代码呢？

接着，代码思路是什么？ 我们怎么做到遍历完 1，2，3 后去遍历 4，5 呢？此时也无法直接通过 2 来找到 4，5 了这时我们可以想到我们之前学过的东西——队列 我们可以在每次取出结点的同时，将该结点的左结点和右结点存储进队列中，直到队列为空 例如: 开始时放入1，此时队列【1】 取出1，并放入2、3，此时队列【2，3】 取出2，并放入4、5，此时队列【3，4，5】 取出3，并放入6、7，此时队列【4，5，6，7】 取出4，此时队列【5，6，7】 取出5，此时队列【6，7】 取出6，此时队列【7】 取出7，此时队列【】

在前面的学习中小编已经讲解过了队列了，这里就不赘述，想知道的可以去看看 链接：【数据结构】队列——超详解！！！（包含队列的实现）

最后，代码实现 现在，知道了要用队列来实现，就可以开始来写代码了 我们创建一个队列，先把第一个根节点存入 接着在每次取出结点的同时，将该结点的左结点和右结点存储进队列中 以此循环直到队列为空

代码演示：（不包含队列的实现） （内有注释，自行查看）

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	//先创建一个队列来存储结点
	Queue Q;
	QueueInit(&Q);

	//先将第一个根结点存入队列中
	if (root)
	{
		QueuePush(&Q, root);
	}

	//若队列不为空就循环
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		printf("%c ", root->data);
		QueuePop(&Q);

		//将队头的左子树、右子树存入队列中（前提是不为空）
		if (root->left)
		{
			QueuePush(&Q, root->left);
		}
		if (root->right)
		{
			QueuePush(&Q, root->right);
		}
	}
	//最后不要忘记了销毁队列
	QueueDestroy(&Q);
}

（6）二叉树节点个数的计算

当我们想要用代码来计数二叉树中的所有节点个数，该怎么办呢？其实这很简单，只需要熟悉递归就行了 当根节点为空时，就计 0 而当根节点为非空时，就 + 1 并递归计算其左右子树再

代码演示： （内有注释，自行查看）

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
		//递归左右子树并+1
}

（7）二叉树高度的计算

当我们想要用代码来计数二叉树的高度，该怎么办呢？首先我们要知道二叉树高度是什么，是树中结点的最大层次 而二叉树有左子树以及右子树，故左右子树高度更高的一边 + 1 就是树的高度
所以，我们可以用递归来实现 当根节点为空时，返回 0 而当根节点为非空时，就返回左右子树高度更高的一边并 + 1（根节点本身）

代码演示： （内有注释，自行查看）

// 二叉树高度
int BinaryTreeHight(BTNode* root)
{
   //当根节点为空时，返回 0
	if (root == NULL)
	{
		return 0;
	}
	return fmax(BinaryTreeHight(root->left), BinaryTreeHight(root->right)) + 1;
	//而当根节点为非空时
	//返回左右子树高度更高的一边并 + 1（根节点本身）
}

（8）二叉树第k层节点个数的计算

当我们想要用代码来计数二叉树第k层的节点个数，该怎么办呢？对于一个满二叉树很简单，套公式就行，但非完全二叉树咋办呢？这里依旧是递归： 初始 k，若该层不是目标层次，就 k - 1 并递归左右子树 当根节点为空时，返回 0 当根节点为非空且此时 k == 1 时，返回 1（已经到达第 k 层）

代码演示： （内有注释，自行查看）

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//当根节点为空时，返回 0
	if (root == NULL)
	{
		return 0;
	}

	//当根节点为非空且此时 k == 1 时，返回 1（已经到达第 k 层）
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
	//若该层不是目标层次，就 k - 1 并递归左右子树 
}

（9）二叉树查找值为x的节点

当我们想要用代码来查找值为x的节点，该怎么办呢？ 这里依旧是递归： 当根节点为空时，返回空 当根节点的值为X时，返回根节点的地址 最后找左右子树 但要注意！！！： 该函数返回的是地址，故在递归的过程中地址信息不能丢失，要不断返回 可以先判断返回值是否为真，再决定继续递归还是返回数据

代码演示： （内有注释，自行查看）

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//没找到
	{
		return NULL;
	}
	if (root->data == x)//找到直接返回地址
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)//判断返回值，若不为空就返回，为空就找右子树
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
}

（10）判断二叉树是否是完全二叉树

现在，给你一个树，怎么用代码来判断该树是完全二叉树呢？ 我们可以用到之前的层序遍历来完成 当层序遍历到空结点时，若之后还有数据则不是完全二叉树 当层序遍历到空结点时，若没有数据则是完全二叉树

原理就是层序遍历，只不过多加入了一层判断

代码演示： （内有注释，自行查看）

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	//先创建一个队列来存储结点
	Queue Q;
	QueueInit(&Q);

	//先将第一个根结点存入队列中
	if (root)
	{
		QueuePush(&Q, root);
	}

	//若队列不为空就循环
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		QueuePop(&Q);

		//判断是否遇到空结点，遇到就跳出循环
		if (root == NULL)
		{
			break;
		}

		//将队头的左子树、右子树存入队列中
		QueuePush(&Q, root->left);
		QueuePush(&Q, root->right);
	}

	//继续循环判断是否有残余结点
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		QueuePop(&Q);

		//判断是否遇到非空结点，遇到则说明，结点不连续，不是完全二叉树
		if (root != NULL)
		{
			//最后不要忘记了销毁队列
			QueueDestroy(&Q);

			//返回 0（假）
			return 0;
		}
	}
	//最后不要忘记了销毁队列
	QueueDestroy(&Q);

	//最后返回 1（真）
	return 1;
}

四、二叉树实现完整代码

（包含队列的实现）

1. Queue.h

用于存放用来放函数的声明和一些库函数的头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<sperror.h>

//重定义，方便修改类型
typedef int QDataType;

//表示每个节点的类型
typedef struct QListNode
{
	QDataType data;//节点中存储的数据
	struct QListNode* next;//指向下一个节点的指针
	
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;//头指针
	QNode* tail;//尾指针
	int size;  //总元素个数
}Queue;

// 初始化队列 
void QueueInit(Queue* q);

// 队尾入队列 
void QueuePush(Queue* q, QDataType data);

// 队头出队列 
void QueuePop(Queue* q);

// 获取队列头部元素 
QDataType QueueFront(Queue* q);

// 获取队列队尾元素 
QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数 
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);

// 销毁队列 
void QueueDestroy(Queue* q);

2. Queue.c

用于用来放函数的定义(队列的主体)

#include"Queue .h"

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	//断言空指针

	q->front = NULL;
	q->tail = NULL;
	q->size = 0;
	//全部初始化置 0 / NULL
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	//断言空指针

	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	//直接开辟一个节点的空间

	if (tmp == NULL)
	//加一个 if语句 防止增容失败
	{
		perror("malloc");
		return;
	}

	//没有问题后就赋值
	tmp->data = data;
	tmp->next = NULL;

	//注意：当队列中没有节点时
	//此时插入的节点既是头节点，又是尾节点
	if (q->size == 0)
	{
		q->front = tmp;
		q->tail = tmp;
	}
	else
	{
		q->tail->next = tmp;
		q->tail = tmp;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	//断言空指针
	//断言顺序表不能为空
	
	//注意：当队列中只有一个节点时，头尾节点相等
	//此时将头节点和尾节点都释放
	if (q->size == 1)
	{
		free(q->front);
		q->front = NULL;
		q->tail = NULL;
	}
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	//断言空指针
	//断言顺序表不能为空

	return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->size > 0);
	//断言空指针
	//断言顺序表不能为空

	return q->tail->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	//断言空指针
	
	return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	//断言空指针
	
	return q->size == 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	//断言空指针

	QNode* cur = q->front;

	//遍历链表，一一释放空间销毁
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = q->tail = NULL;
	q->size = 0;
	//全部初始化置 0 / NULL
}

3. BTNode.h

用于存放用来放函数的声明和一些库函数的头文件

#pragma once
#include"Queue .h"

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* ch, int* pi);

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

// 二叉树高度
int BinaryTreeHight(BTNode * root);

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);

4. BTNode.c

用于用来放函数的定义(二叉树的主体)

#include"BTNode.h"

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* ch, int* pi)
{
	if (ch[*pi] == '#')
	{
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = ch[(*pi)++];

	newnode->left = BinaryTreeCreate(ch, pi);
	(*pi)++;
	newnode->right = BinaryTreeCreate(ch, pi);
	return newnode;
}

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	//先创建一个队列来存储结点
	Queue Q;
	QueueInit(&Q);

	//先将第一个根结点存入队列中
	if (root)
	{
		QueuePush(&Q, root);
	}

	//若队列不为空就循环
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		printf("%c ", root->data);
		QueuePop(&Q);

		//将队头的左子树、右子树存入队列中（前提是不为空）
		if (root->left)
		{
			QueuePush(&Q, root->left);
		}
		if (root->right)
		{
			QueuePush(&Q, root->right);
		}
	}
	//最后不要忘记了销毁队列
	QueueDestroy(&Q);
}

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right) + 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}

// 二叉树高度
int BinaryTreeHight(BTNode* root)
{
	//当根节点为空时，返回 0
	if (root == NULL)
	{
		return 0;
	}

	return fmax(BinaryTreeHight(root->left)
		, BinaryTreeHight(root->right)) + 1;
	//而当根节点为非空时
	//返回左右子树高度更高的一边并 + 1（根节点本身）
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//当根节点为空时，返回 0
	if (root == NULL)
	{
		return 0;
	}

	//当根节点为非空且此时 k == 1 时，返回 1（已经到达第 k 层）
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
	//若该层不是目标层次，就 k - 1 并递归左右子树 
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//没找到
	{
		return NULL;
	}
	if (root->data == x)//找到直接返回地址
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)//判断返回值，若不为空就返回，为空就找右子树
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
}

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	//先创建一个队列来存储结点
	Queue Q;
	QueueInit(&Q);

	//先将第一个根结点存入队列中
	if (root)
	{
		QueuePush(&Q, root);
	}

	//若队列不为空就循环
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		QueuePop(&Q);

		//判断是否遇到空结点，遇到就跳出循环
		if (root == NULL)
		{
			break;
		}

		//将队头的左子树、右子树存入队列中
		QueuePush(&Q, root->left);
		QueuePush(&Q, root->right);
	}

	//继续循环判断是否有残余结点
	while (!QueueEmpty(&Q))
	{
		//接受队头的数据，并删除队头的结点
		BTNode* root = QueueFront(&Q);
		QueuePop(&Q);

		//判断是否遇到非空结点，遇到则说明，结点不连续，不是完全二叉树
		if (root != NULL)
		{
			//最后不要忘记了销毁队列
			QueueDestroy(&Q);

			//返回 0（假）
			return 0;
		}
	}
	//最后不要忘记了销毁队列
	QueueDestroy(&Q);

	//最后返回 1（真）
	return 1;
}

5. Test.c

用于测试实现的二叉树的运行效果 （这里是小编在写代码时写的测试用例） （大家在写的时候也要多多测试哦）

#include"BTNode.h"

int main()
{
	char ch[100] = "ABD##E#H##CF##G##";
	int i = 0;

	// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
	BTNode* T = BinaryTreeCreate(ch, &i);

	// 二叉树节点个数
	int ret1 = BinaryTreeSize(T);
	printf("二叉树节点个数：%d\n", ret1);

	// 二叉树叶子节点个数
	int ret2 = BinaryTreeLeafSize(T);
	printf("二叉树叶子节点个数：%d\n", ret2);

	// 二叉树高度
	int ret3 = BinaryTreeHight(T);
	printf("二叉树高度：%d\n", ret3);

	// 二叉树第k层节点个数
	int ret4 = BinaryTreeLevelKSize(T, 3);
	printf("二叉树第k层节点个数：%d\n", ret4);

	// 二叉树查找值为x的节点
	BTNode* ret5 = BinaryTreeFind(T, 'G');
	if (ret5 == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("存在%c\n", ret5->data);
	}

	// 判断二叉树是否是完全二叉树
	int ret6 = BinaryTreeComplete(T);
	if (ret6)
	{
		printf("是完全二叉树\n");
	}
	else
	{
		printf("不是完全二叉树\n");
	}
	printf("\n");

	// 二叉树前序遍历 
	printf("前序：");
	BinaryTreePrevOrder(T);
	printf("\n\n");

	// 二叉树中序遍历
	printf("中序：");
	BinaryTreeInOrder(T);
	printf("\n\n");

	// 二叉树后序遍历
	printf("后序：");
	BinaryTreePostOrder(T);
	printf("\n\n");

	// 层序遍历
	printf("层序：");
	BinaryTreeLevelOrder(T);
	printf("\n\n");

	// 二叉树销毁
	BinaryTreeDestory(&T);

	return 0;
}