• 树（tree）是包含 n ( n ≥ 1 ) n(n\geq 1) n(n≥1)个节点， ( n − 1 ) (n-1) (n−1)条边的有穷集，其中：
  （1）每个元素称为节点（node）；
  （2）有一个特定的节点被称为根节点或树根（root）。
  （3）除根节点之外的其余数据元素被分为 m ( m ≥ 0 ) m(m\geq0) m(m≥0)个互不相交的集合 T 1 ， T 2 ， … … T m − 1 T_1，T_2，……T_{m-1} T1​，T2​，……Tm−1​，其中每一个集合 T i ( 1 ≤ i ≤ m ) T_i(1\leq i\leq m) Ti​(1≤i≤m)本身也是一棵树，被称作原树的子树（subtree）。
• 树也可以这样定义：树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。

1. 空树：具有0个节点的树。
2. 节点的度：一个节点含有的子节点的个数称为该节点的度，二叉树节点的度最大为2；
3. 叶节点或终端节点：度为0的节点称为叶节点；
4. 非终端节点或分支节点：度不为0的节点；
5. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8. 树的度：一棵树中，最大的节点的度称为树的度，二叉树最大的树的度为2；
9. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
10. 树的高度或深度：树中节点的最大层次；
11. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
12. 节点的祖先：从根到该节点所经分支上的所有节点；
13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
14. 森林：由 m ( m ≥ 0 ) m(m\geq 0) m(m≥0)棵互不相交的树的集合称为森林；

1. 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树,也称为自由树;
2. 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
3. 二叉树：每个节点最多含有两个子树的树称为二叉树；
4. 满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树，且叶节点全位于最底层；
5. 完全二叉树：设二叉树的深度为 k k k，除第 k k k 层外，其它 1 ∼ ( k − 1 ) 1 \sim (k-1) 1∼(k−1) 层的节点数都达到最大个数，第 k k k 层所有的节点都连续集中在最左边；或：一棵深度为 k k k的有 n n n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为 i ( 1 ≤ i ≤ n ) i(1\leq i \leq n) i(1≤i≤n)的节点与满二叉树中编号为 i i i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树；
6. 哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

1. 二叉树的第 i i i层最多具有 2 i − 1 ( i ≥ 1 ) 2^{i-1}(i\geq 1) 2i−1(i≥1)个节点，第 i i i层最少有 1 1 1个节点。
2. 深度为 k k k的二叉树最多有 2 k − 1 2^k-1 2k−1个节点，最少有 k k k个节点。
3. 对任意一棵二叉树，若其叶节点数为 n 0 n_0 n0​，度为2的节点数为 n 2 n_2 n2​，则有 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。
   推导：
   如上图，设总的边数为 B B B，总节点数为 n n n，度为0（叶节点）的节点数为 n 0 n_0 n0​，度为1的节点数为 n 1 n_1 n1​，度为2的节点数为 n 2 n_2 n2​。从下往上看，除根节点外每个节点都对应一条边，所以总边数 B = n − 1 B=n-1 B=n−1。从上往下看，度为2的节点对应两条边，度为1的节点对应一条边，所以总边数为 B = n 2 × 2 + n 1 B=n_2 \times 2+n_1 B=n2​×2+n1​。由上面两式得： n − 1 = n 2 × 2 + n 1 n-1=n_2 \times 2+n_1 n−1=n2​×2+n1​又因为 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0​+n1​+n2​，代入得 n 0 = n 2 + 1. n_0=n_2+1. n0​=n2​+1.
4. 深度为 k k k的满二叉树的节点数为 2 k − 1 2^k-1 2k−1，所有叶节点都在最底层，每层节点数都是最大节点数。
5. 完全二叉树的叶节点只可能分布在层次最大的两层上，对任一节点，若其右子树的层次为 i i i，那么其左子树最大层次为 i i i或 i + 1 i+1 i+1。
6. 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
7. 具有 n n n个节点的完全二叉树的深度为 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log_{2}n\rfloor+1 ⌊log2​n⌋+1。
8. 如果对于一棵具有 n n n个节点的完全二叉树，按层序（每层从左到右）对节点进行编号，则对任一编号为 i ( 1 ≤ i ≤ n ) i(1\leq i\leq n) i(1≤i≤n)的节点，有：
   1）若 i = 1 i=1 i=1，则节点 i i i是该树的根节点，无父节点；若 i > 1 i>1 i>1，则其父节点为 ⌊ i 2 ⌋ \lfloor \frac{i}{2} \rfloor ⌊2i​⌋；
   2）若 2 i > n 2i>n 2i>n，则该节点为叶节点，无左子节点，否则，左子节点为 2 i 2i 2i；
   3）若 2 i + 1 > n 2i+1>n 2i+1>n，则该节点无右子节点，否则，右子节点为 2 i + 1 2i+1 2i+1。

