【数据结构篇】-树（共计两万字，你真的搞懂了它吗）

友情链接：C/C++系列系统学习目录

🚀树

🚢一、树的原理精讲

（一）树的定义

之前我们一直在谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构——“树”

树：树是由n（n>=0）个有限结点组成一个具有层次关系的集合。当n = 0时，称为空树。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有且仅有一个特定的称为根的结点。
• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。
• 树的根结点没有前驱（父节点），除根结点外的所有结点有且只有一个前驱（父节点）。
• 树中所有结点可以有零个或多个后继（子结点）。

以上可以看出，在树的定义中又用到了树的概念，显然是一种递归的方式，所以，树不单单是一种分层结构，还是一种递归的数据结构

（二）基本术语

区别说明：

和我之前在线性表中说的一样，在C语言中，我们一般是从0开始第一个下标的，但我们数数都是从1开始数的，在大多数书记讲解中，树的计数，比如：深度、高度、层级以及其它许多数据结构叔叔起始也是1，如果为了和C语言下标法嵌合，我们也可以将这些从0开始数，只是在代码实现上需要改动一点而已。

为了习惯C语言下标法，我经常用后者，两种代码实现的差别我都会提到，读者不必担心这点，只是希望读者注意此差距，因为不同的文章用的不同的方法，避免造成歧义。

以上的图即采用数数从0开始的方式

（三）树的性质

提几个基本性质，其它还有很多读者自行搜索相关资料

1. 树中的结点数等于所有结点的度数加1.
2. 度为m的树中第i层上至多有$m^i$个结点（i > = 0 ）
3. 高度为h的m叉树至多有$( m^{h+1} − 1 ) / ( m − 1 ) $个结点。从1开始数的话为：$( m^h − 1 ) / ( m − 1 ) $
4. 具有n个结点的m叉树的最小高度为$ log_m ( n ( m − 1 ) + 1 )-1 $，从1开始数的话最后不减去个1即可

🚢二、树的存储结构

（一）双亲表示法

每个结点中，包含data和parent两部分，data为数据域，保存自身的数据，而parent为指针域，存储该结点的双亲在数组中的下标

结构体定义：

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100

typedef int ElemType;	//树结点的数据类型，目前暂定为整型

/*结点结构*/
typedef struct PTNode{
	ElemType data;	//结点数据
	int parent;	//双亲位置
}PTNode;

/*树结构*/
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;

解释：

这样的存储结构，我们可以根据结点的parent 指针很容易找到它的双亲结点，所用的时间复杂度为0(1)，直到parent为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，则需要遍历整颗树

（二）孩子表示法

前面已经知道在树中每个结点有零个或多个子结点，我们将每个结点的孩子节点以单链表的形式排列起来，则n个结点就有n个孩子链表，如果是叶子结点则它的孩子链表为空。然后这n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

1. 方法一：

   结构体定义：

   /*树的孩子表示法结构定义*/
   #define MAX_TREE_SIZE 100
   
   /*树的结点定义*/
   typedef struct CTNode{
   	ElemType data;
   	struct CTNode *next;
   }CTNode;
   
   /*树结构*/
   typedef struct{
   	CTNode nodes[MAX_TREE_SIZE];	//结点数组
   	int r, n;	//根的位置和结点数
   }
   

   解释：

   上面已经提到，n个结点就有n个孩子链表，然后我们将这n个孩子链表的表头放进一个一维结构体数组中即可，并且孩子链表的顺序都是从左到右，存在数组中的表头即为该子树的根结点

2. 方法二：

   在《大话数据结构》是以另外一种方式定义的，我们将孩子链表的结点，表头分别定义，需要设计两种数据结构：

   （1）孩子链表的结点结构

   

   （2）头指针组成的数组的每个元素（表头）结构

   

   结构体定义：

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100

/*孩子结点*/
typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;

/*表头结点*/
typedef struct{
  ElemType data;
  ChildPtr firstchild;
}CTBox;

/*树结构*/
typedef struct{
  CTBox nodes[MAX_TREE_SIZE];	//结点数组
  int r, n;	//根的位置和结点数
}

解释：

每个结点我们都存在了数组里面，所以表头我们只需要表示出数据以及指向孩子链表的指针即可，进而孩子链表的结点因为它作为某个表头的孩子，同时又作为另一颗子树的表头存在数组里，所以我们只需要用个int类型表示是数组中哪个结点作为孩子即可，还有一个next指针指向它的兄弟结点

这两种方式本质都是一样的，这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。

但同时，又造成了我们很难访问到某个结点的双亲结点，需要整棵树遍历才行，失去了双亲表示法的优点，难道就不可以把双亲表示法和孩子表示法综合一下吗? 当然是可以，这个读者可自己尝试结合一下，在次不做赘述。

（三）孩子兄弟表示法

刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢？

任意一棵树， 它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结构体定义：

