数据结构树和二叉树有哪些实际应用？
一个单位有10个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）
5 20 10 12 8 4 3 5 6 9
问应该如何设计个内线电话号码，使得接线员拨号次数尽可能少？
这是哈夫曼树的应用。
一种数据结构，用于保存和处理树状的数据，如家谱。
应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理。
二叉树再排序、查找、大规模数据索引方面有很多很多应用。
二叉树排序是简单算法排序中速度最快的。
树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针Treap 是每个节点都带个随机的 priority number, parent priority >= child priority。
自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上，如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界。
树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:Double Array - trie 的一个经典实现。
每个节点可以存一段字符串而不限于一个字符Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储,。
不过压缩效果一般HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie nodeMARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。
