1、树
- 结点的度：该结点所拥有的子树的个数
- 叶子结点：度为 0 的结点
- 树的度：树中各个结点度的最大值
![](/blog/image/1bcf98f3bf8f4d35b09a55d292fb02d4_1651329176.png/)

2、二叉树
假设根的深度为 1 ：
- 性质1：二叉树的第 $i$ 层上的结点数目**最多**为 $2^{i-1} (i>=1)$
- 性质2：深度为 $k$ 的二叉树**至多**有 $2^k-1 (k>=1)$
- 性质3：叶子结点的个数为 $n_0$，度为 $2$ 的结点个数为 $n_2$，对于任意一个二叉树，均有：$n_0 = n_2 + 1$

**性质2证明：**
![](/blog/image/193fac389e8245da93c0c516efe5a0a6_1651329214.png/)

**性质3证明：**
![](/blog/image/1f6908eb8e6c43aa9014a44bf23e58c4_1651329327.png/)

在满二叉树的最下一层上，从最右边开始连续删除若干个结点后，就可得到一颗完全二叉树。
![](/blog/image/594adf12c2444a96b4336990231665e2_1651329252.png/)

2.1、二叉树遍历
      前序遍历：ABDECFG
      中序遍历：DBEAFCG
      后序遍历：DEBFGCA
      宽度优先搜索（广度优先、横向优先）：ABCDEFG
      深度优先搜索：ABDECFG

3、表达式
运算符（+，-，*，/）为根结点
运算数为叶子结点
中缀表达式  ----- 中序遍历：（A+B）*（C-D）
前缀表达式、波兰式  ----- 前序遍历：*+AB-CD
后缀表达式、逆波兰式 ----- 后序遍历：AB+CD-*

举例：请把 表达式 ((35+15)*(80-70))/20 （ 中缀表达方式 ）  转成前缀和后缀表达式

35,15,+,80,70,-,*,20,/               //后缀表达方式
/,*,+,35,15,-,80,70, 20             //前缀表达方式

习惯的运算方式是中缀表达式。而碰到前缀，后缀方式会有点迷茫其实仅仅是一种表达式子的方式而已（不被你习惯的方式）

这里教你一种简单转换方式：一个中缀式到其他式子的转换方法~

这里我给出一个中缀表达式~

a+b*c-(d+e)

第一步：按照运算符的优先级对所有的运算单位加括号~
        式子变成了：((a+(b*c))-(d+e))

第二步：转换前缀与后缀表达式
        前缀：把运算符号移动到对应的括号前面
              则变成了：-( +(a *(bc)) +(de))
              把括号去掉：-+a*bc+de  前缀式子出现
        后缀：把运算符号移动到对应的括号后面
              则变成了：((a(bc)* )+ (de)+ )-
              把括号去掉：abc*+de+-  后缀式子出现

通过以上的方式发现：前缀式，后缀式是不需要用括号来进行优先级的确定的。

4、树的计数问题（卡特兰数）
具有 n 个结点的不同形态的二叉树有多少棵？B0 = 1, B1=1, B2=2, B3=5, B4=14...
一般情况下，一棵具有 n 个结点的二叉树可以看成是由一个根结点、一棵具有 i 个结点的左子树，和一棵具有 n - i -1 个结点的右子树组成，其中 0 <= i <= n-1，由此得出递推公式：
$B_0 = 1$
$B_n  = \sum_{i=0}^{i \le n-1} {B_i*B_{n-i-1} } $  (n >= 1)

通项公式 =  $\frac{C^n_{2n}}{n+1}$

5、二叉查找（排序）

6、哈夫曼编码（又称最优二叉树，是一种带权路径长度最短的二叉树）

哈夫曼树相关的几个名词：
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
![](/blog/image/e9c0381696354f7e8bd9dc8fae4f4495_1651329497.png/)
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

什么是哈夫曼树

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫 "赫夫曼树" 或者 "哈夫曼树"。
在构建哈夫曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

构建哈夫曼树

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。

举例子：

五个字符：a,b,c,d,e 它们出现的的频率为8，14，10，4，18，请你构造相应的哈夫曼树，求出每个字符的哈夫曼编码。

（先不看以下的答案，自己在草稿纸上做一遍！！）
答案：

问：哈夫曼树编码一定是左边为 0,右边为 1 吗?

答：0 和 1 表示左子树还是右子树没有明确规定。因此左右节点的顺序是任意的,所以构造出的哈夫曼树并不唯一，但是各个哈夫曼树的带权路径长度相同且为最优。

哈夫曼树：（我们把树的左右子树，编码按左边 0 右边 1来）
           54
   0  /           \   1
    22             32