/*树的孩子兄弟表示法结构定义*/
typedef struct CSNode{
	TElemtype data;
	struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

于是通过这种结构，我们就把原来的树变成了这个样子：

这不就是个二叉树么？

我们在实际使用中最常用的也就是二叉树，这种存储结构的最大优点就是：它把一棵复杂的树变成了一棵二叉树，它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作 。接下来，我们就详细来介绍一下二叉树。

🚀二叉树

🚢一、二叉树的原理精讲

（一）二叉树的定义

我们以前介绍的线性表一样，一个没有限制的线性表应用范围可能有限，但是我们对线性表进行一些限制就可以衍生出非常有用的数据结构如栈、队列、优先队列等。

树也是一样，一个没有限制的树由于太灵活，控制起来比较复杂。如果对普通的树加上一些人为的限制，比如节点只允许有两个子节点，这就是我们接下来要介绍的二叉树

二叉树：与树相似，二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

• 或者为空二叉树，即n=0。
• 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
• 每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

二叉树是一个有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。故而二叉树有五种基本形态：

（二）二叉树的性质

1. 任意一棵树，若结点数量为n,则边的数量为n − 1。
2. 非空二叉树上的叶子结点数等于度为2的结点数加1，即$n_0=n_2+1$。
3. 在非空二叉树中，第 $i$ 层的结点总数不超过 $2^i,i>=0$；如果层数是从1开始，则定义改为：非空二叉树上第 $i$ 层上至多有$2^i-1$个结点，i>=1。
4. 高度为 h 的二叉树最多有 $2^{h+1}-1个$结点$(h>=0)$，最少有 $h+1$ 个结点；同样若高度从1开始：高度为h的二叉树至多有$2^h-1$ 个结点$(h\ge 1)$。
5. 对于任意一棵二叉树，如果其叶结点数为 $N_0$，而度数为 2 的结点总数为 $N_2$，则 $N_0=N_2+1$；
6. 具有$n(n>0)$个结点的完全二叉树的高度为$lo{g}_{2}n$。从1开始的话就加各一即可，高度为$lo{g}_{2}n+1$
7. 对完全二叉树按从上到下、从左到右的顺序依次编号1，2…，n,则有以下关系:
   • $i>1$时，结点$i$的双亲的编号为$i/2$，即当$i$为偶数时， 它是双亲的左孩子；当$i$为奇数时，它是双亲的右孩子。
   • 当$2 i ≤ n $时，结点$i$的左孩子编号为$2i$, 否则无左孩子。
   • 当$2 i + 1 ≤ n $时，结点$i$的右孩子编号为$2i+1$，否则无右孩子。
   • 结点$i$所在层次(深度)为$lo{g}_{2}n+1$。
8. 对完全二叉树按从上到下、从左到右的顺序依次编号0，1…，n:
   • $i$的左子结点：$2i+1$，$i$的右子结点：$2i+2$
   • i的父结点：$(i-1)/2$

🚢二、二叉树的存储结构

（一）顺序存储结构

前面我们已经谈到了树的存储结构，并且谈到顺序存储对树的这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现

二叉树的顺序存储：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i的分量中。还是一样从0开始数数，如果从1开始数结点数，就应该将编号为i的结点存在一维数组下标为i-1的位置上

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为h且只有h+1个结点的单支树却需要占据近$2(h+1)-1$个存储单元。

（二）链式存储结构

既然顺序存储结构适用性不强，我们就要考虑链式存储结构。在前面讲树的存储结构中孩子兄弟表示法就是采用二叉链表的方式将一棵复杂的树变成了一棵二叉树。树的孩子兄弟表示法和二叉树的二叉链表表示完全一样

二叉链表：二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

讲孩子兄弟表示法的时候，我们设置的两个指针firstchild指向该结点的第一个孩子结点的存储地址，rightsib指针，存储该结点的右兄弟结点的存储地址。我们只需要稍微转换一下思想：

每个结点包含两个指针域，指向两个孩子结点，LCHILD指向左子结点，RCHILD指向右子结点，同样还包含一个数据域，存储结点信息

结构体定义：

/*树的孩子兄弟表示法结构定义*/
typedef struct BITNode{
	Elemtype data;
	struct BITNode *lchild, *rchild;
} BITNode, *BITNode;

🚢二、常见二叉树的分类

（一）斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

（二）完全二叉树

若设二叉树的高度为 h，除第 h 层外，其它各层 (0～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。

堆也是常见的数据结构，常常单独拿出来研究使用：【数据结构篇C++实现】- 堆

（三）满二叉树

除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。

满二叉树就是特殊的完全二叉树

（四）平衡二叉树

又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

（五）二叉搜索树（二叉排序树）

又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：

• 若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
• 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
• 左、右子树也分别为二叉排序树。

🚢三、二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问所有结点，使得每个结点被当且访问一次。共分为四种方式：

（一）前序遍历（先序遍历）

先序遍历(PreOrder) 的操作过程如下：

1. 若二叉树为空，则什么也不做，否则
2. 访问根结点
3. 先序遍历左子树
4. 先序遍历右子树

上图前序遍历结果： 19 7 5 11 15 25 21 61

1.前序遍历-递归实现：

/************************
* 采用递归方式实现前序遍历
*************************/
void PreOrderRec(Btree *root) {
    if (root == NULL)
    {
    	return;
    }
    printf("- %d -", root->data);  //访问根节点
    preOrderRec(root->lchild);     //递归遍历左子树
    preOrderRec(root->rchild);     //递归遍历右子树
}

2.前序遍历-非递归方式实现：

1. 首先申请一个新的栈，记为 stack；
2. 将头结点 head 压入 stack 中；
3. 每次从 stack 中弹出栈顶节点，记为 cur，然后打印 cur 值，如果 cur 右孩子不为空，则将右孩子压入栈中；如果 cur 的左孩子不为空，将其压入 stack 中；
4. 重复步骤 3，直到 stack 为空.

/************************
* 借助栈实现前序遍历
*************************/
void PreOrder(Btree *root) 	{
    Bnode cur ;
    if (root == NULL)
    {
    	return;
    }
    
    SqStack stack;
    InitStack(stack);
    PushStack(stack, *root); //头节点先入栈
    
    while (!(IsEmpty(stack))) //栈为空，所有节点均已处理
    {
        PopStack(stack, cur); //要遍历的节点
        printf("- %d -", cur.data);
        
        if (cur.rchild != NULL) {
        PushStack(stack, *(cur.rchild)); //右子节点先入栈，后处理
        }
        if (cur.lchild != NULL) {
        PushStack(stack, *(cur.lchild)); //左子节点后入栈，接下来先处理
        }
    }
    DestroyStack(stack);
}

（二）中序遍历

中序遍历( InOrder)的操作过程如下：

1. 若二叉树为空，则什么也不做，否则
2. 中序遍历左子树
3. 访问根结点
4. 中序遍历右子树

中序遍历结果： 5 7 11 15 19 21 25 61

1.中序遍历-递归实现：

void InOrder(BiTree root){
    if (root == NULL)
    {
    	return;
    }
    preOrderRec(root->lchild);  //递归遍历左子树
    printf("- %d -", root->data);  //访问根结点
    preOrderRec(root->rchild);    //递归遍历右子树
}

2.中序遍历-非递归方式实现：

1. 沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，
2. 栈顶元素出栈并访问
3. 判断栈顶元素若其右孩子为空，继续执行步骤2;若其右孩子不空,将右子树转执行步骤1。

void InOrder2(BiTree T){
	InitStack(S);	//初始化栈S
	BiTree p = T;	//p是遍历指针
	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
		if(p){
			Push(S, p);	//当前节点入栈
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//栈顶元素出栈
			visit(p);	//访问出栈结点
			p = p->rchild;	//向右子树走，p赋值为当前结点的右孩子
		}
	}
}

（三）后序遍历

后序遍历(PostOrder) 的操作过程如下：

1. 若二叉树为空，则什么也不做，否则
2. 后序遍历左子树
3. 后序遍历右子树
4. 访问根结点

后序遍历结果： 5 15 11 7 21 61 25 19

1.后序遍历-递归实现：

void PostOrder(BiTree T){
	if (root == NULL)
    {
    	return;
    }
    preOrderRec(root->rchild);   //递归遍历左子树
    preOrderRec(root->lchild);   //递归遍历右子树
    printf("- %d -", root->data);
}

2.后序遍历-非递归方式实现：

1. 在后序遍历中，要保证左孩了和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，
2. 沿着根的左孩子，依次入栈，直到左孩子为空。
3. 读栈顶元素:若其右孩子不空且未被访问过，将右子树转执行1否则，栈顶元素出栈并访问。

void PostOrder2(BiTree T){
	InitStack(S);
	p = T;
	r = NULL;
	while(p || !IsEmpty(S)){
		if(p){	//走到最左边
			push(S, p);
			p = p->lchild;
		}else{	//向右
			GetTop(S, p);	//读栈顶元素（非出栈）
			//若右子树存在，且未被访问过
			if(p->rchild && p->rchild != r){
				p = p->rchild;	//转向右
				push(S, p);	//压入栈
				p = p->lchild;	//再走到最左
			}else{	//否则，弹出结点并访问
				pop(S, p);	//将结点弹出
				visit(p->data);	//访问该结点
				r = p;	//记录最近访问过的结点
				p = NULL;
			}
		}
	}
}

（四）层序遍历

从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问

上图层序遍历结果： 19 7 25 5 11 21 61 15

对应的递归算法：

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队;若它有右子树，则将右子树根结点入队。然后出队，访问出队结点…如此反复，直至队列为空。
二叉树的层次遍历算法如下:

void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化辅助队列
	BiTree p;
	EnQueue(Q, T);	//将根节点入队
	while(!IsEmpty(Q)){	//队列不空则循环
		DeQueue(Q, p);	//队头结点出队
		visit(p);	//访问出队结点
		if(p->lchild != NULL){
			EnQueue(Q, p->lchild);	//左子树不空，则左子树根节点入队
		}
		if(p->rchild != NULL){
			EnQueue(Q, p->rchild);	//右子树不空，则右子树根节点入队
		}
	}
}

