关于二叉树，还有一个有趣的例子没有提到，那就是递归求值的数学表达式。从实际的角度来看，它基本上是无用的，但它是一种有趣的方式来考虑这样的表达式。

基本上，树的每个节点都有一个值，这个值要么是自身固有的，要么是通过对其子节点的值进行操作来递归计算的。

例如，表达式(1+3)*2可以表示为:

    *
   / \
  +   2
 / \
1   3

为了求表达式的值，我们要求父元素的值。这个节点又从它的子节点，一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值，并将它们相加，将4返回给返回8的乘法节点。

这种二叉树的使用在某种意义上类似于反向抛光表示法，因为执行操作的顺序是相同的。还有一点需要注意的是，它不一定是二叉树，只是最常用的操作符是二叉的。在最基本的层次上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

java.util.Set的实现

关于二叉树，还有一个有趣的例子没有提到，那就是递归求值的数学表达式。从实际的角度来看，它基本上是无用的，但它是一种有趣的方式来考虑这样的表达式。

基本上，树的每个节点都有一个值，这个值要么是自身固有的，要么是通过对其子节点的值进行操作来递归计算的。

例如，表达式(1+3)*2可以表示为:

    *
   / \
  +   2
 / \
1   3

为了求表达式的值，我们要求父元素的值。这个节点又从它的子节点，一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值，并将它们相加，将4返回给返回8的乘法节点。

这种二叉树的使用在某种意义上类似于反向抛光表示法，因为执行操作的顺序是相同的。还有一点需要注意的是，它不一定是二叉树，只是最常用的操作符是二叉的。在最基本的层次上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

当大多数人谈论二叉树时，他们通常会想到二叉搜索树，所以我将首先介绍它。

非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况的形式，即链表，因为简单的二叉树是不平衡的。

一个很好的例子:我曾经不得不修复一些软件，它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:

Alice
Bob
Chloe
David
Edwina
Frank

所以，当读入它的时候，最终会得到下面的树:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

也就是简并形式。如果你要在那棵树中寻找弗兰克，你必须搜索所有六个节点才能找到他。

当你平衡二叉树时，它们对搜索真正有用。这涉及到通过根节点旋转子树，以便任何两个子树之间的高度差小于或等于1。每次将上面的名字添加到平衡树中，会得到以下序列:

1.   Alice
    /     \
   =       =

 

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

 

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

 

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

 

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

 

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

实际上，你可以看到整个子树在添加条目时向左旋转(在步骤3和6中)，这就得到了一个平衡的二叉树，其中最坏情况的查找是O(log N)，而不是简并形式给出的O(N)。在任何情况下，最高的NULL(=)与最低的NULL(=)的差异都不超过一个级别。在上面的最后一棵树中，您可以通过查看三个节点(Chloe、Edwina和最后的Frank)找到Frank。

当然，当你把它们做成平衡的多路树而不是二叉树时，它们会变得更有用。这意味着每个节点拥有一个以上的项(从技术上讲，它们拥有N个项和N+1个指针，二叉树是1路多路树的特殊情况，有1个项和2个指针)。

使用三向树，你最终会得到:

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

这通常用于维护项索引的键。我编写了针对硬件优化的数据库软件，其中节点的大小恰好是磁盘块(比如512字节)，您可以在单个节点中放入尽可能多的键。在这种情况下，指针实际上是记录数字到一个固定长度的记录直接访问文件，与索引文件分开(因此，记录数字X可以通过查找X * record_length找到)。

例如，如果指针为4字节，键大小为10，则512字节节点中的键数为36。这是36个键(360字节)和37个指针(148字节)，总共508个字节，每个节点浪费4个字节。

多路键的使用引入了两阶段搜索的复杂性(寻找正确节点的多路搜索与查找节点中正确键的小顺序(或线性二进制)搜索相结合)，但较少的磁盘I/O的优点远远弥补了这一点。

我认为没有理由为内存结构这样做，您最好坚持使用平衡的二叉树并保持代码简单。

还要记住，当你的数据集很小时，O(log N)比O(N)的优势并不会真正显现出来。如果您使用多路树来存储15个人在您的地址簿，这可能是多余的。当您存储过去十年来自数十万客户的每一笔订单时，优势就显现出来了。

大o符号的全部意义在于指出当N趋于无穷时会发生什么。有些人可能不同意，但如果你确定数据集将保持在某个大小以下，只要没有其他现成的数据，使用冒泡排序甚至是可以的:-)

---

至于二叉树的其他用途，还有很多，例如:

二进制堆，其中较高的键高于或等于较低的键，而不是在左侧(或低于或等于或右); 哈希树，类似于哈希表; 用于计算机语言编译的抽象语法树 霍夫曼树用于数据压缩; 用于网络流量的路由树。

考虑到我为搜索树生成了很多解释，我不愿详细介绍其他搜索树，但如果您愿意，这应该足以研究它们了。

它们可以作为一种快速排序数据的方法。在O(log(n))处将数据插入二叉搜索树。然后遍历树，对它们进行排序。

在现代硬件上，由于糟糕的缓存和空间行为，二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们，则说明性能不重要(或由比较函数主导)，或者更可能是由于历史或无知的原因。