实现：按满二叉树的节点层次编号（从上到下，从左到右），定义一个数组依次存放二叉树中的数据元素。数据元素存放到数组中对应的编号下标位置。如下图示：

对于非满二叉树或非完全二叉树，对于空缺的节点，则将数组中该空缺编号对应位置置空，如下图示：

二叉树顺序存储结构有很大的缺点，首先是数组的容量固定，不适用于需要频繁插入增加节点的场景。其次，对于非满二叉树或者非完全二叉树，存储空间的利用率可能很低。最坏情况下，存储深度为k且只有k个节点的右单支树，需要长度为 2 k − 1 2^k-1 2k−1的数组。 如下图：

所以，顺序存储结构较适用于满二叉树或完全二叉树。

二叉树节点的特点如下图。对于主要对后继节点进行操作的场景，为节省存储空间，一般定义一个结构体来表示树的节点，该结构体仅包含三个信息（不包含父节点），即数据域、左子节点和右子节点：

typedef struct BiTreeNode
{
	ElemType data;
	struct BiTreeNode *lchild, *rchild;
}BiTreeNode, pBiTreeNode;

同理，对于主要对父节点进行操作的场景，也是定义一个结构体来表示树的节点，但该结构体应包含父节点的信息，即数据域、左子节点、右子节点和父节点：

typedef struct BiTreeNode
{
	ElemType data;
	struct BiTreeNode *lchild, *rchild， *parent;
}BiTreeNode, pBiTreeNode;

二叉树的遍历方式若以根节点的访问先后来命名的，分为三种：

1. 先访问根节点；
2. 先序遍历左子树；
3. 先序遍历右子树。

1. 中序便利左子树；
2. 访问根节点；
3. 中序遍历右子树。

中序遍历的非递归可以使用辅助栈来实现。

1. 后序遍历左子树；
2. 后序遍历右子树；
3. 访问根节点。

顾名思义，层次遍历，就是以树的层次，从上到下，从左到右对树进行遍历。可以通过队列来实现。具体为：

1. 将根节点入队；
2. 若队列不为空，从队列中出列一个节点，访问该节点。若该节点左子节点不为空，将左子节点入队；若该节点右子节点不为空，将右子节点入队。

当用二叉链表作为二叉树的存储结构时，可以很方便找到某个节点的左右子节点。但是一般情况下，无法直接找到该节点在某种遍历序列中的前驱和后继节点。
可能的解决办法，一是通过遍历寻找，但这样做浪费时间。二是增设两个指针域，一个指向前驱，一个指向后继，这会增加存储负担。

线索二叉树的思路是充分利用二叉链表中，节点的空指针域。
二叉链表中空指针域的数量：
具有 n n n个节点的二叉链表中，一共有 2 n 2n 2n个指针域，而因有n个节点，所以一共有 n − 1 n-1 n−1个子节点，所以只有 n − 1 n-1 n−1个指针域被用来指示左右子节点。故空指针域有 2 n − ( n − 1 ) = n + 1 2n-(n-1)=n+1 2n−(n−1)=n+1个。

如果某个节点的左子节点指针域为空，则将该指针域改为指向其前驱；如果其右子节点指针域为空，则将该指针域该为指向其后继。
这种改变指向的指针称为“线索”，加上线索的二叉树则称为线索二叉树。
对二叉树按某种遍历次序使其变为线索二叉树的过程称为“线索化”。
为了区分节点的左右子节点指针域是指向其子节点还是指向其前去和后继，需要对二叉链表中的每个节点增加两个标志域：ltag和rtag，并规定：
ltag=0，左子节点指针域指向左子节点
ltag=0，左子节点指针域指向节点的前驱
rtag=0，右子节点指针域指向右子节点
rtag=1，右子节点指针域指向节点后继