🚢四、树、森林与二叉树的转化

我们前面已经讲过树的定义和存储结构，对于树来说，在满足树的条件下可以是任意形状，一个结点可以有任意多个孩子，显然对树的处理要复杂得多，我们前面也讲了二叉树，如果所有的树都像二叉树一样方便就好了。

在讲树的存储结构时，我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以相互进行转换。从物理结构来看，它们的二叉链表也是相同的，只是解释不太一样而已。 因此，只要我们设定一定的规则，用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以互相进行转换。

（一）树转换为二叉树

步骤如下：

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

如上图：一棵树经过三个步骤转换为一棵二叉树。初学者容易犯的错误就是在层次调整时，弄错了左右孩子的关系。比如图中F、G本都是树结点B的孩子，是结点E的兄弟，因此转换后，F就是二叉树结点E的右孩子，G是二叉树结点F的右孩子。

（二）森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为,森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。
步骤如下：

1. 将森林中的每棵树转换成相应的二叉树;
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

🚢五、树和森林的遍历

（一）树的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式:

1. 先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树。遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。

2. 后根遍历：先依次后根遍历每棵子树，然后再访问根结点。遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

下图的树的先根遍历序列为ABEFCDG,后根遍历序列为EFBCGDA。

另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

（二）森林的遍历

森林的遍历也分为两种方式:

1. 前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
2. 后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

下图森林的前序遍历序列为ABCDEFGHI，后序遍历序列为BCDAFEHIG。

当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，可知森林的先序和后序遍历即为其对应二叉树的先序和中序遍历。

🚀线索二叉树

🚢一、线索二叉树原理精讲

回顾我们之前讲的二叉链表：

• 首先，传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。

• 其次，观察图可以发现，指针域并不是充分的利用了，有许多的空指针的存在，比如18的Rchild。对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1 条分支线数，也就是说，其实是存在2n- (n-1) =n+1个空指针域。

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Mk0Xq6Ay-1690729766453)(E:\create\图片\树\21.png)]

由此设想能否利用这些空指针来存放指向其前驱或后继的指针?这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

线索链表：我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

其结点结构如下所示：

其中

• ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
• rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

于是我们可以将上面提到的二叉链表修改成如下的线索链表：

🚢二、线索二叉树的结构实现

二叉树的线索存储结构代码如下：

typedef struct ThreadNode{
	ElemType data;	//数据元素
	struct ThreadNode *lchild, *rchild;	//左、右孩子指针
	int ltag, rtag;	//左、右线索标志
}ThreadNode, *ThreadTree;

🚢三、二叉树的线索化

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树的时候才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。我们先以中序线索二叉树的建立为例，还是继续拿上面的二叉链表讲解

（一）中序线索二叉树

1.建立中序线索二叉树

1. 在中序遍历的过程中，P指向当前结点，用一个pre指针记录上一个访问过的结点
2. 检查当前结点P的左孩子指针Lchild是否为空，若为空，将P的Ltag设为1，并将Lchild指向上一个结点pre
3. 同时检查父结点pre的右指针Rchild是否为空，若为空，将pre的Rtag设为1，并将Rchild指向当前结点P

中序遍历对二叉树线索化的递归算法:

struct Tree *pre = NULL;    //全局变量 
 
void InThread(struct  Tree  *p) {
    InThread(p->lchild);    //递归左子树线索化
 
    if(!p->lchild)            //没有左孩子
    {
        p->Ltag = 1;
        p->lchild = pre;    //本来指向左孩子的指针指向前驱结点 
    }
 
    if(pre != NULL && !pre->rchild)        //没有右孩子
    {
        pre->Rtag = 1;
        pre->rchild = p;    //本来指向右孩子的指针指向后继结点 
    }
 
    pre = p;    //保持pre指向p的前驱
 
    InThread(p->rchild);    //递归右子树线索化
}

解释：

1. 你会发现，除了中间的代码，和二叉树中序遍历的递归代码几乎完全一样。只不过将本是访问结点的功能改成了线索化的功能。

2. if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过（如果是第一个元素则前驱指向NULL），赋值给了 pre，所以可以将pre赋值给p->lchild,并修改p->L为1，以完成前驱结点的线索化。

   后继结点的线索化就会麻烦一点。因为此时p结点的后继结点还没有被访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就为pre的后继结点，于是就让pre->rchild = p，并设置pre->R为1，以完成后继结点的线索化。

