@TOC

一、前言

本章将讲解：

二叉树的概念以及各种接口实现

注：这里我们不会像之前数据结构那样去学习二叉树的增删查改，二叉树不是一个线性结构，并不适合用来储存数据，也就是增删查改并不适合它，这里我们主要是在它本身的性质上拓展

二、二叉树

1、二叉树概念

二叉树是一棵度不大于二的树，可能有左子树和右子树，也可能为空树

• 任意的二叉树都是由以下几种情况复合而成的：
  

2、链式存储

• 概念：

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系

• 通常的方法：

链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址

• 链式结构分类 ：

链式结构又分为二叉链和三叉链，当前我们所讲的是二叉链，当学到高阶数据结构如红黑树等会用到三叉链

• 图示：

三、链式二叉树的实现

1、接口展示

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;//数据
	struct BinaryTreeNode* left;//左子节点地址
	struct BinaryTreeNode* right;//右子节点地址
}BTNode;

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);

2、节点类型创建

注：这里我们主要学习二叉链表

二叉链表具有数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址

• 参考代码：

typedef char BTDataType;//数据类型

typedef struct BinaryTreeNode
{
	BTDataType data;//数据
	struct BinaryTreeNode* left;//左子节点地址
	struct BinaryTreeNode* right;//右子节点地址
}BTNode;

注：因为二叉树结构的特点（子树的根结点有且只有一个前驱，可以有最多两个后继）–是递归定义的，所以接下来对二叉树的多种操作需要依靠递归，可以快速解决

3、快速建树

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作

由于对二叉树结构掌握还不够深入，为了降低学习成本，这里手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，检验操作的正确性（等深入了解后再来学习二叉树真正的创建方式）

• 图示对应二叉树逻辑结构：

注：#代表NULL，即空树

//开辟节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

4、二叉树遍历

• 概念：

二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次

注：访问结点所做的操作依赖于具体的应用问题，遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础

• 遍历分类：

二叉树的遍历有前序/中序/后序的递归结构遍历：

• 前序遍历(Preorder Traversal 亦称先序遍历)——先访问根结点，再遍历其左子树，后遍历右子树
• 中序遍历(Inorder Traversal)——先访问左子树，再遍历其根节点，后遍历右子树
• 后序遍历(Postorder Traversal)——先访问左子树，再遍历其右子树，后访问根节点

注意：

1. 根据根节点访问的先后来决定是那种访问方式
2. 各类遍历的实现逻辑基本一致，只是顺序有所不同罢了

1）前序遍历

• 参考代码：

// 二叉树前序遍历(根左右)
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);//前序递归调用
	BinaryTreePrevOrder(root->right);
}

• 前序遍历示图：
  

2）中序遍历

• 参考代码：

// 二叉树中序遍历（左根右）
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);//中序递归调用
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

注：递归过程示图可以自己动手画解哦

3）后序遍历

• 参考代码：

// 二叉树后序遍历（左右根）
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);//后序递归调用
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

注：递归过程示图可以自己动手画解哦

4）层序遍历

• 概念：

除了前中后序遍历，还有层序遍历
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点
以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

• 逻辑示图：

• 遍历方式：

1. 这里需要使用我们的队列来解决
2. 先将根节点地址入队列，再将根节点的左右子节点也入队列（不为NULL的话）再将根节点出队列
3. 如果队列不为空，则访问现队头，将队头的左右子树也入队（不为NULL的话），入队后再将现队列头数据给出队列
4. 直到为空队列则层序遍历完毕

• 遍历示图：
  
• 注意：

1. 对于C语言首先我们需要实现队列
2. 该队列的数据类型为二叉树节点地址

注：对与非内置类型我们需要进行前置声明，否则编译器会当做不认识该类型并报错

• 示图：
  
• 参考代码：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		struct BinaryTreeNode* front = QueueFront(&q);//保存节点地址
		printf("%c ", front->data);
		QueuePop(&q);//出队列
		if (front->left)//带入孩子节点
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

5）遍历测试

• 测试代码：

int main()
{
	BTNode* root = CreatBinaryTree();

	BinaryTreePrevOrder(root);
	printf("\n");
	BinaryTreeInOrder(root);
	printf("\n");
	BinaryTreePrevOrder(root);
	printf("\n");
	BinaryTreeLevelOrder(root);
    printf("\n");
	BinaryTreeDestory(&root);
	return 0;
}

• 结果示图：

5、判断是否为完全二叉树