定义结构数组，存放树的节点，每个节点包含两个域：数据域和父节点域。
数据域：存放节点本身数据信息
父节点域：指示本节点的父节点在数组中的位置
特点：寻找父节点容易，寻找子节点难
如下图示

把每个节点的子节点排列起来，看成一个线性表，用单链表存储。则 n n n个节点有 n n n个子节点链表(叶子节点的子节点链表为空表)。而 n n n个子节点链表的头指针又组成线性表，用顺序表(含 n n n个元素的结构数组)存储。
特点：寻找父节点难，寻找子节点容易
如下图示

用二叉链表作树的存储结构，链表中的每个节点的指针域分别指向第一个子节点和下一个兄弟节点。
如下图示

由于树和二叉树都可以用二叉链表作存储结构，则用二叉链表作媒介可以导出树和二叉树的对应关系。对应关系如下图，本质是对表示树的二叉链表的解释方式不同，所以对应不同的树结构。

给定一棵树，一定可以找到一棵二叉树与之对应。

在实际转换过程中，不需要先将树以二叉链表的形式存储，然后再转换为二叉树。通过观察发现，树节点的兄弟节点在转换成二叉树后，会变成其右子节点，于是可以得出一下树转换成二叉树实现：

1. 加线：在兄弟节点之间加一条线
2. 抹线：对每一节点，除左子节点外，去除其与其他子节点的关系
3. 旋转：以树的根节点为轴心，将整棵树顺时针旋转 45 ° 45\degree 45°

口诀：兄弟相连留长子

同样通过观察，二叉树中某一左子节点的右子节点，右子节点的右子节点…转换成树后，都会成为该左子节点的兄弟。
二叉树转换成树的实现：

1. 加线：若节点p是其父节点的左子节点，则将p的右子节点，右子节点的右子节点…沿分支找到所有右子节点，都将它们与p的父节点连接起来
2. 抹线：抹掉原二叉树中父节点与右子节点的连线
3. 调整，将节点按层次排列，形成树的结构

口诀：左孩右右连双亲，去掉原来右孩线

1. 将每棵树分别转换成二叉树
2. 将每棵树的根节点用线相连
3. 以第一棵树的根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构

口诀：森林变二叉树，树变二叉根相连

1. 抹线：将二叉树中根节点与其右子节点的连线，及其沿右分支搜索到所有右子节点间的连线全部抹去，使之称为孤立的二叉树
2. 还原：将孤立的树还原成树（二叉树转换成树）

口诀：二叉树变森林，去掉所有右孩线，孤立二叉再还原

1. 先根遍历：若树不空，则先访问根节点，然后再先根遍历各棵子树
2. 后根遍历：若树不空，则先依次后根遍历各棵子树，然后再访问根节点
3. 层次遍历：若树不空，则自上而下自左往右访问树中的每个节点

将森林看成三部分组成：

1. 森林中第一棵树的根节点
2. 森林中第一棵树的子树森林
3. 森林中其他树构成的森林
   

若森林不空，则：

1. 访问森林中第一棵树的根节点
2. 先序遍历森林中第一棵树的子树森林
3. 先序遍历森林中其他树构成的森林

即从左到右一次森林中的每一棵树进行先根遍历

若森林不空，则：

1. 中序遍历森林中第一棵树的子树森林
2. 访问森林中第一棵树的根节点
3. 中序遍历森林中其他树构成的森林

即从左到右一次森林中的每一棵树进行后根遍历

1. 路径：从树的一个节点到另一个节点之间的分支构成这两个节点之间的路径。
2. 节点的路径长度：两节点路径上的分支数
   
3. 树的路径长度：从树根节点到每一个节点的路径长度之和。记作TL
   
   从上图可知，具有相同节点数的两棵树，其路径长度不一定相同。节点数目相同的二叉树中，完全二叉树的路径长度最短。（充分条件）
4. 权（权重，weight）：将树中节点赋予一个含有某种意义的值，则称这个数值为该节点的权
5. 节点的带权路径长度：从根节点到该节点的路径长度与该节点的权的乘积
6. 树的带权路径长度：树中所有叶节点的带权路径长度之和，记作： W P L ( Weighted Path Length ) = ∑ k w k l k WPL(\text{Weighted Path Length})=\sum_k w_k l_k WPL(Weighted Path Length)=k∑​wk​lk​
7. 哈夫曼树（最优树）就是带权路径长度（WPL）最短的树。注：“带权路径长度最短”是在“度相同”的树中比较得到的结果，度不相同的树比较没有意义，因此有最优二叉树，最优三叉树等分类
   
   由上图可知，完全二叉树不一定是哈夫曼树；具有相同带权节点的哈夫曼树不唯一。

