二叉树的深度 二叉树的深度怎么算公式
树(Tree)是n(n≥0)个结点的有限集。
- 若n=0，则它表示一个空树。
- 每个树都有根结点，其余结点可分为m（m≥0）个互不相交的有限集T1，T2，T3，... ，Tm，其中每一个集合本身又是一棵树，并称为根的子树。
根结点：在非空树中，没有前驱结点的结点被称为根结点。
结点的度：结点拥有的子树数就是其度。
树的度：树中所有结点的度的最大值。
树的最大层次：树中结点的最大层次数。
终端结点：当度为0时的结点。非终端结点则拥有至少一个子树。
内部结点：除根节点外的非终端结点。
孩子、双亲：一个结点的子树的根称为该结点的孩子，而该结点称为孩子的双亲。
结点的祖先：从根到该节点所经分支上的所有结点。
结点的子孙：以某结点为根的子树中的任一结点。
有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。
无序树：树中结点的各子树无次序。
森林：m(m≥0)棵互不相交的树的集合。
二叉树是n(≥0)个结点的有限集。它或者是空集 (n = 0)，或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。
二叉树的每个结点的位置或者说次序都是固定的，可以是空，但是不可以说它没有位置。而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了。
将数据文件转换成由0、1组成的二进制串，这个过程被称为编码。
以二叉树表示表达式的递归定义如下：
- 若表达式为数或简单变量，则相应二叉树中仅有一个根结点。
- 若表达式为“第一操作数 运算符 第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符。
遍历二叉树是树的重要操作之一。遍历结果将决定二叉树的后续操作。常见的遍历方式有前序遍历、中序遍历和后序遍历。
满二叉树是一种特殊的二叉树，每一层上的结点数都是最大结点数。叶子结点全部在最底层。
完全二叉树深度为k且具有n个结点的二叉树中，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。它是满二叉树的一种扩展形式。
为了在二叉链表中进行特定操作（如层次遍历），需要使用队列来存储待访问的结点。队列的先进先出特性使得我们可以自上而下、自左至右地访问每个结点，得到树中所有结点的一个线性排列。
哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩等领域。其构造算法包括构建森林、合并森林、删除小树添加新根等步骤。
通过对树、二叉树及哈夫曼树等数据结构的定义和性质的探讨，我们可以更好地理解其内在逻辑和实际应用场景。这些数据结构为后续的算法设计和实现提供了坚实的基础。
在信息论中，哈夫曼算法是一种用于无损数据压缩的算法。其核心思想是通过构建哈夫曼树来实现对数据的优化编码。下面我们将详细解析哈夫曼算法的原理和步骤。
一、哈夫曼树的构建
在哈夫曼算法中，初始时有n棵二叉树。经过n-1次合并，最终会形成一棵哈夫曼树。这n-1次合并会产生n-1个新结点，而这些新结点都是具有两个子节点的分支结点。哈夫曼树中总共有2n-1个结点，且其所有的分支结点的度（即子节点的数量）均不为1。
为了实现这一过程，我们可以采用顺序存储结构，即一维结构数组。具体操作如下：
1. 初始化HT[1...2n-1]，将leftchild、rightchild和parent都置为0。
2. 输入初始n个结点，置HT[1...n]的weight的值。这些weight通常代表字符在电文现的概率，概率越大，要求编码越短。
3. 进行n-1次合并操作，依次产生n-1个结点HT[i]，其中i从n+1开始递增至2n-1。
具体合并步骤如下：
- 在HT[1...i-1]中选择两个未被选过（即parent值为0的结点中）的weight最小的两个结点HT[s1]和HT[s2]。
- 生成新的HT[i]，其weight为HT[s1].weight与HT[s2].weight之和，leftchild值为s1，rightchild值为s2。
二、哈夫曼编码的生成
在构建完哈夫曼树后，我们可以为其分配编码。具体做法是在树的每个分支上标上0或1：左分支标0，右分支标1。然后，从根开始，将路径上的标号连接起来，作为该叶子代表的字符的编码。
三、哈夫曼编码的特性
关于哈夫曼编码的两个常见问题：
1. 为什么哈夫曼编码能够保证是前缀编码？
答：因为哈夫曼树的构建过程中，确保了没有一片树叶是另一片树叶的祖先。这意味着每个叶结点的编码不可能是其它叶结点编码的前缀，从而保证了哈夫曼编码的前缀性。
2. 为什么哈夫曼编码能够保证字符编码总长最短？
答：因为在哈夫曼树的构建过程中，权值越大的叶子离根越近。这保证了哈夫曼树具有最小的带权路径长度。使用哈夫曼树进行编码时，字符的编码总长最短。