本文仅为基于教材学习的发散思维笔记，并非对教材内容的抄录，因此有可能存在错误的理解，欢迎指教。
什么是二叉树
树形结构属于图论中的连通无环图。子节点数不超过 k 个的树，被称为 k-叉树。二叉树为 k-叉树的一种特例，但其特性足以涵盖后者，因此一般来说只需研究二叉树即可。
区别于元素之间具有明确的前导和后继定位的数组或链表这类线性结构，二叉树是半线性结构。每个父节点存在最多两个子节点。
二叉树的分类
二叉树
仅指每个节点最多包含2个子节点的树，对元素间大小、树高等属性均没有限制。
真二叉树
二叉树中，每个父节点的子节点数被称为度 (degree)。一个节点的度数可以为0（该节点为叶节点）、1（只有一个子节点）、2（左右子节点均存在）。
真二叉树就是所有节点的度数均为0或2的二叉树，即不存在单个子节点的二叉树。
二叉搜索树 BST
二叉树的子集，增加了定语“搜索”，特指元素间存在单调性（有序）的二叉树，但是对树高没有进行限制。
理想的二叉树
- 完全二叉树：叶节点只出现在最底的两层，且最底层叶节点均处于次底层叶节点的左侧。
- 满二叉树：叶节点只出现在最底层，且最底层的节点数正好为 2ʰ 个（h为树高，从0开始）。满树的节点数为 2ʰ⁺¹ - 1 个。
平衡二叉搜索树 BBST
在 BST 的基础上增加定语“平衡/Balanced”，特指各节点的左右子树之间高度差不超过1的 BST。
BBST 根据不同的特性，可进一步分为 AVL 树、伸展数、B树和红黑树等。
为什么要使用 BBST？
BBST 相较于线性结构（e.g. 完全二叉树 vs 链表）的优势：缩短搜索路径，使之从渐进 O(n) 优化为 O(logn)。假设链表由1024个元素组成，则找到最大值需要进行1024次遍历。由相同元素集组成的完全二叉搜索树，则只需要进行 log₂1024=10 次遍历即可，存在着两个数量级的优化。
这个自根节点往下到叶节点的搜索过程，实际上就是线性数组的二分搜索的变种。
二叉搜索树的高效搜索特性的核心是树的高度。如果一棵二叉树仅由左节点或仅由右节点组成，则会退化为线性结构 O(n)。
二叉树的层次表示
二叉树的层次使用“深度” depth 与“高度” height 这两个概念来描述。
深度 depth 指的是节点 node 到根节点 root 的通路中，经过的边 (edge) 的数量。高度 height 则为二叉树所有节点中的最大深度，即 Height(T)=Max(Depth(T))。
只有根节点的树（节点数为1），高度为0。空树（节点数为0）的高度为-1。
以 图01 为例，节点 B、E、I 的深度分别为 1、2和3，即这些节点到根节点 A 的边的数量。
必须注意的是，当我们在说“深度”或“高度”的时候，必须对其含义有清醒的认识（因为二者概念很相似）。深度的概念针对的是内部节点，而高度的概念针对的是根节点。
仍以 图01 为例，当我们说节点 E 的深度时，意思是“节点 E 到其所在二叉树的根节点 A 的边数”，即 Depth(E)=2。而当我们说节点 E 的高度时，意思是“以节点 E 为根节点的二叉树的高度”，因此 Height(E)=1。即同一个节点的高度和深度的概念，是相反的两个方向。
节点的关系
祖先节点 ancestor: 节点 v 通往根节点 r 的通路上途经的所有节点均为 v 的祖先节点，即 v 也是自己的祖先节点。
后代节点 descendant: 以节点 v 作为根节点的子树中，所有节点均为 v 的后代节点，即 v 也是自己的后代节点。
相应地，真祖先 (proper ancestor) /真后代 (proper descendant) 的概念才不含节点 v 自身。
而父子节点 (Parent/Child) 则特指层次数相差为1的祖先/后代节点。
度数：即子节点的数量。
子节点与子树：学习过程要注意这两个含义的区别。子节点特指一个节点；子树则由子节点和其真后代节点组成，可以把子树想象成一个庞大的集合。
单调性：BST 元素之间为全局有序，各个节点 V 的左子树均小于（或等于）V，而右子树的元素均大于（或等于）V。
层次遍历与深度遍历
与图的遍历相同，分为深度遍历（深度优先）和层次遍历（广度优先）两大类。
层次遍历只需要使用一个队列即可完成。
深度遍历则分为先序遍历 (pre-order)、中序遍历 (in-order) 和后序遍历 (post-order) 三种。所谓的先中后，针对的是当前节点的读取时机，而左右两个子节点之间无论何时都是先左后右。
假设二叉树由三个节点组成：父节点 V 和左节点 L、右节点 R 组成。则先序遍历为 V 先读，即VLR；中序遍历为 V 在中间，即 LVR；后序遍历为 V 在最后，即 LRV。
二叉搜索树的中序遍历，与相应线性结构的顺序相同。（想象在二叉搜索树正上方往下打光线，各元素在地上的投影正好按顺序单调递增/非降）
亲戚
堆结构（优先队列）的结构与 BST 相同。二者的区别在于有序性。
BST 的元素维持了全局有序。堆结构则只维持了局部的有序性（偏序性），即父节点为左右子树的最大值，但左子树中可以有元素大于右子树的元素。