二叉树是每个节点最多有两个子树的树结构，子树有左右之分，二叉树常被用于实现二叉查找树和二叉堆。
二叉树的第i层至多有$$2^{i-1}$$个结点；深度为k的二叉树至多有$$2^k-1$$个结点；对任何一棵二叉树T，如果其终端结点数为$$n_0$$，度为2的结点数为$$n_2$$，则$$n_0=n_2+1$$。
一棵深度为$$k$$，且有$$2^k-1$$个节点称之为满二叉树；深度为$$k$$，有$$n$$个节点的二叉树，当且仅当其每一个节点都与深度为$$k$$的满二叉树中序号为1至$$n$$的节点对应时，称之为完全二叉树。完全二叉树中重在节点标号对应。
编程实现
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点，或者根节点）、遍历左边子节点、遍历右边子节点。访问节点顺序的不同也就形成了不同的遍历方式。需要注意的是树的遍历通常使用递归的方法进行理解和实现，在访问元素时也需要使用递归的思想去理解。实际实现中对于前序和中序遍历可尝试使用递归实现。
按照访问根元素（当前元素）的前后顺序，遍历方式可划分为如下几种：
- 深度优先：先访问子节点，再访问父节点，最后访问第二个子节点。根据根节点相对于左右子节点的访问先后顺序又可细分为以下三种方式。
- 前序（pre-order）：先根后左再右
- 中序（in-order）：先左后根再右
- 后序（post-order）：先左后右再根
- 广度优先：先访问根节点，沿着树的宽度遍历子节点，直到所有节点均被访问为止。
TODO 需重点分析遍历顺序类题目
如下图所示，遍历顺序在右侧框中，红色A为根节点。使用递归和整体的思想去分析遍历顺序较为清晰。
二叉树的广度优先遍历和树的前序/中序/后序遍历不太一样，前/中/后序遍历使用递归，也就是栈的思想对二叉树进行遍历，广度优先一般使用队列的思想对二叉树进行遍历。
如果已知中序遍历和前序遍历或者后序遍历，那么就可以完全恢复出原二叉树结构。其中最为关键的是_前序遍历中第一个一定是根，而后序遍历最后一个一定是根，中序遍历在得知根节点后又可进一步递归得知左右子树的根节点。_但是这种方法也是有适用范围的：元素不能重复！否则无法完成定位。
对树相关的题进行复杂度分析时可统计对每个节点被访问的次数，进而求得总的时间复杂度。
一棵二叉查找树（BST）是一棵二叉树，其中每个节点都含有一个可进行比较的键及相应的值，且每个节点的键都大于等于左子树中的任意节点的键，而小于右子树中的任意节点的键。
使用中序遍历可得到有序数组，这是二叉查找树的又一个重要特征。
注意：有序数组的表示。
二叉查找树使用的每个节点含有两个链接，它是将链表插入的灵活性和有序数组查找的高效性结合起来的高效符号表实现。
TODO 什么是符号表？
主要思想：放弃文本文件的普通保存方式：不再使用7位或8位二进制数表示每一个字符，而是使用较少的比特表示出现频率最高的字符，用较多的比特表示出现频率低的字符。
使用长编码来表示字符串，势必会导致编解码时码字的唯一性问题，因此需要一种编解码方式唯一的前缀码，而表示前缀码的一种简单方式就是使用单词查找树，其中最优前缀码即为Huffman首创。
以符号F,O,R,G,E,T为例，只七出现的频次如以下表格所示。
| Symbol | F | O | R | G | E | T |
|---|---|---|---|---|---|---|
| Frequence | 2 | 3 | 4 | 4 | 5 | 7 |
| code | 000 | 001 | 100 | 101 | 01 | 11 |
则对各符号进行霍夫曼编码的动态演示如下图所示。基本步骤是将出现频率由小到大排列，组成子树后频率相加作为整体再和其他加入二叉树中的节点频率比较。加权路径长为节点的频率乘以树的深度。