观察下图的哈夫曼树，得出出贪心构造算法

算法步骤为：

1. 根据 n n n个给定的权值 { w 1 , w 2 . . . w n } \{w_1,w_2...w_n\} {w1​,w2​...wn​}构成具有 n n n棵树的森林 F = { T 1 , T 2 . . . T n } F=\{T_1,T_2...T_n\} F={T1​,T2​...Tn​}，其中 T i T_i Ti​为只有一个带权为 w i w_i wi​的根节点（构造森林全是根）
2. 在 F F F中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左右子树根节点的权值之和（选用两小造新树）
3. 从 F F F中删除这两棵树，并把新构造的二叉树树加入 F F F中（删除两小添新人）
4. 重复步骤2，3，直至 F F F中仅剩一棵树，此时，这棵树即为哈夫曼树（重复2，3剩单根）

对于给定的 n n n个节点，利用上述贪心算法构造哈夫曼树，需要两两合并 n − 1 n-1 n−1次，每次合并增加一个节点，所以最终得到的哈夫曼树共有 2 n − 1 2n-1 2n−1个节点；并且只有度数为0或2的节点，没有度数为1的节点。

在远程通信中，要将待传字符转换成由二进制表示的字符串

• 设要传送的字符为：ABACCDA
  若采用等长编码为：A——00，B——01，C——10，D——11，则转换后的二进制表示为：00010010101100
• 若将编码设计成长度不等的二进制编码，即让待传字符串中出现字数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。
• 设要传送的字符依然是：ABACCDA
  若采用不等长编码为：A——0，B——00，C——1，D——01，则转换后的二进制表示为：000011010。这时出现重码的现象，如前4个0，可以表示AAAA、ABA、BB等。
• 于是设计不等长编码的关键是，必须使任一字符的编码都不是另一任意字符编码的前缀，这也称为前缀编码。
• 什么样的前缀码能使电文总长最短？问题的解决办法就是利用哈夫曼编码，哈夫曼编码是哈夫曼树的典型应用。

1. 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。
2. 利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的节点路径越短。
3. 在哈夫曼树的每个分支上标记0或1：节点的左分支标0，右分支标1。把从根到每个叶节点路径上的标号连接起来，作为该叶节点代表的字符的编码。

• 例题
  

1. 为什么哈夫曼编码能保证是前缀编码？
   因为没有一个叶节点是另一个叶节点的祖先（如上图，字符都被叶节点代表，这是哈夫曼树的特性），所以每个叶节点的编码不可能是其他叶节点编码的前缀。
2. 为什么哈夫曼编码能保证字符编码总长最短？
   因为哈夫曼树的带权路径长度最短，所以字符编码总长最短。

从上述两个问题可以得到哈夫曼编码的两个相应性质：

1. 哈夫曼编码是前缀码
2. 哈夫曼编码是最优前缀码

编码过程：

• 输入各字符及其权值
• 根据权值构造哈夫曼树
• 进行哈夫曼编码
• 查询编码结果，得到各字符的哈夫曼编码

解码过程：

• 构造与编码时相同的哈夫曼树
• 依次读入二进制码，读入0，则走向左子节点，读入1，则走向右子节点
• 一旦到达叶节点，即可译出字符
• 然后再从根节点出发，重复上面两个步骤，直至全部译出

• 二叉排序树（Binary Sort Tree）又称为二叉搜索树或二叉查找树。
• 定义
  或是空树，或是满足以下性质：
  • 若其左子树非空，则左子树上的所有节点的值均小于根节点的值。
  • 若其右子树非空，则右子树上的所有节点的值均大于根节点的值。
  • 其左右子树又各是一棵二叉排序树。
• 性质：中序遍历非空的二叉树所得到的数据元素序列，是一个按关键字排列的递增有序序列。

• 若查找的关键字等于根节点，成功
• 否则
  • 若小于其根节点，查找其左子树
  • 若大于其根节点，查找其右子树
• 在左右子树上重复上述步骤。查找过程中，左右子树为空则查找失败。

