19. 树与字典树¶
19.1. 树与字典树¶
我们看到，所有编码以 '0' 开头的字母都存储在左分支中， 而所有编码以 '1' 开头的字母都存储在右分支中。 把这与在 BST 中存储记录的做法对比一下。 在 BST 中，所有键值小于根结点值的记录都存储在左分支中， 而所有键值大于根结点值的记录都存储在右分支中。
回想一下，Huffman 编码树把所有编码以 0 开头的字母存储在左分支中， 把所有编码以 1 开头的字母存储在右分支中。 我们可以用同样的概念把记录存储在一棵搜索树中， 其行为与 BST 略有不同。 我们可以把所有存储的键看作位于一条数轴上。 BST 根据接收键值的顺序，按这些值的位置来划分数轴。 相比之下，我们可以像 Huffman 编码树那样， 根据键值的二进制表示来划分它们。 下面的幻灯片将更详细地展示这一点。