0 /      \ 1   0 /    \   1
c:10  12   b:14  e:18
     0  /   \  1
     d:4    a:8

以上标注为红色的为哈夫曼编码：
a 的哈夫曼编码为 011  ，它的编码长度为 3

b 的哈夫曼编码为 10  ，它的编码长度为 2

c 的哈夫曼编码为 00，它的编码长度为 2

d 的哈夫曼编码为 010，它的编码长度为 3

e 的哈夫曼编码为 11，它的编码长度为 2

1、树 - 结点的度：该结点所拥有的子树的个数 - 叶子结点：度为 0 的结点 - 树的度：树中各个结点度的最大值

2、二叉树假设根的深度为 1 ： - 性质1：二叉树的第 $i$ 层上的结点数目最多为 $2^{i-1} (i>=1)$ - 性质2：深度为 $k$ 的二叉树至多有 $2^k-1 (k>=1)$ - 性质3：叶子结点的个数为 $n_0$，度为 $2$ 的结点个数为 $n_2$，对于任意一个二叉树，均有：$n_0 = n_2 + 1$

性质2证明：

性质3证明：

在满二叉树的最下一层上，从最右边开始连续删除若干个结点后，就可得到一颗完全二叉树。

2.1、二叉树遍历前序遍历：ABDECFG 中序遍历：DBEAFCG 后序遍历：DEBFGCA 宽度优先搜索（广度优先、横向优先）：ABCDEFG 深度优先搜索：ABDECFG

3、表达式运算符（+，-，，/）为根结点运算数为叶子结点中缀表达式 ----- 中序遍历：（A+B）（C-D）前缀表达式、波兰式 ----- 前序遍历：+AB-CD 后缀表达式、逆波兰式 ----- 后序遍历：AB+CD-

举例：请把表达式 ((35+15)*(80-70))/20 （中缀表达方式）转成前缀和后缀表达式

35,15,+,80,70,-,,20,/ //后缀表达方式 /,,+,35,15,-,80,70, 20 //前缀表达方式

习惯的运算方式是中缀表达式。而碰到前缀，后缀方式会有点迷茫其实仅仅是一种表达式子的方式而已（不被你习惯的方式）

这里教你一种简单转换方式：一个中缀式到其他式子的转换方法~

这里我给出一个中缀表达式~

a+b*c-(d+e)

第一步：按照运算符的优先级对所有的运算单位加括号~ 式子变成了：((a+(b*c))-(d+e))

第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成了：-( +(a (bc)) +(de)) 把括号去掉：-+abc+de 前缀式子出现后缀：把运算符号移动到对应的括号后面则变成了：((a(bc) )+ (de)+ )- 把括号去掉：abc+de+- 后缀式子出现

通过以上的方式发现：前缀式，后缀式是不需要用括号来进行优先级的确定的。

4、树的计数问题（卡特兰数）具有 n 个结点的不同形态的二叉树有多少棵？B0 = 1, B1=1, B2=2, B3=5, B4=14... 一般情况下，一棵具有 n 个结点的二叉树可以看成是由一个根结点、一棵具有 i 个结点的左子树，和一棵具有 n - i -1 个结点的右子树组成，其中 0 <= i <= n-1，由此得出递推公式： $B_0 = 1$ $B_n = \sum_{i=0}^{i \le n-1} {B_i*B_{n-i-1} } $ (n >= 1)

通项公式 = $\frac{C^n_{2n}}{n+1}$

5、二叉查找（排序）

6、哈夫曼编码（又称最优二叉树，是一种带权路径长度最短的二叉树）

哈夫曼树相关的几个名词：路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

什么是哈夫曼树

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫 "赫夫曼树" 或者 "哈夫曼树"。在构建哈夫曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

构建哈夫曼树

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

举例子：

五个字符：a,b,c,d,e 它们出现的的频率为8，14，10，4，18，请你构造相应的哈夫曼树，求出每个字符的哈夫曼编码。

（先不看以下的答案，自己在草稿纸上做一遍！！）答案：

问：哈夫曼树编码一定是左边为 0,右边为 1 吗?

哈夫曼树：（我们把树的左右子树，编码按左边 0 右边 1来） 54 0 / \ 1 22 32 0 / \ 1 0 / \ 1 c:10 12 b:14 e:18 0 / \ 1 d:4 a:8

以上标注为红色的为哈夫曼编码： a 的哈夫曼编码为 011 ，它的编码长度为 3

b 的哈夫曼编码为 10 ，它的编码长度为 2

c 的哈夫曼编码为 00，它的编码长度为 2

d 的哈夫曼编码为 010，它的编码长度为 3

e 的哈夫曼编码为 11，它的编码长度为 2

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

二叉树杂谈