• 注意：

1. 对于该接口同样需要使用队列来实现
2. 完全二叉树的定义是有左子树才能存在右子树（注:我的理解）在这里我们也对二叉树进行层序遍历，唯一一点的区别是对于空树也进行入队列
3. 当出队列出到NULL时，对之后的队列数据进行检查如果多为NULL则是完全二叉树，否则不是

• 图示过程：
  
• 参考代码：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	assert(root);
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		struct BinaryTreeNode* front = QueueFront(&q);//保存节点地址
		QueuePop(&q);//出队列
		if (front == NULL)//出队列遇到空指针，直接退出循环
			break;
		else//不是空指针才能带入孩子节点，否则访问空指针报错
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	//遇到空节点，如果剩下的都是NULL则为完全二叉树
	//否则为不完全二叉树
	while (!QueueEmpty(&q))
	{
		if (QueueFront(&q))
		{
			QueueDestroy(&q);//返回前先销毁
			return 0;//0表示假
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);//返回前先销毁
	return 1;//非0表示真
}

6、二叉树销毁

• 注意：

1. 节点一次次动态开辟，也需要一次次来释放
2. 销毁当前节点时，需先将子节点销毁和置空，避免野指针
3. 对于销毁我们希望也将二叉树的根节点给销毁并置空，而根节点本身就是一个地址，这里就需要传入二级指针才能修改其指向对象

• 参考代码：

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)//root本身为地址，传入二级指针才能修改root
{
	if (root == NULL)//空树
		return;
	BinaryTreeDestory(&(*root)->left);//递归释放节点
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;//释放并且置空
}

• 递归展开图：

注：画递归图是一个理解递归操作很好的方式

7、二叉树节点个数

• 注意：

1. 为空树不计数
2. 不为空树则计数1，并且递归获取左右子树节点个数

• 抽象化思想：

二叉树节点个数==当前根节点+左右子树节点个数

注：如果对递归思想有问题的话，可以画递归展开图以便于理解，以下接口实现都同理

• 参考代码：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)//空树不计数
		return 0;

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//递归计数
}

8、二叉树叶子结点个数

• 注意：

1. 叶子结点的特点是左右子树都为空树
2. 如果当前节点为空树则计数0
3. 如果当前节点的左右子树都为空树则计数1
4. 不为叶子结点则继续递归计数

• 抽象化思想：

叶子结点个数==左右子树叶子结点个数（当前节点不为叶子结点的话）

• 参考代码：

// 二叉树叶子节点个数
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);//不是叶子结点则继续递归
}

9、二叉树第K层节点个数

• 注意：

1. 对于如何控制递归深度，这里我们使用k来控制递归层数
2. 首先判断k的合理性

• 抽象化思想：

第k层节点==左右子树第k层结点个数（当前节点不为第k层的话）

• 参考代码：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)//k用来控制递归次数
{
	assert(k >= 1);//断言k一定大于0
	if (root == NULL)//空树
		return 0;
	if (k == 1)//为所层数
		return 1;
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);//不是则递归
}

10、二叉树查找值为x的节点

• 注意：

1. 为空树则没找到
2. 不为空树则进一步检查值是否为x
3. 还不是的话，递归去左右子树寻找
4. 依旧没有找到的话则返回NULL

• 参考代码：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->left, x);//依次在左右子树中查找
	if (left != NULL)//找到了
		return left;

	BTNode* right = BinaryTreeFind(root->right, x);
	if (right != NULL)
		return right;

	return NULL;
	//return BinaryTreeFind(root->right, x);
}

11、二叉树的深度

• 注意：

1. 如果为空树则计当前层不存在
2. 不是空树则计当前层存在

• 抽象化思想：

当前层数加上左右子树的最大层数为二叉树的深度

• 参考代码：

//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int left = BinaryTreeDepth(root->left);//查找左右子树深度并比较
	int right = BinaryTreeDepth(root->right);

	return left > right ? left + 1 : right + 1;
}

四、测试

• 测试对应的二叉树：
  
• 测试代码：

BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}
int main()
{
	BTNode* root = CreatBinaryTree();
	printf("TreeSize:%d\n", BinaryTreeSize(root));
	printf("TreeLeafSize:%d\n", BinaryTreeLeafSize(root));
	printf("TreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));
	printf("BinaryTreeFind:%p\n", BinaryTreeFind(root, 'F'));
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

• 结果示图：
  

有问题的话可以留言，可以的话欢迎三连支持哦！