深入学习二叉树（BinaryTree）（纯小白进）

一、 前言

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。简言之，二叉树是数据结构中非常重要的东西，在很多OJ试题和笔试题中，都会出现它的影子；后续我们也会学到各种各样的树，比如二叉搜索树、AVL树、红黑树、B树等都是基于二叉树的高阶树。总之，现在把普通二叉树学好了，对以后的学习是十分有帮助的。

Tips：二叉树的学习与之前略有不同，我们不讨论普通二叉树的增删查改，因为对于普通二叉树来说，这些操作意义不大

二、 正文

2.1、 树的概念

2.1.1、 树的结构

• 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 有一个特殊的结点，称为根结点，根节点没有前驱结点 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
• 树可以理解为是递归定义的.

**这里需要注意的是:**树形结构中，子树之间不能有交集，否则就不是树形结构。

2.1.2、 树的小知识

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6。
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点。
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点。
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点。
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点。
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点。
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6。
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4。
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点。
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先。
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
• 森林：由m（m>0）棵互不相交的树的集合称为森林。

上面我们先认识一下树，以便我们接下来继续学习二叉树可以更好地理解二叉树。

2.2、 认识二叉树

2.2.1、 二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成d

从上图看出:

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树会有以下几种情况复合而成的：

2.2.2、 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 满二叉树是一种特殊的完全二叉树。简单来说，就是最后一层从左到右是不间断的节点。

以下两张神图,来源于网络:

如上图所示，这是一棵现实中的二叉树，我们看着很形象，也很容易理解 “二叉” 这个概念，不过计算机可不这样认为，在它眼中二叉树要么长这样 [1,2,3,4,5]，要么长这样 1->2->3->4->5
没错，二叉树在计算机中可以有两种表示形式

• 顺序结构
  • 即以数组的形式存储节点信息，这种结构一般用于存储完全二叉树
  • 比如接下来要学的堆，因为数组正好符合完全二叉树连续存储的要求
• 链式结构
  • 即以链表的形式存储节点信息，这种结构可以用于所有二叉树，本文代码结构也是以链式为主
  • 二叉树普遍都是不规则的，数组难以满足节点分散这个要求

知道结构后还需加以规则限制，二叉树的规则有

• 空树也可以看作二叉树
• 任何一棵二叉树，都可以分为根、左子树、右子树
• 二叉树中不存在度大于2的节点（度即当前节点的子树数量）
• 二叉树的子树有左右之分，顺序不可颠倒，即左边一定是左树

了解以上关于二叉树的相关性质，接下来，咱们来看一下关于二叉树的具体实现

2.3、 实现二叉树

这部分主要是实现一些简单功能，涉及大量递归知识。

2.3.1、 结构

前面说过，二叉树主要有两种表现形式，通常我们采用链式结构（链式二叉树）来实现。
任何一棵二叉树都有根、左、右三部分，细化到一个节点也是如此，因此链式二叉树在结构上分为以下三部分

1. 数据域，负责存放当前节点的元素信息
2. 左子树（左孩子），指向左树的指针
3. 右子树（右孩子），指向右树的指针

二叉树的实现和创建如下：

typedef char BTDataType;	//二叉树的数据类型

