二叉树【数据结构】

前言：
之前讲到过：
数据结构：是存在一种或多种特定关系的数据元素的集合。其中，一种或多种特定关系，会分为：逻辑结构和物理结构(也叫存储结构)。

• 逻辑结构：数据对象中数据元素之间的相互关系。其中逻辑结构又分为多种
• • 集合结构：集合结构中的元素属于同集合，没有其他关系
• • 线性结构：数据元素之间是一对一的关系
• • 树形结构：数据元素之间是一对多的层次关系
• • 图形结构：数据元素之间是多对多的的关系

物理(存储)结构：

• 线性(顺序)存储
• 链式存储

首先简单滴介绍一下树

树：是一种对多的层次关系
树是一种非线性的数据结构，由节点（或称为顶点）和边组成。它可以表示为一个层次结构，其中每个节点都可以有零个或多个子节点。树的一个节点称为其父节点的子节点，而父节点则称为其子节点的父节点。树的顶部节点称为根节点，没有父节点的节点称为叶节点。树可以用于表示层次关系，如文件系统的目录结构或组织结构图。

关于结点的分类：

• 结点的度：结点拥有的子树
• 叶子结点：度为0的结点
• 分支结点：度不为0的结点
• 树的度：分支结点度的最大值

二叉树

1. 二叉树定义

二叉树定义：由一个根结点和两棵互不相交、分别称为根结点的左右子树的二叉树组成

二叉树的特点：

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点
• 左右子树是有顺序的不能颠倒

二叉树的基本形态：

• 空二叉树
• 只有一个根结点
• 根节点只有左子树
• 根结点只有左子树
• 根结点既有左子树又有右子树

满二叉树: 在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上
满二叉树的特点：

• 叶子结点只能出现在最下一层
• 分叶子结点的度一定是2
• 在相同深度的二叉树中，满二叉树的结点个数最多，叶子树最多

完全二叉树:
除了最后一层外，也就是前n-1层的结点都必须是满的，最后一层的结点从左到右连续存在，不能有间隔
完全二叉树的特点：

1. 叶子只能出现在最后两层
2. 最后一层从左到有是连续的

二叉树的存储定义

二叉树的顺序存储
二叉树的链式存储

这里我们采用链式存储方式

存储结构:

代码展示

typedef int BTDataType;

typedef struct BinaryTreeNode 
{
	BTDataType val;	//二叉树的值
	struct BinaryTreeNode* left;	//指向左子树
	struct BinaryTreeNode* right;	//指向右子树
}BinaryTree;

2. 遍历二叉树

二叉树遍历：从根结点出发，按某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次

因为我们习惯从左到右的习惯，二叉树的遍历方法分为 前序、中序、后序、层序遍历

这里的二叉树的存储结构我们使用链式存储

(1) 前序遍历

前序遍历(先根遍历)： 若二叉树为空，返回空，否则访问根结点，然后 前序遍历左子树，再 前序遍历右子树。

代码展示

//前序遍历二叉树
void PreOrderTree(BinaryTree* root) 
{
	//如果遇到空打印N 并返回函数调用的地方
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ",root->val);	//打印结点的值
	PreOrderTree(root->left);	//先序遍历左子树
	PreOrderTree(root->right);	//先序遍历右子树
}

如图：

(2) 中序遍历

中序遍历(中根遍历)： 若二叉树为空，返回空，否则 中序遍历左子树，再访问根结点，中序遍历右子树。

代码展示

//中序遍历二叉树
void InOrderTree(BinaryTree* root)
{
	//如果遇到空打印N 并返回函数调用的地方
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrderTree(root->left);	//中序遍历左子树
	printf("%d ", root->val);
	InOrderTree(root->right);	//中序遍历右子树
}

(3) 后序遍历

后序遍历(后根遍历)： 若二叉树为空，返回空，否则 后序遍历左子树 , 后序遍历右子树 , 再访问根结点。

“#” 表示空

(4) 层序遍历

层序遍历：这里我们需要借助队列来实现，原理：上一层出来会依次带入下一层进入(队列:先进先出)

思路：

1. 根结点不为空就进队(注意是结点进队，不是结点的值进队)
2. 队头结点进行出队，同时下一层进队(即根结点的左右子树进队)
3. 当队列为空时，层序遍历完成

代码展示

//二叉树的层序遍历
void BinaryTreeLevelOrder(BinaryTree* root) 
{
	Queue pq;	//定义队列变量
	//初始化对队列
	InitQueue(&pq);

	//当root不为空时,就进队
	if (root != NULL)
	{
		//结点入队
		QueuePush(&pq,root);
	}
	//队列不为空就继续进行层序遍历
	//队列为空时，层序遍历完成
	
	int levelsize = 1;
	while ( !QueueEmpty(&pq) )
	{
		//一层一层出
		while (levelsize--)
		{
			//队头出队，队尾进队
			//先获取队头结点
			BinaryTree* headnode = QueueFront(&pq);
			//上一层出队
			QueuePop(&pq);
			//打印队头结点的值
			printf("%d- ", headnode->val);

			//下一层进队，即队头结点的左右子树结点入队
			//前提时，左右子树结点不能为空
			if (headnode->left)
			{
				QueuePush(&pq, headnode->left);
			}
			if (headnode->right)
			{
				QueuePush(&pq, headnode->right);
			}
		}
		printf("\n");
		levelsize = QueueSize(&pq);
	}

	//销毁队列
	QueueDestroy(&pq);

}

