搞定二叉树

树的名词与概念

在这里插入图片描述

子树：树是一个有限集合，子树则是该集合的子集。就像套娃一样，一棵树下面还包含着其子树。比如，树T1 的子树为树T2、T3、T4，树T2的子树为 T5、T6 。上图中还有许多子树没有标记出来。

结点(Node)：一个结点包括一个数据元素和若干指向其子树分支。比如，在树T1 中，结点A 包括一个数据元素A 和三个指向其子树的分支。上图中共有 17 个结点。

根结点(Root)：一颗树只有一个树根，这是常识。在数据结构中,“树根”即根节点。比如，结点A 是树 T1 的根结点; 结点C 是树T1 的子结点，是树 T3 的根结点。

度(Degree)：一个结点拥有的子树数。比如，结点A 的度为 3，结点G 的度为 3，结点H 的度为 1。

叶子(Leaf)/ 终端结点：度为 0 的结点被称为叶子结点，很形象吧。比如，对于树 T1来说，结点F、I、K、L、M、N、O、P、Q 均为叶子节点。

分支结点 / 非终端结点：和叶子结点相对，即度不为 0 的结点。

内部结点：顾名思义，在树内部的结点，即不是根结点和叶子结点的结点。

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

堂兄弟节点：双亲在同一层的节点互为堂兄弟节点；如上图：E、G、H互为堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

层次(Level)：从根结点开始，根为第一层，根的孩子为第二层，依次往下。比如，结点K 在树 T1 中的层次为 4。

深度(Depth)/ 高度：指树的最大层次。比如，树 T1 的高度为 4 。

有序树: 树中任意节点的子结点之间有顺序关系，这种树称为有序树。

无序树 : 树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树。

森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

什么是二叉树

满足以下两个条件的树称之为二叉树：

1、本质上为有序树；
2、每个结点的度不能超过2，即结点的度仅能为0，1，2。

二叉树地性质

1、二叉树的第i层上至多有2^(i-1) 个结点；
2、如果二叉树的深度为K，那么此二叉树最多有2^k - 1个结点，最少有h个结点；
3、对任意一棵二叉树，如果其叶子结点数，也就是度为0的节点数为n0,度为2的结点数为n2，则n0=n2+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设节点数为 n1），那么总结点数 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1和 n2表示的，即 B=n1+2*n2。所以，n 用另外一种方式表示为 n=n1+2*n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

在这里插入图片描述
4、具有n个结点的满二叉树深度为log2^(n+1)；
5、在非空二叉树中，第i层的结点总数不超过2^i - 1, i>=1；
6、具有n个结点的完全二叉树的深度为log2^n + 1 (表示向下取整)；
7、最多只有一个度为1的节点：n1=0或1，n0 = n2 + 1，n0 + n2 一定是奇数；
8、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I>1，则其父结点的编号为I/2；

如果2I<=N，则其左孩子（即左子树的根结点）的编号为2I；若2*I>N，则无左孩子；

如果2I+1<=N，则其右孩子的结点编号为2I+1；若2*I+1>N，则无右孩子。

二叉树类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。（如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。）
在这里插入图片描述

完全二叉树除了满足普通二叉树的性质外，还满足以下性质：

n个结点的完全二叉树的深度为⌊log2n⌋+1; （注：⌊ ⌋表示向下取整）
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号，对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
1). 当 i >1 时，父结点为结点 ⌊i/2⌋ 。（i=1 时，表示的是根结点，无父结点）

2). 如果 2i>n（总结点的个数），则结点 i 肯定没有左孩子（左叶子结点）；否则其左孩子是结点 2i 。

3). 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。（如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。）
在这里插入图片描述

满二叉树除了满足普通二叉树的性质，还具有以下性质：

1、满二叉树中第 i 层的节点数为 2^(i-1)个。
2、深度为 k 的满二叉树必有 2^k - 1 个节点，
叶子节点数为 2^(k-1) 。
3、满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4、具有 n 个节点的满二叉树的深度为 log2^(n+1)。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。(平衡二叉树是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。它是二叉排序树的一个进化体，它有几种实现方式：红黑树、AVL树)
在这里插入图片描述

平衡因子：平衡二叉树是在二叉查找树的基础上进行构建，为了维持平衡二叉树的平衡，那么就需要一种机制来判断平衡二叉树是否是平衡的。这种机制就叫做平衡因子。平衡二叉树上某个结点的左子树深度减去右子树深度的值，就称为此结点的平衡因子。
最小不平衡树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡树。

平衡二叉树特点:

1、平衡二叉树是一种二叉查找树
2、每个结点的左子树的高度减去右子树的高度的绝对值不超过1
3、空树和左右子树都是平衡二叉树
4、相比红黑树，平衡二叉树比较适用于没有删除的情况

二叉搜索树（又称: 二叉排序树、二叉查找树）

在这里插入图片描述

二叉搜索树：可以为空树，或者是具备如下性质：

A. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

B. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

C. 任意节点的左、右子树也分别为二叉搜索树;

还有一种特殊情况：
在这里插入图片描述

这种情况下，二叉搜索树已经变更为链表，搜索一个元素的时间复杂度从O( log2^n )退化为O(n), 出现这种情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树。

什么是左旋？

左旋：指将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点
在这里插入图片描述

什么是右旋？

右旋：指将根节点的左侧往右拉，原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点
在这里插入图片描述

