目录
1.树的概念
2.二叉树的概念
二叉树（Binary Tree）
满二叉树（Full Binary Tree）
完全二叉树（Complete Binary Tree）
3.堆和二叉树
4、二叉树的结构
1.二叉树的逻辑结构
2.二叉树的物理结构
1.树的概念
树（Tree）是一种非常常见的数据结构，它是由若干个节点（Node）组成的层次结构，其中一个节点作为根节点（Root），其他节点按照一定规则分层连接。每个节点可以有任意多个子节点，也可以没有子节点。如下图所示是一棵简单的树：
A/ | \B C D/ \ /|\E F G H I在这个例子中，节点 A 是根节点，B、C、D 是 A 的子节点；B 又有 E、F 两个子节点，D 又有 G、H、I 三个子节点。
树的主要应用场景包括：文件系统、目录结构、程序执行流程、HTML/XML 文档对象模型等等。下面是一些树相关的术语：
- 节点的度数（Degree）：指其拥有的子节点数。
- 叶子节点（Leaf Node）：没有子节点的节点称为叶子节点（也叫终端节点）。
- 父节点（Parent Node）：若一个节点有子节点，则这个节点是其子节点的父节点。
- 子节点（Child Node）：一个节点下面的直接连接的节点称为其子节点。
- 兄弟节点（Sibling Node）：拥有同一父节点的节点互为兄弟节点。
- 树的深度（Height）：指树中节点的最大层数，即从根节点到最远叶子节点的距离。
- 子树（Subtree）：以某个节点为根节点，它下面的所有节点和连线所组成的树形结构。
在实际应用中，树可以通过多种方式来表示和实现，例如采用指针、数组、哈希表等数据结构来存储节点和连接关系。常见的树结构包括二叉树、平衡树、B 树、红黑树等，在这些树结构基础上还可以派生出各种高级数据结构，如堆、哈夫曼树、字典树等等。
2.二叉树的概念
二叉树（Binary Tree）
是一种特殊的树形结构，它由若干个节点组成，这些节点中最多只有两个子节点。通常将左侧节点称为左子节点（Left Child），右侧节点称为右子节点（Right Child）。如果一个节点没有子节点，那么它就是一个叶子节点（Leaf Node）。每个节点都可以有零个、一个或两个子节点。
下面是一个简单的二叉树示例：
1/ \2 3/ \ / \4 5 6 7在这个二叉树中，节点1是根节点，节点2和节点3是1的子节点；节点2又有两个子节点4和5，节点3也有两个子节点6和7。
二叉树的应用非常广泛，例如在排序算法中，二叉树可以用于快速查找和排序数据；在计算机科学中，二叉树可以用于存储程序代码的语法分析树；在图形学中，二叉树可以用于实现平衡搜索树（AVL Tree）等等。
需要注意的是，二叉树不同于二叉搜索树（BST），前者只是树的一种特殊形式，而后者是基于二叉树的一种高效的数据结构。
满二叉树（Full Binary Tree）
是一种特殊的二叉树，其中每个节点都恰好有0个或2个子节点。也就是说，如果一个节点有一个子节点，那么它肯定没有另一个子节点。满二叉树的节点总数为 2h−12h−1，其中 hh 是树的高度。
下面是一个满二叉树的例子：
1/ \2 3/ \ / \4 5 6 7
在该满二叉树中，每个节点都恰好有0个或2个子节点。
完全二叉树（Complete Binary Tree）
则是指除了最后一层外，其他层都被填满，最后一层从左边开始连续地填充节点。也就是说，如果最后一层不是满的，只能缺失右侧的连续若干节点。
下面是一个完全二叉树的例子：
1/ \2 3/ \ /4 5 6
在该完全二叉树中，最后一层缺失了一个右侧的节点6，但仍然保持了从左至右连续填充节点的规则。需要注意的是，满二叉树是完全二叉树的一种特殊情况。满二叉树中每个节点都有两个子节点，因此如果把它的最后一层填满，就可以得到一个完全二叉树。反之，如果一个完全二叉树（除了最后一层）也是满二叉树，那么它的最后一层就必须也是满的。
3.堆和二叉树
堆是一种特殊的二叉树，通常用来实现优先队列。堆可以看做一个完全二叉树，其中每个节点的值不小于（或不大于）它的子节点的值，被称为最大堆或最小堆。堆和普通的二叉树的主要区别在于它们的结构和性质。与普通的二叉树不同，堆必须满足以下两个条件：
1.堆是一棵完全二叉树
堆是一种完全二叉树，也就是说，如果将堆中的所有元素从上到下、从左到右依次编号，则这些编号必须恰好对应完全二叉树中的结点编号。这个性质保证了堆的高度尽可能小，也保证了堆中元素的分布比普通的二叉树更加紧凑。
2.堆中每个节点的键值都不大于/不小于其父节点的键值
这是堆的核心性质，也是实现优先队列功能的关键。对于最大堆来说，堆中的任何一个非叶子结点的键值都不小于其子节点的键值，因此堆顶元素是堆中最大的元素。而最小堆则相反，非叶子结点的键值都不大于其子节点的键值，堆顶元素是堆中最小的元素。通过这个性质，堆可以保证堆顶元素是优先级最高（或最低）的元素，使得用堆实现优先队列的操作变得简单且高效。
综上所述，堆和普通的二叉树相比，具有独特的结构和核心性质，使其成为了一种高效的数据结构，广泛应用于算法设计和实现中。
4、二叉树的结构
逻辑结构表示了树中节点之间的关系，二叉树的物理结构指的是如何在计算机中存储和表示这棵二叉树。
1.二叉树的逻辑结构
从逻辑上看，二叉树是由若干个节点和这些节点之间的关系构成。具体来说，每个节点包含一个数据元素和两个指向左右子节点的指针，如果某个节点没有左子节点或者右子节点，则对应的指针为空。节点之间的关系可以描述为：“根节点与子节点的连接”、“父节点与子节点的连接”、“兄弟节点之间的关系”等。
二叉树的逻辑结构有许多特殊的形态，例如满二叉树、完全二叉树、平衡二叉树等等。这些特殊的形态在算法设计和实现中都有着重要的作用。
2.二叉树的物理结构
二叉树的物理结构有多种不同的实现方式，常见的方法包括顺序存储和链式存储。
顺序存储：顺序存储是将二叉树存储在数组中，通过数组下标实现对节点的引用。对于一棵深度为 k 的二叉树，最多有 2k+1−12k+1−1 个结点，因此可以使用大小为 2k+12k+1 的数组存储二叉树。在顺序存储的方式中，每个节点都占用一个数组元素，空节点则用一个特殊的值表示。
链式存储：链式存储是通过指针来实现对二叉树节点的引用。在链式存储中，每个节点都包含数据元素和左右子节点的指针，这些指针指向左右子节点的内存地址。与顺序存储不同，链式存储方式不需要预先知道二叉树的大小，也可以动态地插入或删除节点。