3. 二叉树的相关操作

(1) 二叉树的初始化

这里使用动态函数来开辟二叉树的结点，给结点赋值同时进行把该节点的左右子树暂时置NULL,最后通过返回该结点的地址(避免使用二级指针了)

代码展示

//二叉树的初始化
BinaryTree* InitTreeNode(int x) 
{
	//动态开辟
	BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
	assert(node); //断言避免指针为空
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;	//通过返回函数来进行创建结点
}

(2) 二叉树的结点的手动创建

有时候方便调试，需要手动创建二叉树
同创建完成后通过返回根节点的地址

代码展示

//二叉树的手动构建
BinaryTree* CreateTree() 
{
	BinaryTree* node1 = InitTreeNode(1);
	BinaryTree* node2 = InitTreeNode(2);
	BinaryTree* node3 = InitTreeNode(3);
	BinaryTree* node4 = InitTreeNode(4);
	BinaryTree* node5 = InitTreeNode(5);
	BinaryTree* node6 = InitTreeNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;	//返回根结点

}

(3) 二叉树结点的个数

即计算有多少结点
先从根结点开始，若根节点为空，就返回0，如果不为空，递归左子树，然后递归右子树。(当然这里递归顺序没有要求，也可以先进行递归右子树然后再递归左子树)

使用分治思想：
树的结点个数 = 左子树结点个数 + 右子树结点个数 + 1 ;

代码展示

//计算二叉树结点的个数
int BinaryTreeSize(BinaryTree* root) 
{
	//根结点开始
	//访问左子树，访问右子树
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->left)+BinaryTreeSize(root->right) + 1;
}

优化一下：

int BinaryTreeSize(BinaryTree* root) 
{
	return root == NULL ? 0 : BinaryTreeSize(root->left)+BinaryTreeSize(root->right) + 1;
}

(4) 二叉树叶子结点的个数

叶子结点：结点度为0的结点
使用递归，返回条件为

1. 如果根结点为空返回 0
2. 如果根结点不为空 且 左右子树都为空 说明是叶子返回1
3. root 不是空,也不是叶子，分治法，叶子数 = 左子树的叶子+右子树的叶子

代码展示

//计算叶子结点的个数
int BinaryTreeLeafSzie(BinaryTree* root) 
{	
	//分治法
	// 叶子结点树 = 左子树叶子 + 右子树叶子
	//结点为空返回0
	if (root == NULL)
		return 0;
	//root不为空，左右子树为空是叶子,返回1
	if (root->left == NULL && root->right == NULL)
		return 1;
	//root不为空且左右子树都不为空,继续递归左右子树
	return BinaryTreeLeafSzie(root->left) + BinaryTreeLeafSzie(root->right);
}

(5) 二叉树的高度

分治法
树高 = 左子树与右子树中较高的树 +1
递归条件

1. root 为空 返回 0
2. root 不为空 计算左右子树中较高的，返回较高的+1

代码展示