3. 具体过程：

   • 从4开始，P指向4，prve = NULL，4的Lchild为空，4的Ltag设为1，同时指向前驱pre为NULL，因为此时4结点的后继结点还没有被访问到，所以只能等下再处理4的Rchild
   • 然后pre指向4，p指向5，4的Rchild为空，5就为4的后继结点，此时再处理4的Rchild指向5
   • pre指向5，p指向8，8的Lchild为空，8的Ltag设为1，同时指向前驱pre为5，8的Rchild为空，一样等到12的时候再处理
   • pre指向8，p指向12，因为之前8的Rchild为空，8的Rchild指向12
   • pre指向12，p指向13，操作同上…

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ShyD63Oe-1680510619306)(E:\create\图片\树\29.png)]

通过中序遍历建立中序线索二叉树的主过程算法如下：

void CreateInThread(ThreadTree T){
	ThreadTree pre = NULL;
	if(T != NULL){
		InThread(T, pre);	//线索化二叉树
		pre->rchild = NULL;	//处理遍历的最后一个结点
		pre->rtag = 1;
	}
}

但如上操作建立中序线索二叉树，第一个结点的Lchild和最后一个结点的Rchild仍然指向NULL，为了方便,可以在二叉树的线索链表上也添加一个头结点，令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点;令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如下图所示。

2.遍历中序线索二叉树

/*T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍
的最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
void InOrderTraverse_Thr(BiThrTree T){
	BiThrTree p;
	p = T->lchild;	//p指向根结点
	//空树或遍历结束时，p==T（最后一个结点指向根结点）
	while(p != T){	
		//当ltag==1时循环到中序序列第一个结点
		while(p->ltag == 0){	
			p = p->lchild;	//p指向p的左子树
		}
		visit(p);	//访问该结点
		//后继线索为1且不是指向头结点
		while(p->rtag == 1 && p->rchild != T){	
			p = p->rchild;	//p指向p的后继
			visit(p);	//访问该节点
		}
		//p进至其右子树根，开始对右子树根进行遍历
		p = p->rchild;	
	}
}

从这段代码也可以看出，它等于是一个链表的扫描,所以时间复杂度为0(n)。由于它充分利用了空指针域的空间(这等于节省了空间)，又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

（二）先序和后序线索二叉树

上面给出了建立中序线索二叉树的代码，建立先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

以图(a)的二叉树为例，其先序序列为ABCDF，后序序列为CDBFA，可得出其先序和后序线索二叉树分别如图(b)和( c)所示：

如何在先序线索二叉树中找结点的后继：

如果有左孩子，则左孩子就是其后继；如果无左孩子但有右孩子，则右孩子就是其后继；如果为叶结点，则右链域直接指示了结点的后继。

在后序线索二叉树中找结点的后继较为复杂，可分3种情况：

1. 若结点x是二叉树的根，则其后继为空;
2. 若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲;
3. 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。图( c)中找结点B的后继无法通过链域找到，可见在后序线索二叉树上找后继时需知道结点双亲，即需采用带标志域的三叉链表作为存储结构。

🚀常用于查找数据的树

树这种数据结构，经常使用于查找数据的场合，而最常用的就是二叉排序树与平衡二叉树，以及多路查找树

🚢二叉搜索树与平衡二叉树详解

一、二叉搜索树

（一）二叉搜索树的原理精讲

1. 当我们要在一组数中要找到你女朋友（或未来女朋友）的年龄，比如 26？你该怎么找

答案： 从左至右 或 从右至左遍历一次，找到这个数字

2. 当我们把数据进行排序（按照从小到大的顺序排列）后，再查找相应的这条记录？还是用上面的方法吗？

答案：最快的方式，是采用折半法（俗称二分查找）
 
思考：当我们有新的数据加进来，或者删除其中的一条记录，为了保障查找的效率，我们仍然要保障数组有序，但是，会碰到我们讲顺序表时的问题，涉及到大量数据的移动！在插入和删除操作上，就需要耗费大量的时间（需进行元素 的移位），能否有一种既可以使得插入和删除效率不错，又可高效查找的数据结构和算法呢？
 
抛砖: 首先解决一个问题，插入时不移动元素，我们可以想到链表，但是要保证其有序的话，首先得遍历链表寻找合适的位置，那么又如何高效的查找合适的位置呢，能否可以像二分一样，通过一次比较排除一部分元素？
 
引玉： 那么我们可以用二叉树的形式，以数据集第一个元素为根节点，之后将比根节点小的元素放在左子树中，将比根节 点大的元素放在右子树中，在左右子树中同样采取此规则。那么在查找 x 时，若 x 比根节点小可以排除右子树所有元素， 去左子树中查找（类似二分查找），这样查找的效率非常好，而且插入的时间复杂度为 O（h），h 为树的高度，较 O（n） 来说效率提高不少。故二叉搜索树用作一些查找和插入使用频率比较高的场景

二叉搜索树（也称二叉查找树、二叉排序树）或者是一棵空树，或者是具有下列特性的二叉树:

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空，则右子树上所有结点的值均大于根结点的值。
• 左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值根据二叉排序树的定义，左子树结点值$<$根结点值$<$右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，下图所示二叉排序树的中序遍历序列为 5 7 11 15 19 21 25 26 61 99。

（二）二叉搜索树的算法实现

1.二叉搜索树的结构体定义

#define MAX_NODE 1024

#define isLess(a, b) (a<b)
#define isEqual(a, b) (a==b)

typedef int ElemType;
/*二叉树的二叉链表结点结构定义*/
typedef struct _Bnode{
    ElemType data; //元素类型
    struct _Bnode *lchild, *rchild;//指向左右孩子节点
}Bnode, *Btre

2.二叉搜索树插入结点

将要插入的结点 e，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上 操作直到找到一个空位置用于放置该新节点。

bool InsertBtree(Btree **root, Bnode *node){
    Bnode *tmp = NULL;
    Bnode *parent = NULL;
    
    if(!node){
    	return false;
    } else {//清空新节点的左右子树
        node->lchild = NULL;
        node->rchild = NULL;
    }
    
    if(*root){//存在根节点
    	tmp= *root;
    }else{ //不存在根节点
        *root = node;
        return true;
    }
    
    while(tmp != NULL){
        parent = tmp;//保存父节点
        printf("父节点： %d\n", parent->data);
        if(isLess(node->data,tmp->data)){
        	tmp = tmp->lchild;
        }else{
        	tmp = tmp->rchild;
        }
    }
    
    //若该树为空树,则直接将 node 放置在根节点上
    if(isLess(node->data, parent->data)){//找到空位置后，进行插入
    	parent->lchild = node;
    }else{
    	parent->rchild = node;
    }
    
    return true;
}