• 查找过程中比较关键字次数=此节点所在层数，树的深度为 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log_2n \rfloor +1 ⌊log2​n⌋+1。
• 含有 n n n个节点的二叉排序树的查找效率（平均查找长度）和树的形态有有关。
• 最好情况（树形态比较均衡）： O ( log ⁡ n ) O(\log n) O(logn)。
• 最坏情况（树为单支树形态）： O ( n ) O(n) O(n)。

• 若插入的二叉排序树为空，则插入节点作为根节点插入到空树中。
• 否则，继续在其左右子树上查找
  • 树中已有，不再插入
  • 树中没有
    • 查找直至某个叶节点的左子树或者右子树为空为止，则插入节点作为该叶节点的左子节点或右子节点。
• 插入节点一定在叶节点上。

• 从空树出发，经过一系列的查找、插入操作后，可得到一棵二叉排序树。
  
• 一个无序序列可通过构造二叉排序树而变成一棵有序序列。构造树的过程就是对无序序列进行排序的过程。
• 插入的节点均为叶节点，故无需移动其他节点。相当于在有序序列上插入而无需移动其他记录。
• 关键字的输入顺序不同，生成的二叉排序树的形态不同。
  

• 从二叉树中删除一个节点，不能把以该节点为根的子树都删除，只能删掉该结点，并且保证删除后所得的二叉树还能满足二叉排序树的性质。
• 由于中序遍历二叉排序树可以得到一个递增有序的序列，那么删除一个节点相当于删除这个有序序列中的一个元素。
  • 将删除节点而断开的二叉链表重新连接。
  • 防止重新连接后的树高度增加。
• 删除操作
  • 被删除的节点为叶节点，则直接删除，并将父节点的对应指针域置空。
  • 被删除的节点只有左子树或者右子树，则用其左子树或者右子树替换它。父节点的相应指针域改为指向该左子树或右子树。
  • 被删除节点既有左子树又有右子树。
    • 以其中序遍历序列的前驱值替换之，然后再删除该前驱值所在的节点。前驱节点即是左子树中值最大的节点。
    • 也可以以其中序遍历序列的后继值替换之，然后再删除该后继值所在的节点。后继节点即是右子树中值最小的节点。
      

• 旨在解决二叉排序树形态不均衡的查找效率低的问题。
• 做“均衡化处理”，尽量让二叉树形态均衡。

• 平衡二叉树（Balanced Binary Tree），又称AVL树（Adelson-Velskii-Landis）。
• 一棵平衡二叉树或是空树，或是具有以下性质的二叉排序树：
  • 左子树和右子树的高度差的绝对值小于等于1。
  • 左子树和右子树也是平衡二叉排序树。
• 为方便起见，给每个节点添加一个数字，记录该节点左子树和右子树的高度差。这个数字称为节点的平衡因子。 平衡因子=节点左子树高度-节点右子树高度 \textbf{平衡因子=节点左子树高度-节点右子树高度} 平衡因子=节点左子树高度-节点右子树高度
• 根据平衡因子的定义，平衡二叉树上所有节点的平衡因子的取值只能是 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1}。
• 如果在一棵AVL树上插入节点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

• 四种失衡形态：因为C的插入，导致A节点失衡。不止一个失衡节点时，A是最小失衡树的根节点。
  
• 调整方法
  
• 调整原则：
  • 降低高度
  • 保持二叉排序树的性质
• LL型调整过程
  • B节点带其左子树 α \alpha α一起上移。
  • A节点成为B节点的右子节点。
  • 原来B节点的右子树 β \beta β成为A节点的左子树。
    
• RR型调整过程
  • B节点带其右子树 β \beta β一起上移。
  • A节点成为B节点的左子节点。
  • 原来的B节点的左子树 α \alpha α作为A的右子树。
    
• LR型调整过程
  • C节点穿过A，B节点上移。
  • B节点成为C节点的左子节点，A节点成为C节点右子节点。
  • 原来C节点的左子树 β \beta β成为B节点的右子树，原来C节点的右子树 γ \gamma γ成为A节点的左子树。
    
• RL型调整过程
  • C节点穿过A，B节点上移。
  • A节点成为C节点的左子节点，B节点成为C节点右子节点。
  • 原来C节点的左子树 β \beta β成为A节点的右子树，原来C节点的右子树 γ \gamma γ成为B节点的左子树。