//计算二叉树的高度
int BinaryTreeHeight(BinaryTree* root) 
{
	//树高 = 左子树与右子树中较高的树 +1
	if (root == NULL)
		return 0;
	//记录左子树高
	int leftHeight = BinaryTreeHeight(root->left);
	//记录右子树高
	int rightHeight = BinaryTreeHeight(root->right);
	//返回较高树同时+1
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

方法二：

//计算树高方法二
int BinaryTreeHeight(BinaryTree* root)
{
	//树高 = 左子树与右子树中较高的树 +1
	if (root == NULL)
		return 0;
	return fmax(BinaryTreeHeight(root->left),BinaryTreeHeight(root->right))+1;
}

如图：

(6) 第k层结点个数

计算第k 层的结点个数，这里我们可以转化为去求 左子树的 k - 1 层和右子树的 k - 1 层 的结点的个数

递归条件：

1. root 为空，返回0
2. root不为空且 k == 1,返回1
3. root不为空且 k > 1, 返回左子树的 k - 1 层 + 右子树的 k - 1 层

代码展示

//二叉树第k层结点的个数
int BinaryTreeLevelSizeK(BinaryTree* root, int k) 
{
	assert(k >= 1); //层数最小为1
	//第k层结点个数 = 左子树k-1层 + 右子树k-1层 的结点个数
	if (root == NULL)
		return 0;
	//结点不为空，k == 1,返回1
	if (k == 1)
		return 1;
	//k>1,继续递归左右子树的 k-1 一层
	return BinaryTreeLevelSizeK(root->left,k-1) + BinaryTreeLevelSizeK(root->right,k - 1);
}

(7) 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

当元素的值是 ‘#’ 时，表示为空，数组下标加一；不是‘#’时，动态分配内存空间并给结点赋值。然后递归左右子树，最后返回根结点

代码展示

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BinaryTree* BinaryTreeCreate(BTDataType* arr, int* pi) 
{
	//# 表示为空
	if (arr[*(pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	
	//不是＃，就动态分配内存空间
	BinaryTree* root = (BinaryTree*)malloc(sizeof(BinaryTree));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//结点赋值
	root->val = arr[(*pi)++];
	//递归左右子树
	root->left = BinaryTreeCreate(arr,pi);
	root->right = BinaryTreeCreate(arr,pi);
	
	//返回根结点
	return root;
}

如图：

(8) 二叉树查找值为x的结点

首先当根结点为空直接返回空，当root不为空且结点值等于x的时候直接返回结点，当root不为空且结点值不等于x的时候，递归左右子树(通过记录左右子树的结点来避免重复去找，还需注意左右结点为空的情况)

代码展示

//二叉树查找值为x的结点
BinaryTree* BinaryTreeFind(BinaryTree* root, BTDataType x)
{
	//结点为空直接返回空
	if (root == NULL)
		return NULL;
	//root不为空，结点值 = x ,就返回结点
	if (root->val == x) 
	{
		return root;
	}
	//root不为空，结点值 != x ，递归左右子树
	//但是递归左右子树时，注意子树为空的情况
	//记录结点，避免重复去找
	BinaryTree* left = BinaryTreeFind(root->left, x);
	if (left)
		return left;
	BinaryTree* right = BinaryTreeFind(root->right, x);
	if (right)
		return right;

	//左右结点都为空，返回空
	return NULL;
}

(9) 判断是否为完全二叉树

除了最后一层外，也就是前n-1层的结点都必须是满的，最后一层的结点从左到右连续存在，不能有间隔

完全二叉树

不是完全二叉树 ，情况一：

情况二 :

判断是否为完全二叉树，我们需要进行借助层序遍历,层序遍历时当遇到结点为空时，跳出循环。然后在借助一次层序遍历，如果遇到了不为空的结点，即不是完全二叉树。否则是完全二叉树。

代码展示

//判断是否为完全二叉树
bool BinaryTreeComplete(BinaryTree* root)
{
	//借助层序遍历
	//遇到空时，再层序遍历后面都为空，就是完全二叉树
	//否则不是
	Queue pq;
	QueueInit(&pq);
	//结点不为空就进队列
	if (root)
	{
		QueuePush(&pq, root);
	}
	while (!QueueEmpty(&pq))
	{
		//先取队头
		BinaryTree* headnode = QueueFront(&pq);
		//上一层出队
		QueuePop(&pq);
		//只要遇到空就停止层序遍历
		if (headnode == NULL)
		{
			break;	//跳出循环
		}
		//下一层进队
		QueuePush(&pq,headnode->left);
		QueuePush(&pq,headnode->right);
	}

	//再一次层序遍历，只要遇到结点不为空就不是完全二叉树，否则是完全二叉树
	while (!QueueEmpty(&pq)) 
	{
		//先取队头
		BinaryTree* headnode = QueueFront(&pq);
		//上一层出队
		QueuePop(&pq);
		if (headnode)	//结点不为空，此树不是完全二叉树
			return false;	
	}
	
	return true;
}

上述中使用了两次层序遍历

下方的另种方法只使用了一次层序遍历的方法，通过记录值进行确定,当遇到空的时候，记录值为true,当在层序遍历中，发现记录值为true 且 结点不为空，说明不是完全二叉树

//判断是否为完全二叉树 法二
bool BinaryTreeComplete(BinaryTree* root) 
{
	//使用一次层序遍历，遍历时，对空进行记录
	Queue pq;
	QueueInit(&pq);
	

	//如果根结点不为空，结点入队
	if (root)
	{
		//注意进队的是结点，不是结点的值
		QueuePush(&pq, root);
	}

	//使用bool类型进行记录
	bool hasEmpty = false;

	while (!QueueEmpty(&pq))
	{
		//获取队头元素
		QDataType headnode = QueueFront(&pq);
		//出队
		QueuePop(&pq);
		if (headnode == NULL) 
		{
			//当队头元素为空时，记录值为true
			hasEmpty = true;
		}
		else
		{
			//当队头结点不为空时，记录值为true，说明前面已经遇到空且后面的结点有不为空的(即不是完全二叉树)
			if (hasEmpty == true)
			{
				//不是完全二叉树
				return false;
			}

			//记录值为false时，没有遇到空
			//继续层序遍历
			//前一层出队，后一层入队
			QueuePush(&pq,headnode->left);
			QueuePush(&pq,headnode->right);
		}
	}
	return true;
}

(10) 二叉树的销毁

把二叉树的所有不为空结点进行 一 一 释放

代码展示

//二叉树的销毁
void BinaryTreeDestroy(BinaryTree* root) 
{
	//需要把二叉树的所有不为空结点进行一一释放
	//root 为空 直接返回
	if (root == NULL)
		return;
	//root不为空，递归左右子树
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}