ShannonChenCHN
commented
3 years ago 理论部分（一）
参考：
一、树的基本概念
- 父节点
- 子节点
- 兄弟节点
- 根节点
- 叶子节点/叶节点
- 高度（Height）
- 深度（Depth）
- 层（Level）
二、分类
- 二叉树（Binary Tree）
- 满二叉树、完全二叉树
- 二叉查找树（Binary Search Tree）
- 平衡二叉查找树
- 红黑树（）
- 堆（Heap）
- AVL树（AVL Tree）
- B 树/B-树（B-Tree）
- 基数树(Radix Tree)
- 最小生成树(Minimum Spanning Tree)
- 红黑树（Red-Black Tree）
- 线段树（Segment Tree）
- 二叉线索树(Threaded Binary Tree)
- 前缀树/字典树（Trie）
- 并查集(Union-Find)
三、二叉树
二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，如下图所示。
A
/ \
B C
/ \ / \
D E F G
/ \ / \ / \ / \
H I J K L M N O完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
A
/ \
B C
/ \ / \
D E F G
/ \ / \
H I J K Swift 实现的二叉树：
/// Definition for a binary tree node.
class TreeNode<T> {
var data: T
var left: TreeNode<T>?
var right: TreeNode<T>?
init(_ data: T, _ left: TreeNode?, _ right: TreeNode?) {
self.data = data
self.left = left
self.right = right
}
convenience init(_ data: T) {
self.init(data, nil, nil)
}
}二叉树的可视化：
extension TreeNode: CustomStringConvertible {
var description: String {
return toString()
}
/// Print a [large] tree by lines.
/// See https://stackoverflow.com/a/8948691
func toString(_ content: String = "", _ prefix: String = "", _ childrenPrefix: String = "") -> String {
var content = content
content += prefix
content += "\(data)"
content += "\n"
var children = [TreeNode<T>]()
if let left = left {
children.append(left)
}
if let right = right {
children.append(right)
}
for (i, child) in children.enumerated() {
if i == children.count - 1 {
content = child.toString(content, childrenPrefix + "└── ", childrenPrefix + " ")
} else {
content = child.toString(content, childrenPrefix + "├── ", childrenPrefix + "│ ")
}
}
return content
}
}打印出来的效果：
15
├── 14
│ ├── 13
│ └── 15
└── 16
├── 15
└── 17四、完全二叉树的由来（如何表示/存储一棵二叉树？）
想要存储一棵二叉树，我们有两种方法：
- 基于指针或者引用的二叉链式存储法
- 基于数组的顺序存储法
链式存储法示意图：
顺序存储法示意图：
如图所示，如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
图中的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。
所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
补充：后面要讲到的堆也是一种完全二叉树，最常用的存储方式就是数组。
五、二叉树的遍历（重点）
二叉树遍历：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。
四种遍历方式：
- 前序遍历（Pre-order）：根-左-右
- 中序遍历（In-order / depth-first）：左-根-右
- 后序遍历（Post-order）：左-右-根
- 层序遍历（Level-order）：先访问根节点和离根节点最近的子节点，再访问子节点的子节点，也就是说按照从高到低的层级顺序来访问。宽度优先也算是一种层级遍历。
实际上，二叉树的前、中、后序遍历就是一个递归的过程。 这三种遍历方式的递推公式如下：
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r从上面的前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)。
关于前、中、后序遍历，以及层序遍历的实现，详见下面的练习题。
题目列表
1. 二叉树
二叉搜索树
堆 见 #25
平衡二叉树
其他
总结