3.二叉搜索树删除结点

将要删除的节点的值，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上操作直到找到一个节点的值等于删除的值，则将此节点删除。删除时有 4 中情况须分别处理：

（1）删除节点不存在左右子节点，即为叶子节点，直接删除

（2）删除节点存在左子节点，不存在右子节点，直接把左子节点替代删除节点

（3）删除节点存在右子节点，不存在左子节点，直接把右子节点替代删除节点

（4）删除节点存在左右子节点，则取左子树上的最大节点或右子树上的最小节点替换删除节点

相关代码如下：

/************************
* 查找二叉搜索树上最大的结点
*************************/
int findMax(Btree* root)
{
    assert(root!=NULL);
    //方式一 采用递归
    /*if(root->rchild==NULL){
      	return root->data;
      }
    return findMax(root->rchild);
    */
    
    //方式二 采用循环
    while(root->rchild){
    	root = root->rchild;
    }
    	return root->data;
    }

//删除结点
Btree* DeleteNode(Btree* root, int key) {
    if(root==NULL)return NULL;//没有找到删除节点
    
    if(root->data > key)
    {
        root->lchild = DeleteNode(root->lchild, key);
        return root;
    }
    if(root->data < key)
    {
        root->rchild = DeleteNode(root->rchild, key);
        return root;
    }
    
    //删除节点不存在左右子节点，即为叶子节点，直接删除
    if(root->lchild==NULL && root->rchild==NULL)return NULL;
    
    //删除节点只存在右子节点，直接用右子节点取代删除节点
    if(root->lchild==NULL && root->rchild!=NULL)return root->rchild;
    
    //删除节点只存在左子节点，直接用左子节点取代删除节点
    if(root->lchild!=NULL && root->rchild==NULL)return root->lchild;
    
    删除节点存在左右子节点，直接用左子节点最大值取代删除节点
    int val = findMax(root->lchild);
    root->data=val;
    root->lchild = DeleteNode(root->lchild,val);
    return root;
}

4.二叉搜索树查找结点

/************************
* 采用递归方式查找结点
*************************/
Bnode* queryByRec(Btree *root, ElemType e){
    if (root == NULL || isEqual(root->data, e)){
    	return root;
    } else if(isLess(e, root->data)) {
    	return queryByRec(root->lchild, e);
    } else {
    	return queryByRec(root->rchild, e);
    }
}

/**
* 使用非递归方式查找结点
*/
Bnode* queryByLoop(Bnode *root, int e){
    while(root != NULL && !isEqual(root->data, e)){
        if(isLess(e, root->data)){
        	root = root->lchild;
        }else{
        	root = root->rchild;
        }
    }
    return root;
}

二、平衡二叉树（AVL树）

（一）平衡二叉树原理精讲

平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)：是一种特殊的二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

它是一种高度平衡的二叉排序树。它要么是一棵空树， 要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) ， 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

（二）平衡二叉树的相关算法实现

1.平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以n $n_h$表示深度为$h $的平衡树中含有的最少结点数。显然，有$n 0 = 0 , n 1 = 1 , n 2 = 2 $并且有$n_h = n_{h − 1} + n_{h − 2}+ 1$ 可以证明，含有$n$个结点的平衡二叉树的最大深度为$O(log2n)$，因此平衡二叉树的平均查找长度为$O(log2n)$如下图所示。

2.平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
注意:每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列4种情况：

1. LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
   如下图所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

   

2. RR平衡旋转(左单旋转)。由于在结点A的右孩子®的右子树®上插入了 新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

   

3. LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树®上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置（即进行一次RR平衡旋转(左单旋转)），然后再把该C结点向右上旋转提升到A结点的位置（即进行一次LL平衡旋转(右单旋转)）。

   

4. RL平衡旋转(先右后左双旋转)。由于在A的右孩子®的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置（即进行一次LL平衡旋转(右单旋转)），然后再把该C结点向左上旋转提升到A结点的位置（即进行一次RR平衡旋转(左单旋转)）。

   

   注意: LR和RL旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程，而上图中是以插入C的左子树中为例。

举个例子：
假设关键字序列为15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8}15,3,7,10,9,8，通过该序列生成平衡二叉树的过程如下图所示。

🚢多路查找树

一、B树

多路查找树(muitl-way search tree)， 其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。常见的有4种特殊形式：2-3树、2-3-4树、B树和B+树。这里主要介绍B树和B+树，因为2-3树、2-3-4树都是B树的特例。
如下图所示是一颗2-3树：

1、定义

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

1. 树中每个结点至多有m 棵子树，即至多含有m − 1个关键字。

2. 若根结点不是终端结点，则至少有两棵子树。

3. 除根结点外的所有非叶结点至少有⌈ m / 2 ⌉ 棵子树，即至少含有⌈ m / 2 ⌉ − 1个关键字。

4. 所有非叶结点的结构如下：

   

   其中，K i ( i = 1 , 2 , . . . , n )为结点的关键字，且满足K 1 < K 2 < . . . < K n ；P i ( i = 0 , 1 , . . . , n ) 为指向子树根结点的指针，且指针$P_{i-1}$所指子树中所有结点的关键字均小于Ki ， Pi 所指子树中所有结点的关键字均大于Ki （即符合二叉排序树的左小右大），n ( ⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 ) 为结点中关键字的个数。

5. 所有的叶结点都出现在同一层次上，并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

B树是所有结点的平衡因子均等于0的多路平衡查找树。
下图所示的B树中所有结点的最大孩子数m = 5，因此它是一棵5阶B树，在m mm阶B树中结点最多可以有m个孩子。可以借助该实例来分析上述性质：

1. 结点的孩子个数等于该结点中关键字个数加1（每一个空隙都存在一个分支）。
2. 如果根结点没有关键字就没有子树，此时B树为空；如果根结点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。
3. 除根结点外的所有非终端结点至少有⌈ m / 2 ⌉ = ⌈ 5 / 2 ⌉ = 3棵子树(即至少有⌈ m / 2 ⌉ − 1 = ⌈ 5 / 2 ⌉ − 1 = 2 个关键字)，至多有5棵子树(即至多有4个关键字)。
4. 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了3个区间：( − ∞ , 5 ) , ( 5 , 11 ) , ( 11 , + ∞ ) ，该结点3个指针所指子树的关键字均落在这3个区间内。
5. 所有叶结点均在第4层，代表查找失败的位置。

