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

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

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

    *
   / \
  +   2
 / \
1   3

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

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

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. In a binary tree a degree of every node is maximum two.

二叉树很有用，因为正如你在图中看到的，如果你想找到树中的任何节点，你最多只需要找6次。例如，如果您想搜索节点24，您将从根节点开始。

根节点的值为31，大于24，所以要到左边的节点。 左边节点的值为15，小于24，所以要转到右边节点。 右边节点的值为23，小于24，所以您要转到右边节点。 右边节点的值是27，大于24，所以要转到左边节点。 左边节点的值是25，比24大，所以你到左边节点。 节点的值为24，这是我们要查找的键。

如下图所示:

您可以看到，在第一次传递时就可以排除整个树的一半节点。左边子树的一半在第二个。这使得搜索非常有效。如果这是在40亿个元素上进行的，那么您最多只需要搜索32次。因此，树中包含的元素越多，搜索的效率就越高。

删除会变得很复杂。如果节点有0或1个子节点，那么只需移动一些指针来排除要删除的指针。但是，不能轻易删除具有2个子节点的节点。所以我们走捷径。假设我们要删除节点19。

由于试图确定将左右指针移动到哪里并不容易，所以我们找到一个替换它的指针。我们到左边的子树，尽可能地向右移动。这就给出了我们想要删除的节点的下一个最大值。

现在我们复制18的所有内容，除了左指针和右指针，并删除原来的18节点。

为了创建这些图像，我实现了一棵AVL树，一棵自平衡树，这样在任何时间点，树的叶节点(没有子节点)之间最多有一层差异。这可以防止树变得倾斜，并保持最大的O(log n)搜索时间，而插入和删除需要更多的时间。

下面是一个示例，显示我的AVL树如何保持自己尽可能紧凑和平衡。

在排序数组中，查找仍然需要O(log(n))，就像树一样，但是随机插入和删除将需要O(n)，而不是树的O(log(n))。一些STL容器利用这些性能特征来发挥它们的优势，因此插入和删除时间最多为O(log n)，非常快。这些容器包括map、multimap、set和multiset。

AVL树的示例代码可以在http://ideone.com/MheW8上找到

在c++ STL中，以及许多其他语言的标准库中，如Java和c#。二叉搜索树用于实现set和map。

几乎所有的数据库(和类数据库)程序都使用二叉树来实现它们的索引系统。

你的程序语法，或者其他很多东西，比如自然语言，都可以用二叉树来解析(虽然不一定)。

我认为“纯”二叉树没有任何用处。(教育用途除外) 平衡二叉树，如红黑树或AVL树更有用，因为它们保证O(logn)运算。普通的二叉树最终可能是一个列表(或几乎是列表)，在使用大量数据的应用程序中并没有真正的用处。

平衡树通常用于实现映射或集合。 它们也可以用于O(nlogn)排序，即使存在更好的方法。

也可以用于搜索/插入/删除哈希表，它通常比二叉搜索树(平衡与否)有更好的性能。

在需要搜索/插入/删除和排序的应用程序中，(平衡的)二叉搜索树将是有用的。排序可以在适当的位置(几乎，忽略递归所需的堆栈空间)，给定一个就绪的构建平衡树。它仍然是O(nlogn)，但有一个更小的常数因子，不需要额外的空间(除了新的数组，假设数据必须放入数组中)。另一方面，哈希表不能排序(至少不能直接排序)。

也许它们在一些复杂的算法中也很有用，但说实话，我什么也想不起来。如果我发现更多，我会编辑我的帖子。

其他树如f.e.b +树也广泛应用于数据库中