typedef struct BinaryTreeNode
{
	BTDataType data;	//存储节点的元素信息，每个节点都有
	struct BinaryTreeNode* left;	//左子树（左孩子）
	struct BinaryTreeNode* right;	//右子树（右孩子）
}BTNode;
//申请节点
BTNode* BuyNode(BTDataType x) {
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL) {
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreateTree() {
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

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

}

注意： 因为链式二叉树每次都需要单独申请节点，因此没有初始化函数，但每个节点都有初始化状态： *数据域置0，左右子树都指向空* 。二叉树的销毁需要借助递归+后序遍历的方式销毁，后面会提及

2.3.2、 节点数

为了方便后续功能的讲解，先在假设存在一棵二叉树，形状如下所示，代码实现时由自己手动进行申请、赋值、链接

关于二叉树的节点数

• 对于二叉树来说，不为空的都可以称为一个节点，如上图所示，共计5个节点，其中节点 'A ’ 为根节点（root）
• 统计二叉树节点需要巧妙利用递归，大问题化为小问题

如何递归呢？
众所周知，递归是个技巧，代码极其简洁，但不太好懂，也不太好调试，并且存在很多问题（栈溢出、运行效率低等），但这丝毫不妨碍我们在这里使用它，理由如下：

• 首先我们需要统计的是整棵二叉树的节点数，已知任何一棵二叉树都可以看成 n 棵树组成的树，而每二叉棵树都有根、左、右三部分组成
• 其中如果根不为空，那么这个节点就是有效节点，可以参与统计，为空就不参与
• 现在我们只考虑一个节点是否合法，如果合法，那么返回1，兵分两路走向它的左右子树，继续判断
• 观察发现二叉树肯定存在边界，比如上图，最底层的空就是边界，当我们往下递归，碰到空时，直接返回，不再往下判断
• 整个过程符合递归要求：有终止条件+接近手段，我们可以从根节点开始往下递出，最后返回每次判断所得到的节点数就行了（要么是0，要么是1），这就是递归
• 这个思想比较重要，后面很多函数都是走的这个思想

长话短说，借助递归+二叉树的特性，将整个二叉树走一遍，如果发现当前节点为空，就不往下走，否则会一直往下走，总体路径为 根 -> 左 -> 右，最后会回归每次判断所得的节点数，整个过程如图所示，这是一个比较长的 动图，耐心看完

代码实现如下所示

// 二叉树节点个数
int TreeSize(BTNode* root)
{
	//一级指针，不能断言，不然就无法递归
    //就是说，这里root为空是递归终止的条件，如果断言，就永远不可能达到终止，一直递归下去
	if (!root)
		return 0;
	return 1 + TreeSize(root->left) + TreeSize(root->right);	//根 + 左 + 右
    //或者
    //return root==NULL?0: TreeSize(root->left) + TreeSize(root->right) + 1;
}

注意： 除了单纯统计二叉树节点数外，还有一个变种：统计第k层节点数，需要借助k，每下潜一层，k-1，直到 k 为1时，才计数返回。

代码实现如下所示

//求第k层的节点个数
//根的第k层=左子树的第k-1层+右子树的第k-1层
int TreeKLevel(BTNode* root, int k) {
	//没有说k是负层的
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	int leftK = TreeKLevel(root->left, k - 1);
	int rightK = TreeKLevel(root->right, k - 1);
    //不建议直接写成下面,是因为每次计算的话都要去在计算一遍结果，效率很低
    //return TreeKLevel(root->left, k - 1)+ TreeKLevel(root->right, k - 1);
	return leftK + rightK;
}

2.3.3、 树深度

二叉树的深度，指根节点的左右子树深度中的较大值，假如根的左子树深度为3，右子树的深度为1，那么整棵树的深度为3，同样的，需要借助递归，步骤如下

• 设两个变量：leftHeight 和 rightHeight ，分别用来存储左右子树的深度
• 左右子树的深度即左右子树的节点数，统计方式与上面函数类型
• 得到这两个深度后，判断谁是较大的一方，返回它
• 这也是个典型的递归，终止条件为节点为空，接近手段为向下移动
  这个的代码量也很少，无非就是比上面多了两句

//二叉树的深度
int TreeHeight(BTNode* root) {
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

2.3.4、 前、中、后序遍历 + 销毁

学校最喜欢考的东西，其实很简单，我们直接三剑齐发，再附带一个销毁
遍历思想：

• 前、中、后序思想一致，无非就是出发点和结束点不一样罢了
• 前序：根出发，最右子树结束
• 中序：最左子树出发，最右子树结束
• 后序：最左子树出发，根结束
• 三种方式遍历代码量可以说是完全一致，只不过顺序不同罢了

关于这三种遍历方式，我想直接通过三张动图解决，单独将没啥意义，复读而已，还不如动图来的直观

2.3.4.1、 前序遍历

代码如下

// 二叉树前序遍历 
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	} 
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
	
}

2.3.4.2、 中序遍历

代码如下

// 二叉树中序遍历
void InOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);

	InOrder(root->right);

}

2.3.4.3、 后序遍历

代码如下

// 二叉树后序遍历
void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

2.3.4.4、 二叉树的销毁

二叉树的销毁其实和后续遍历差不多，不过是把打印换成了 free 当前节点，其实也很好理解，想要销毁整棵二叉树就得从最后一层开始往上销毁，如果先销毁的是上面的节点，那么下面的节点就丢失了，如此看来，只有后序符合这个要求，通过后序遍历能完美销毁整棵二叉树，代码如下

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

2.4、 玩转二叉树

二叉树的热身环节已经结束了，现在准备进入更高难度的函数，带你从多种角度玩转二叉树

2.4.1、 构建树

首先来看看这个热门题：根据一个已知数组（存放的是某二叉树前序遍历的结果，# 表示空），构建出原二叉树。 题目的意思很简单，就是提供某二叉树的前序遍历结果，包括空也提供了，让我们根据这个结果，还原出原来的二叉树，前序遍历我们已经解决了，反过来还不简单？步骤如下