2、B树与磁盘存取

B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

我们的外存，比如硬盘， 是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是211到214个字节。
在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对B树进行调整，使得B树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001 (即1个结点包含1000个关键字)，高度为2，它可以储存超过10亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于B树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。

3、B树的查找

在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。
B树的查找包含两个基本操作：①在B树中找结点；②在结点内找关键字。由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。
在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。

例如，在上图中查找关键字42 ，首先从根结点开始，根结点只有一个关键字，且42 > 22 ，若存在，必在关键字22 的右边子树上，右孩子结点有两个关键字，而36 < 42 < 45，则若存在，必在36和45中间的子树上，在该子结点中查到关键字42，查找成功。若查找到叶结点时（对应指针为空指针)，则说明树中没有对应的关键字，查找失败。

4、B树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉査找树中，仅需査找到需插入的终端结点的位置。但是，在B树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足B树定义中的要求。将关键字key插入B树的过程如下：

1. 定位。利用前述的B树査找算法，找出插入该关键字的最低层中的某个非叶结点(在B树中查找key时,会找到表示查找失败的叶结点,这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最低层中的某个非叶结点)。
2. 插入。在B树中，每个非失败结点的关键字个数都在区间[ ⌈ m / 2 ⌉ − 1 , m − 1 ]内。插入后的结点关键字个数小于m，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m − 1时，必须对结点进行分裂。

分裂的方法是：取一个新结点，在插入key后的原结点，从中间位置⌈ m / 2 ⌉将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置⌈ m / 2 ⌉的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止,进而导致B树高度增1。
对于m = 3的B树，所有结点中最多有m − 1 = 2 个关键字，若某结点中已有两个关键字，则结点已满，如下图a所示。插入一个关键字60 后，结点内的关键字个数超过了m − 1，如图b所示，此时必须进行结点分裂，分裂的结果如图c所示。

通俗点讲，B树的插入，结点不溢出时好说，直接插入；如果结点溢出那就分裂，并把中间结点合并到父节点。

5、B树的删除

B树中的删除操作与插入操作类似，但要更复杂一些，即要使得删除后的结点中的关键字个数≥ ⌈ m / 2 ⌉ − 1，因此将涉及结点的“合并”问题。

1. 当被删关键字k不在终端结点(最低层非叶结点)中时，可以用k kk的前驱(或后继) k ′来替替代k ，然后在相应的结点中删除k ′ ，关键字k ′必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。在下图的B树中，删除关键字80，用其前驱78替代，然后在终端结点中删除78。因此只需讨论删除终端结点中关键字的情形。

   