失衡：当我们在一个平衡二叉树上插入一个结点时，有可能会导致失衡，即出现平衡因子绝对值大于 1 的结点，如下图，当插入结点后，其中key为53的结点失去了平衡，我们称该结点为失衡结点，我们必须重新调整树的结构，使之恢复平衡
在这里插入图片描述

不一定只有一个结点失去平衡，有可能插入一个结点会让多个结点失衡。这时候找最小的失衡子树的根节点作为失衡结点。
恢复平衡：那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？先来看平衡调整的四种类型：
在这里插入图片描述

举个例子：如第一个，当平衡二叉树为AB时，插入一个C结点，使得失衡了，失衡结点为A，此时因为C结点插入的位置为失衡结点的左孩子的左孩子，所以是LL型，以此类推。

为了恢复平衡，针对每一种都不一样，但目的都是调整为平衡的，且不能违背二叉搜索树的性质：如下图是每种失衡类型的解决方法，每个都不太一样，目的都是一样的，把key的值为中等的变为树的根，最小的放在左孩子，做大的放右孩子，通过这一目的，降低树的高度，也不用死记硬背。
在这里插入图片描述

AVL树

AVL树是根据它的发明者G.M.Adelson-Velsky和E.M.Landis命名的。它是最先发明的自平衡二叉查找树，也被称为高度平衡树。
在这里插入图片描述

AVL树本质上还是一棵二叉搜索树，它的特点是：
1、本身首先是一棵二叉搜索树。
2、带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。AVL实现平衡的关键在于旋转操作。

红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。因而，红黑树是相对接近平衡的二叉树，并不是一个完美平衡二叉查找树
在这里插入图片描述

红黑树的性质：
1、结点不是红色就是黑色
2、根节点是黑色的
3、每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
4、从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
5、每个叶子结点都是黑色的(叶结点即指树尾端NIL指针或NULL结点)

红黑树与AVL树的比较 ：

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( log2^n)，红黑树不追求绝对平衡，只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。

对于完全二叉树的存储，仅需对其从根节点开始仅需编号，使用数组存储编号即可。取出式依据完全二叉树由左到右分布的性质恢复即可。

在这里插入图片描述

在这里插入图片描述
链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

在这里插入图片描述

二叉树遍历：线性化

#include <iostream>

typedef int ElemType;
typedef struct TreeNode
{
	//数据域
	ElemType data;
	//指针域，左孩子节点、有孩子节点
	TreeNode *left, *right;
	TreeNode(int val) : data(val), left(nullptr), right(nullptr) {
	}
}Node;

typedef struct LinkedNode {
	//数据域
	TreeNode *node;
	//指针域，指向下个节点
	LinkedNode *next;
	LinkedNode(TreeNode *n): node(n), next(nullptr){
	}
}LinkedQueue;

LinkedNode *head = nullptr;
LinkedNode *tail = nullptr;

LinkedNode* LinkedNodeInit() {
	TreeNode* node = new TreeNode(-1);
	LinkedNode* temp = new LinkedNode(node);
	head = temp;
	tail = head;
	return head;
}

void Push(TreeNode* node) {
	LinkedNode* next = new LinkedNode(node);
	tail->next = next;
	tail = next;
}

LinkedNode* Pull() {
	head = head->next;
	return head;
}
//层次遍历
void LeveOrder(TreeNode* node)
{
	LinkedNodeInit();
	Push(node);
	while (head != nullptr) {

		LinkedNode* linknode = Pull();
		if (!linknode)
			break;
		std::cout << linknode->node->data << "->";
		if(linknode->node->left)
			Push(linknode->node->left);
		if (linknode->node->right)
			Push(linknode->node->right);
	}

}
//先序遍历 根左右
void PreOrder(TreeNode* node) {
	//节点为空，什么都不做
	if (node != NULL) {
		//访问节点数据
		std::cout << node->data << "->";
		//递归地访问左子树
		PreOrder(node->left);
		//递归地访问右子树
		PreOrder(node->right);
	}
}
//中序遍历 左根右
void InOrder(TreeNode* node) {
	//节点为空，什么都不做
	if (node != NULL) {
		//递归地访问左子树
		InOrder(node->left);
		//访问节点数据
		std::cout << node->data << "->";
		//递归地访问右子树
		InOrder(node->right);
	}
}
//后序遍历 左右根
void PostOrder(TreeNode* node) {
	//节点为空，什么都不做
	if (node != NULL) {
		//递归地访问左子树
		PostOrder(node->left);
		//递归地访问右子树
		PostOrder(node->right);
		//访问节点数据
		std::cout << node->data << "->";
	}
}

int main()
{
	//二叉树遍历： 线性化
	TreeNode child10(10), child7(7), child13(13), child5(5), child9(9), child11(11), child18(18),
		child3(3), child6(6), child8(8), child12(12);

	child10.left = &child7;
	child10.right = &child13;
	child7.left = &child5;
	child7.right = &child9;
	child13.left = &child11;
	child13.right = &child18;
	child5.left = &child3;
	child5.right = &child6;
	child9.left = &child8;
	child11.right = &child12;

	PreOrder(&child10);//先序遍历: 10->7->5->3->6->9->8->13->11->12->18->
	std::cout << std::endl;
	InOrder(&child10);//中序遍历: 3->5->6->7->8->9->10->11->12->13->18->
	std::cout << std::endl;
	PostOrder(&child10);//后序遍历: 3->6->5->8->9->7->12->11->18->13->10->
	std::cout << std::endl;
	LeveOrder(&child10);//层次遍历: 10->7->13->5->9->11->18->3->6->8->12->
}