• 根据题目可知，数组中的 # 表示空，反过来说，如果遇到的不是 #，那就说明这是一个节点
• 如果是 # ，直接 return NULL；否则就申请一个节点，将此节点看作根节点
• 每次递归函数要么产生新节点，要么直接返回 NULL，利用前序遍历思想，在得到根节点后，递归链接其左右孩子，至于孩子是节点还是 NULL ，得看递归结果
• 最后再返回当前节点信息，除了根节点可以返回出函数外，其他的节点信息都是返回给上一层节点，即成为他们的左右孩子，返回时，整棵树才会被链接起来

长话短说，这就是一个递归遍历数组+申请节点链接的程序，每次递归，都得保证数组递归遍历能往后走，前序思想为 根、左、右，大问题转小问题：先保证这个节点存在，再链接其左右孩子。代码实现时需要多加小心，比如传递数组下标时，要传地址，不然数组都走不下去，还有递归终止条件为当前数组值是否为 # ，接近手段就是数组的遍历，具体看**动图**实现：

代码如下

// 通过前序遍历的数组"A B D # # E # H # # C F # # G # #"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert(a);
	//如果一开始就为 # 就没必要创建了
	if (a[*pi] == '#')
	{
		(*pi)++;	//向后移动，找到下一个值
		return NULL;
	}
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

	node->data = a[(*pi)++];	//赋值，并向后移动

	node->left = BinaryTreeCreate(a, n, pi);	//左右链接
	node->right = BinaryTreeCreate(a, n, pi);

	return node;	//最开始的节点就是根节点
}

注意： 参数【数组下标】，需要传地址，不然数组遍历就无法进行下去

2.4.2、 层序遍历

层序遍历，又被称为 广度优先遍历，之前是前、中、后序都属于深度优先遍历，所谓广度优先，就是一层一层的遍历，比如最开始的演示二叉树，层序遍历结果为：A B C D E
层序遍历不必依靠递归，但是需要借助队列，因为队列的性质很符合广度这个要求（如果大家对队列存在疑惑的，大家可以移步这边）

• 队列的性质：先进先出，后进后出(FIFO)

具体实现步骤：

• 核心思想：先将根节点入队，然后出队，带根节点的下一层入队（如果存在的话）
• 当根节点入队，出队打印后，把第二层的节点入队
• 如此重复，直到每层所有节点遍历完毕
• 循环终止条件是队列是否为空，当队列为空时，说明整棵二叉树都入过队了

层序遍历具体 **动图**如下 ：

代码如下

// 层序遍历
void  LeverOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	//root不为空，就把它push到队列中
	while (!QueueEmpty(&q)) {
		//用树节点保存出队列的节点
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		//如果左右子树不为空，就进队列,进指针，不是数值
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

注意： 这里借助了队列，需要引出相关头文件，入队列的元素是指向二叉树节点的指针，即二叉树节点 在队列相关头文件中，需要特别注意一下，把队列`元素类型修改为对应类型

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

这是力扣上的中等题，牛客上的困难题，也是本文的压轴戏
完全二叉树，指连续的二叉树，判断是否为完全二叉树的关键就是 判断当前树是否连续（每一层都要连续），涉及到层序遍历，一样需要借助队列，不过循环终止条件和入队条件不同，也不需要打印了，只是多了一个判断，步骤如下：

• 提前统计出二叉树的节点树，存储在变量 countNode 中，循环 countNode 次
• 核心思想仍然为 出上一层，带下一层
• 原层序遍历中的打印当前出队得到的节点，会被替换成判断当前节点是否为空
• 原层序遍历中，为空的节点是入不了队的，但这里不管当前节点的左右子树是否为空，都入队，假如不是完全二叉树，那么肯定就存在循环未终止的情况下，出队取到空节点
• 用节点数作为循环终止条件，如果是完全二叉树，是肯定取不到空节点的，因为它根本没机会入队
• 这样一来，问题就很好解决了，无非就是 入队、出队、判断、入队 如此重复
  代码如下

//判断是否为完全二叉树
bool  BTComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//为空就跳出来
		if (front==NULL) {
			break;
		}
		else {
			//不为空就把他的左右子节点push到队列中进去
			QueuePush(&q, root->left);
			QueuePush(&q, root->right);
		}
	}
	//再把队列全部出空
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果有非空，说明队列中还存在非空节点，不是完全连续
		if (front) {
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

三、总结

以上就是二叉树的全部内容了，回顾全文，我们从介绍树的相关性质，到了解了二叉树的相关概念，学习了二叉树的基础功能和实现，相信你在看完本文后，一定能学到很多干货，轻松理解二叉树！，下一站：堆