视频字幕
今天我们来学习两种重要的二叉树结构:线索化二叉树和霍夫曼树。虽然它们都是二叉树,但用途完全不同。线索化二叉树通过在空指针域添加线索来优化遍历操作,而霍夫曼树则是为了数据压缩而构建的最优二叉树。
线索化二叉树的核心思想是利用二叉树中的空指针域。在普通二叉树中,叶子节点和只有一个孩子的节点会有空指针,这些空间被浪费了。线索化二叉树通过添加标志位来区分指针的用途:当标志位为0时,指针指向孩子节点;当标志位为1时,指针作为线索指向前驱或后继节点。这样可以在不使用栈的情况下进行中序遍历。
霍夫曼树的构建过程体现了贪心算法的思想。首先将所有字符按权值排序,然后每次选择权值最小的两个节点进行合并。比如权值为1和2的节点合并成权值为3的新节点。接着继续选择最小的两个节点,可能是刚才合并的节点和其他节点。重复这个过程直到只剩下一个根节点,就得到了霍夫曼树。这样构建的树保证了带权路径长度最小。