2. 当被删关键字在终端结点(最低层非叶结点)中时，有下列三种情况:
   ① 直接删除关键字。若被删除关键字所在结点的关键字个数≥ ⌈ m / 2 ⌉，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。
   ② 兄弟够借。若被删除关键字所在结点删除前的关键字个数= ⌈ m / 2 ⌉ − 1 ，且与此结点相邻的右(或左)兄弟结点的关键字个数≥ ⌈ m / 2 ⌉，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)，以达到新的平衡。在图(a)中删除B树的关键字65，右兄弟关键字个数≥ ⌈ m / 2 ⌉ = 2 ，将71取代原65的位置，将74调整到71的位置。

   

   ③ 兄弟不够借。若被删除关键字所在结点删除前的关键字个数= ⌈ m / 2 ⌉ − 1 ，且此时与该结点相邻的左、右兄弟结点的关键字个数均= ⌈ m / 2 ⌉ − 1 ，则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。在图(b)中删除B树的关键字5 55，它及其右兄弟结点的关键字个数= ⌈ m / 2 ⌉ − 1 = 1，故在5 删除后将60合并到65 结点中。
   在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0(根结点关键字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到⌈ m / 2 ⌉ − 2 ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。

其实通俗点讲，B树的删除，删除结点无非就是多留少补的情况，多留不必多说；少补复杂点：当兄弟够借时，就向左旋转一次（即往左挪一个位置，重构根节点关键字的前驱和后继）；当兄弟不够借时就拆根节点，合并到兄弟结点，合并拆分要始终保证B树平衡，理清了就很容易理解。

二、B+树

尽管B树的诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行。可是在B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问。

如上图所示。我们希望遍历这棵B树，假设每个结点都属于硬盘的不同页面，我们中序遍历所有的元素：
$$页面2\to 页面1\to 页面3\to 页面1\to 页面4\to 页面1\to 页面5$$
而且我们每次经过结点遍历时，都会对结点中的元素进行一次遍历，这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢?
B+树来了。

1、定义

B+树是应文件系统（比如数据库）所需而出现的一种B树的变形树。

m阶的B+树与m阶的B树的主要差异如下：

1. 有n棵子树的结点中包含有n个关键字;
2. 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接;
3. 所有分支结点可以看成是索引，结点中仅含有其子树中的最大(或最小)关键字。
4. 在B+树中，每个结点(非根内部结点)的关键字个数n的范围是⌈ m / 2 ⌉ ≤ n ≤ m(根结点：1 ≤ n ≤ m)；在B树中，每个结点(非根内部结点)的关键字个数n范围是⌈ m / 2 ⌉ − 1 ≤ n ≤ m − 1 (根结点: 1 ≤ n ≤ m − 1)。

下图所示为一棵4阶B+树。

B+树的结构特别适合带有范围的查找。比如查找我们学校18~22岁的学生人数，我们可以通过从根结点出发找到第一个18岁的学生，然后再在叶子结点按顺序查找到符合范围的所有记录。
B+树的插入、删除过程也都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已。

🚀哈夫曼树

哈夫曼编码

哈夫曼（Huffman）编码算法是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算法。算法根据文本字符出现的频率，重新对字符进行编码。

首先请大家阅读下面两段中外小学作文：

中国 - 今天天气晴朗，我和小明出去玩！小明贪玩，不小心摔了一跤，小明被摔得哇哇哭了，小明的爸爸闻声赶来，又把小明痛扁了一阵。小明的小屁屁都被揍扁了，因为小明把妈妈刚买给他的裤子弄破了！

外国 - 今天天气晴朗，我和乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿出去玩！乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿贪玩，不小心摔了一跤，乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿被摔得哇哇哭了，乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿的爸爸闻声赶来，又把乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿痛扁了一阵。乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿的小屁屁都被揍扁了，因为乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿把妈妈刚买给他的裤子弄破了！

同一段内容，当小明换成了外国小朋友的名字，篇幅就增加了几倍，有没有办法把内容缩减呢？当然有！在文章的开头，先声明一个缩写：

那么，上面这段文字就可以缩成很小的一段：

今天天气晴朗，我和乔顿出去玩！乔顿贪玩，不小心摔了一跤，乔顿被摔得哇哇哭了，乔顿的爸爸闻声赶来，又把小明痛扁了一阵。乔顿的小屁屁都被揍扁了，因为乔顿把妈妈刚买给他的裤子弄破了！

哈夫曼编码就是这样一个原理！按照文本字符出现的频率，出现次数越多的字符用越简短的编码替代，因为为了缩短编码的长度，我们自然希望频率越高的词，编码越短，这样最终才能最大化压缩存储文本数据的空间。

哈夫曼编码举例： 假设要对“we will we will r u”进行压缩。

压缩前,使用 ASCII 码保存:

共需： 19 个字节 - 152 个位保存

下面我们先来统计这句话中每个字符出现的频率。如下表，按频率高低已排序：

接下来，我们按照字符出现的频率，制定如下的编码表：

这样，“we will we will r u”就可以按如下的位来保存：

01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100

🚀红黑树

是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：

• 节点是红色或黑色；
• 根节点是黑色；
• 所有叶子节点都是黑色；
• 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

🚀堆

🚢一、堆的原理精讲

⛳（一）堆的概念

堆（Heap）：一种有特殊用途的数据结构——用来在一组变化频繁（发生增删查改的频率较高）的数据集中查找最值

• 堆中某个节点的值总是不大于或不小于其父节点的值;
• 堆总是一棵完全二叉树。
• 每个节点最多可以有两个节点
• 根结点的键值是所有堆结点键值中最大（小）者，且每个结点的值都比其孩子的值大（小），这样的堆叫最大（小）堆
• 除了根节点没有兄弟节点，最后一个左子节点可以没有兄弟节点，其他节点必须有兄弟节点
• 这里需要注意的是：在多个子树中，并不是说其中一个子树的父结点一定大于另一个子树的儿子结点。

实际上，先弄懂树这种数据结构再来看堆就会简单很多了，堆是你见过的最有个性的树！它是用数组表示的树。所以逻辑结构上其实是一棵树，物理结构上是一维数组，属于非线性结构

本篇博客默认你没有事先学过树，通俗易懂，讲解知识详细，即使不知道完全二叉树，也能辨认出堆，即使没学过树也能搞懂堆，本篇以最大堆进行讲解

⛳（二）看图识最大堆

图1：因为93 > 87，而且82无左子节点却有右子节点，不满足除了根节点和最后一个左子节点可以没有兄弟节点，其他节点必须要有兄弟节点的规定，所以图1不是堆

图2：82是最后一个左子节点，但92不是，而且没有兄弟节点，所以图2也不是堆

图3：满足条件，为最大堆

⛳（三）详解堆是用数组表示的树

i为下标，由上图我们能看出规律：

• i的左子节点：2i+1
• i的右子节点：2i+2
• i的父节点：(i-1)/2

这也就是我们在代码实现的时候需要注意的地方

🚀二、堆的向下调整算法

向下调整：是让调整的结点与其孩子节点进行比较，若想将其调整为小堆，那么根结点的左右子树必须都为小堆，
若想将其调整为大堆，那么根结点的左右子树必须都为大堆，有些文章说单纯满足为堆就行这种说法是不对的

向下调整算法的基本思想（大部分搜到的都是以最小堆为例，我就继续以最大堆为例了）：

1. 从根结点处开始，选出左右孩子中值较大的孩子。
2. 让大的孩子与其父亲进行比较。
3. 若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
4. 若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

代码实现：

/*向下调整将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap &heap, int index) { 
    int cur=heap.arr[index];//当前待调整的节点
	int parent,child;
/*判断否存在大于当前节点子节点，如果不存在 ，则堆本身是平衡的，不需要调整；如果存在，则将最大的子节点与之交换，交换后，如果这个子节点还有子节点，则要继续按照同样的步骤对这个子节点进行调整*/
	for(parent=index; (parent*2+1)<heap.size; parent=child) {
        child=parent*2+1;
        
        //取两个子节点中的最大的节点
        
        if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])) {
        	child++;
		}
        
            //判断最大的节点是否大于当前的父节点
         if(cur>=heap.arr[child]) {//不大于，则不需要调整，跳出循环
             break;
         }else {//大于当前的父节点，进行交换，然后从子节点位置继续向下调整
             heap.arr[parent]=heap.arr[child];
             heap.arr[child]=cur;
         }
    }
}

🚀三、堆的向上调整算法

向上调整：是让调整的结点与其父亲结点进行比较，当我们已经有一个堆，我们需要在堆的末尾插入数据，再对其进行调整，使其任然保持堆的结构，这里我们就需要用到堆的向上调整算法

向上调整算法的基本思想：

1. 将目标结点与其父结点比较
2. 若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置
3. 将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是大堆了。

代码实现：

/*将当前的节点和父节点调整成最大堆*/
void adjustUp(Heap &heap, int index) {
    if(index<0 || index >= heap.size) {//大于堆的最大值直接 return
    	return;
    }

    while(index>0){	
        int temp = heap.arr[index];
        int parent = (index - 1) / 2;
        
        if(parent >= 0){//如果索引没有出界就执行想要的操作
        	if(temp > heap.arr[parent]){
                heap.arr[index] = heap.arr[parent];
                heap.arr[parent] = temp;
                index = parent;
        	} else {//如果已经比父亲小 直接结束循环
        		break;
        	}
        } else {//越界结束循环
        	break;
        }
    }
}

🚀四、将任意一棵树建成堆

前面我们已经知道，堆的向下调整算法是在基于根节点左右子树已经为最大堆或最小堆的前提下才能操作的；而堆的向上调整算法是在我们已经建好了一个最大堆或最小堆，用于插入元素后的调整

那么如何将任意一棵树建成最大（小）堆呢，这里我就改为：如何在数组中快速创建堆：

