数据结构：树

诸神缄默不语-个人CSDN博文目录

我和ChatGPT一起制作了一个框架，现在只填充了一部分，具体的在补了。

1. 树的基本概念

1.1 树的定义

树是一种非线性的数据结构，由节点（或称作顶点）和连接节点的边组成。它具有一个特殊的节点，称为根节点，树中的任意两个节点之间都有唯一的路径相连。

1.2 树的术语

• 节点：树的基本部分，可以有0个或多个子节点。
• 边：连接两个节点的线。
• 根：没有父节点的节点。
• 路径：从一个节点到另一个节点的节点序列。
• 深度：从根节点到指定节点的边的数量。
• 高度：从指定节点到最远叶子节点的最长路径上的边的数量。

1.3 树的性质

1.4 树的存储结构（顺序存储和链式存储）

2. 二叉树

2.1 二叉树的定义

二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左子节点和右子节点。

2.2 特殊二叉树

1. 满二叉树

满二叉树是一种特殊的二叉树，其中每一层的所有节点都完全填满，不存在空的位置。

2. 完全二叉树

3. 平衡二叉树（AVL树）

4. 红黑树

2.3 二叉树的遍历

1. 前序遍历

2. 中序遍历

3. 后序遍历

4. 层次遍历

2.4 二叉树的操作

1. 插入节点

2. 删除节点

3. 多路搜索树

1. 2-3树

2. B树

3. B+树

4. 堆

1. 堆的定义与性质

堆是一种特殊的完全二叉树，其中每个节点的值都满足堆的性质：在最大堆中，任意节点的值大于等于其子节点的值，或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值；在最小堆中，任意节点的值小于等于其子节点的值。

2. 最大堆与最小堆的操作

1. 插入元素

自底向上

2. 堆化（Heapify）

堆化是一种调整堆结构的过程，以维护其性质。
当从堆中删除元素或插入新元素时，通过堆化过程来恢复堆的顺序。

删除堆顶元素后：
自底向上：从第二层开始选择比较大的节点往上挪（会产生气泡）
自顶向下：把最后一个元素挪到顶，然后往下挪

3. 删除堆顶元素

3. 特殊堆结构

1. 斐波那契堆

2. 二项堆

3. 左倾堆

4. 斜堆

参考资料

1. 二叉搜索树_百度百科
2. 二叉排序树_二叉排序树升序-CSDN博客
3. 「图解数据结构」堆：这篇公式很乱
4. 二叉树的先序、中序、后序遍历C++_二叉树的先序,中序,后序遍历-CSDN博客
5. 二叉树（八）:二叉树的全部路径_二叉树路径-CSDN博客