树

二叉树

二叉树的遍历

先左后右，根对序

1. 前序遍历 根左右
2. 中序遍历 左根右
3. 后序遍历 左右根
4. 层序遍历 按层的顺序遍历

二叉搜索树

二叉搜索树（Binary Search Tree，BST），也称为二叉排序树或二叉查找树，是一种特殊的二叉树。它具有以下性质：

• 每个节点都有一个键值，且每个节点的键值都是唯一的。
• 任意节点的左子树中的所有节点的键值都小于该节点的键值。
• 任意节点的右子树中的所有节点的键值都大于该节点的键值。
• 左子树和右子树也都是二叉搜索树。

二叉搜索树允许快速查找、插入和删除节点的操作。例如，查找操作从根节点开始，如果树为空，则查找失败。如果不为空，则比较节点键值与目标值，如果目标值小于节点键值，则在左子树中继续查找；如果目标值大于节点键值，则在右子树中继续查找；如果相等，则查找成功。

二叉搜索树的效率很大程度上取决于树的高度。平衡的二叉搜索树（如AVL树）可以确保操作的效率。二叉搜索树在计算机科学中广泛应用，特别是在那些需要频繁查找和更新的场景中。它是许多动态集合数据结构和抽象数据类型的基础，如集合、映射、多重集合等。

*线索二叉树

线索二叉树是一种通过增加额外的线索信息来优化遍历操作的数据结构。在传统的二叉树中，每个节点有两个指针，分别指向其左孩子和右孩子。如果某个节点的孩子为空，这个指针就会为空，不存储任何信息。线索二叉树利用这些空指针来存放指向节点在某种遍历顺序下的前驱或后继的指针，从而加快查找节点前驱和后继的速度¹²³。

例如，在中序线索二叉树中，如果一个节点的左指针为空，它将指向该节点的中序遍历的前驱；如果一个节点的右指针为空，它将指向该节点的中序遍历的后继。这样，即使在没有父指针或栈的帮助下，也可以快速遍历整个二叉树¹。

线索化的过程就是在遍历二叉树时，为每个节点添加这些额外的线索信息。这个过程可以在先序、中序或后序遍历的基础上进行²⁴。

源: 与必应的对话， 2024/4/9 (1) 线索二叉树怎么理解？ - 知乎. https://www.zhihu.com/question/46994916. (2) #图解 数据结构：轻松搞定线索二叉树 - 知乎 - 知乎专栏. https://zhuanlan.zhihu.com/p/134184036. (3) 线索二叉树 - 百度百科. https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037. (4) 线索二叉树（中序、先序、后续的前驱和后继）_线索二叉树的前驱和后继是什么-CSDN博客. https://blog.csdn.net/qq_35963993/article/details/106460166.

哈夫曼树

哈夫曼树（Huffman Tree），也称为最优二叉树，是一种特殊的二叉树。它是根据一组给定的权值构造出来的带权路径长度最短的二叉树。在哈夫曼树中，权值较大的节点离根较近，这样可以保证整棵树的带权路径长度尽可能小，从而达到数据压缩的目的¹²³。

构造哈夫曼树的过程是这样的：

1. 将每个权值视为一棵只有根节点的二叉树，形成一个森林。
2. 在森林中选出两棵根节点权值最小的树合并，新树的根节点权值为两棵子树根节点权值之和。
3. 将合并后的新树加入森林，删除原来的两棵树。
4. 重复步骤2和3，直到森林中只剩下一棵树，这棵树就是哈夫曼树。

哈夫曼树的一个重要应用是哈夫曼编码（左分支为0，右分支为1），它是一种广泛使用的数据压缩方法。在哈夫曼编码中，常见的字符使用较短的编码，不常见的字符使用较长的编码，这样可以有效减少编码后数据的大小¹。

源: 与必应的对话， 2024/4/9 (1) 数据结构——哈夫曼树（Huffman Tree） - 知乎 - 知乎专栏. https://zhuanlan.zhihu.com/p/415467000. (2) 哈夫曼树（最优二叉树）详解 - 知乎 - 知乎专栏. https://zhuanlan.zhihu.com/p/665686647. (3) 数据结构与算法—哈夫曼树详解与构造 - 知乎 - 知乎专栏. https://zhuanlan.zhihu.com/p/85576216. (4) 哈夫曼树_哈夫曼树性质-CSDN博客. https://blog.csdn.net/gao1440156051/article/details/49947993.

并查集

并查集是一种用于处理不相交集合的合并及查询问题的数据结构。它主要包括两个操作：

1. 合并（Union）：将两个不相交的集合合并为一个集合。
2. 查询（Find）：确定两个元素是否属于同一个集合。

并查集通过一个数组来表示一片森林，其中每个元素的父节点代表所属集合的标识。如果两个元素有相同的根节点，那么它们就在同一个集合中。并查集的优势在于它能够快速地合并集合并查找元素的集合归属，这使得它在解决诸如网络连接、最小生成树等问题时非常有效¹²³。

简单来说，如果你想知道森林中有几棵树，或者某个节点是否属于某棵树，你可以使用并查集来快速找到答案。并查集的实现通常涉及优化技巧，如路径压缩和按秩合并，以提高效率⁴⁵。

源: 与必应的对话， 2024/4/9 (1) 并查集基础 | 菜鸟教程. https://www.runoob.com/data-structures/union-find-basic.html. (2) 并查集是什么？-CSDN博客. https://blog.csdn.net/zhi258wei/article/details/115478852. (3) 算法学习笔记(1) : 并查集 - 知乎 - 知乎专栏. https://zhuanlan.zhihu.com/p/93647900. (4) 什么是 “并查集” ？-CSDN博客. https://blog.csdn.net/bjweimengshu/article/details/108332389. (5) 【算法与数据结构】—— 并查集-CSDN博客. https://blog.csdn.net/the_zed/article/details/105126583.

const int  N=1005					//指定并查集所能包含元素的个数（由题意决定）
int pre[N];     					//存储每个结点的前驱结点 
int rank[N];    					//树的高度 
void init(int n)     				//初始化函数，对录入的 n个结点进行初始化 
{
    for(int i = 0; i < n; i++){
        pre[i] = i;     			//每个结点的上级都是自己 
        rank[i] = 1;    			//每个结点构成的树的高度为 1 
    } 
}
int find(int x)     	 		    //查找结点 x的根结点 
{
    if(pre[x] == x) return x;  		//递归出口：x的上级为 x本身，则 x为根结点 
    return find(pre[x]); 			//递归查找 
} 
 
int find(int x)     				//改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点 
    return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx 
} 

bool isSame(int x, int y)      		//判断两个结点是否连通 
{
    return find(x) == find(y);  	//判断两个结点的根结点（即代表元）是否相同 
}

bool union(int x,int y)
{
    x = find(x);						//寻找 x的代表元
    y = find(y);						//寻找 y的代表元
    if(x == y) return false;			//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑
    if(rank[x] > rank[y]) pre[y]=x;		//如果 x的高度大于 y，则令 y的上级为 x
    else								//否则
    {
        if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同，则令 y的高度加1
        pre[x]=y;						//让 x的上级为 y
	}
	return true;						//返回 true，表示合并成功
}