我们把向下调整算法倒着来，我们知道，满足堆，必须左右子树都是大堆或者小堆，我们可以利用这个思想，从下往上倒着走，从第一个非叶子节点开始，通过数组下标的控制，把它当做根去向下调整，依次往上，直到把当前路径调整成符合条件的大堆或者小堆即可

还是以最大堆为例讲解，可以看到，根节点右子树不是一个最大堆，所以不能直接用向下调整算法

1. 首先我们需要找到最后一个结点的父结点如图（a），我们找到的结点是 87，然后找出该结点的最大子节点与自己比较，若该子节点比自身大，则将两个结点交换.。图(a)中，87 比左子节点 95 小,则交换之.如图（b）所示

2. 我们移动到前一个父结点 93,如图©所示。同理做第一步的比较操作,结果不需要交换

3. 继续移动结点到前一个父结点 82，82 小于右子节点 95，则 82 与 95 交换，如图(d)所示，82 交换后，其值小于左子节点，不符合最大堆的特点，故需要继续向下调整，如图(e)所示

4. 所有节点交换完毕,最大堆构建完成

🚀五、堆的算法实现

1.堆的结构体定义

#define DEFAULT_CAPCITY 128

typedef struct _Heap{
    int *arr; //存储堆元素的数组
    int size; //当前已存储的元素个数
    int capacity; //当前存储的容量
}Heap;

2.初始化堆

/*初始化堆*/
bool initHeap(Heap &heap, int *orginal, int size){
    //orginal：原数据  size：数据个数  heap：堆
    int capacity = DEFAULT_CAPCITY>size? DEFAULT_CAPCITY:size;
    
    heap.arr = new int[capacity];   //分配堆中数组空间
    if(!heap.arr) return false;
    
    heap.capacity = capacity;
    heap.size = 0;
    
    //如果存在原始数据则构建堆
    if(size>0){
        memcpy(heap.arr, orginal, size*sizeof(int));
        heap.size = size;
        buildHeap(heap);
    } else {
    	heap.size = 0;
    }
return true;
}


/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 */
void buildHeap(Heap &heap){
    int i;
    for(i=heap.size/2-1; i>=0; i--){
    	adjustDown(heap, i);
    }
}

解释：

1. 初始化堆操作即为之前讲的将任意一棵树建成堆
2. orginal为函数外传入的原数据，然后通过初始化将其建成堆
3. buildHeap即为以最后一个非叶子节点开始的向下调整算法

3.判断堆是否为空

/*判断堆是否为空*/
bool isEmpty(Heap &heap){
	if(heap.size<1) return true;
		return false;
}

4.插入新元素

/*最大堆尾部插入节点，同时保证最大堆的特性*/
bool insert(Heap &heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "栈空间耗尽！\n");
		return false;
	}
	
    int index = heap.size;
    heap.arr[heap.size++] = value;
    adjustUp(heap, index);
    return true;
}

5.堆顶元素出列（删除元素），同时获取堆顶数据

如果我们将堆顶的元素删除，那么顶部有一个空的节点，怎么处理？

我们先将堆顶的数据与最后一个数据交换位置，删除最后一个结点，然后再修复堆属性。

原因：我们若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为O（N）。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是大堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为O ( log ⁡ ( N ) ）

代码实现：

/* 删除堆顶元素，获取堆顶的数据*/
bool pop(PriorityQueue &pq, DataType &value) {
    
    if (isEmpty(pq)) return false;
    
    value = pq.arr[0];
    pq.arr[0] = pq.arr[--pq.size];
    //heap.arr[0] = heap.arr[heap.size-1];
    //heap.size--;
    adjustDown(pq, 0);// 向下执行堆调整
    return true;
}

6.遍历打印堆

打印堆中的数据，这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印，即打印成树形结构。

//求结点数为n的二叉树的深度
int depth(int n) {
	assert(n >= 0);

	if (n>0) {
		int m = 2;
		int hight = 1;
		while (m < n + 1) {
			m *= 2;
			hight++;
		}
		return hight;
	} else {
		return 0;
	}
}

//打印堆
void HeapPrint(Heap* php) {
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
	//按照树形结构进行打印
	int h = depth(php->size);
	int N = (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数
	int space = N - 1;//记录每一行前面的空格数
	int row = 1;//当前打印的行数
	int pos = 0;//待打印数据的下标
	while (1) {
		//打印前面的空格
		int i = 0;
		for (i = 0; i < space; i++) {
			printf(" ");
		}
		//打印数据和间距
		int count = (int)pow(2, row - 1);//每一行的数字个数
		while (count--)//打印一行
		{
			printf("%02d", php->a[pos++]);//打印数据
			if (pos >= php->size)//数据打印完毕
			{
				printf("\n");
				return;
			}
			int distance = (space + 1) * 2;//两个数之间的空格数
			while (distance--)//打印两个数之间的空格
			{
				printf(" ");
			}
		}
		printf("\n");
		row++;
		space = space / 2 - 1;
	}
}

7.销毁堆

/*销毁堆*/
void destroy(Heap &heap){
    if(heap.arr) delete[] heap.arr;
   
    heap->arr = NULL;//及时置空
    heap->size = 0;//元素个数置0
    heap->capacity = 0;//容量置0  
}

🚀六、拓展

⛳（一）用最大堆或最小堆来实现优先队列

操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列（即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种，如升序优先队列

⛳（二）堆排序算法

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素.

(选择排序工作原理 - 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零)

/* 实现堆排序 */
void heapSort(Heap &heap){
    if (heap.size<1) return ;
    
    while(heap.size>0){
        int tmp = heap.arr[0];
        heap.arr[0] = heap.arr[heap.size-1];
        heap.arr[heap.size-1] = tmp;
        
        heap.size--;
        adjustDown(heap, 0);// 向下执行堆调整
    }
}

⛳（三）top - k问题

若要从N个数字中取得最小的K个数字，则需要创建大小为K的大堆来获取。若要从N个数字中取得最大的K个数字，则需要创建大小为K的小堆来获取。

拜托，面试别再问我TopK了！！！_架构师之路-CSDN博客

总结参考资料:

程杰:大话数据结构

严蔚敏:数据结构C语言版

数据结构：线性表(List)【详解】
（排版结构等都借鉴了此位前辈的博客，对我的学习总结起到了很大的帮助）文章来源地址https://www.toymoban.com/news/detail-401955.html

到了这里，关于【数据结构篇】-树（共计两万字，你真的搞懂了它吗）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！