我想知道二叉树的具体应用是什么。你能举几个例子吗?
当大多数人谈论二叉树时，他们通常会想到二叉搜索树，所以我将首先介绍它。
非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况的形式，即链表，因为简单的二叉树是不平衡的。
一个很好的例子:我曾经不得不修复一些软件，它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:
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趋于无穷时会发生什么。有些人可能不同意，但如果你确定数据集将保持在某个大小以下，只要没有其他现成的数据，使用冒泡排序甚至是可以的:-)
至于二叉树的其他用途，还有很多，例如:
二进制堆，其中较高的键高于或等于较低的键，而不是在左侧(或低于或等于或右); 哈希树，类似于哈希表; 用于计算机语言编译的抽象语法树 霍夫曼树用于数据压缩; 用于网络流量的路由树。
考虑到我为搜索树生成了很多解释，我不愿详细介绍其他搜索树，但如果您愿意，这应该足以研究它们了。
我认为“纯”二叉树没有任何用处。(教育用途除外) 平衡二叉树，如红黑树或AVL树更有用，因为它们保证O(logn)运算。普通的二叉树最终可能是一个列表(或几乎是列表)，在使用大量数据的应用程序中并没有真正的用处。
平衡树通常用于实现映射或集合。 它们也可以用于O(nlogn)排序，即使存在更好的方法。
也可以用于搜索/插入/删除哈希表，它通常比二叉搜索树(平衡与否)有更好的性能。
在需要搜索/插入/删除和排序的应用程序中，(平衡的)二叉搜索树将是有用的。排序可以在适当的位置(几乎，忽略递归所需的堆栈空间)，给定一个就绪的构建平衡树。它仍然是O(nlogn)，但有一个更小的常数因子，不需要额外的空间(除了新的数组，假设数据必须放入数组中)。另一方面，哈希表不能排序(至少不能直接排序)。
也许它们在一些复杂的算法中也很有用，但说实话，我什么也想不起来。如果我发现更多，我会编辑我的帖子。
其他树如f.e.b +树也广泛应用于数据库中
最常见的应用之一是高效地以排序形式存储数据，以便快速访问和搜索存储的元素。例如，std::map或std::set在c++标准库中。
二叉树作为一种数据结构，对于表达式解析器和表达式求解器的各种实现非常有用。
它也可以用来解决一些数据库问题，例如，索引。
一般来说，二叉树是一种特定的基于树的数据结构的一般概念，各种特定类型的二叉树可以构造成具有不同性质的二叉树。
关于二叉树，还有一个有趣的例子没有提到，那就是递归求值的数学表达式。从实际的角度来看，它基本上是无用的，但它是一种有趣的方式来考虑这样的表达式。
基本上，树的每个节点都有一个值，这个值要么是自身固有的，要么是通过对其子节点的值进行操作来递归计算的。
例如，表达式(1+3)*2可以表示为:
*
/ \
+ 2
/ \
1 3
为了求表达式的值，我们要求父元素的值。这个节点又从它的子节点，一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值，并将它们相加，将4返回给返回8的乘法节点。
这种二叉树的使用在某种意义上类似于反向抛光表示法，因为执行操作的顺序是相同的。还有一点需要注意的是，它不一定是二叉树，只是最常用的操作符是二叉的。在最基本的层次上，这里的二叉树实际上只是一种非常简单的纯函数式编程语言。
争论二叉树的性能是没有意义的——它们不是一种数据结构，而是一组数据结构，它们都具有不同的性能特征。虽然不平衡二叉树的搜索性能确实比自平衡二叉树差得多，但对于许多二叉树(如二进制尝试)来说，“平衡”是没有意义的。
二叉树的应用
Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered. Binary Tries - Used in almost every high-bandwidth router for storing router-tables. Hash Trees - Used in torrents and specialized image-signatures in which a hash needs to be verified, but the whole file is not available. Also used in blockchains for eg. Bitcoin. Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort. Huffman Coding Tree (Chip Uni) - Used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats. GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers. Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions. Treap - Randomized data structure used in wireless networking and memory allocation. T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.
二叉树比n-ary树更常用于搜索的原因是n-ary树更复杂，但通常不会提供真正的速度优势。
在一个有m节点的(平衡的)二叉树中，从一层移动到下一层需要进行一次比较，并且有log_2(m)层，总共有log_2(m)次比较。
相比之下，一个n元树将需要log_2(n)个比较(使用二叉搜索)来移动到下一层。由于总共有log_n(m)个级别，因此搜索将需要log_2(n)*log_n(m) = log_2(m)个比较。因此，尽管n元树更复杂，但就必要的总体比较而言，它们没有提供任何优势。
(然而，n-ary树在生态位环境中仍然有用。首先想到的例子是四叉树和其他空间划分树，其中每层只使用两个节点划分空间会使逻辑不必要地复杂;以及在许多数据库中使用的b -树，其中限制因素不是在每个级别上进行多少比较，而是一次可以从硬盘加载多少节点)
在现代硬件上，由于糟糕的缓存和空间行为，二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们，则说明性能不重要(或由比较函数主导)，或者更可能是由于历史或无知的原因。
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上找到
二叉树最重要的应用之一是平衡二叉搜索树，比如:
红黑树 AVL树 替罪羊树
这些类型的树具有这样的特性，即通过每次插入或删除节点时进行旋转等操作，将左子树和右子树的高度差保持在较小的范围内。
因此，树的整体高度保持为log n的阶数，并且搜索、插入和删除节点等操作在O(log n)时间内执行。c++的STL也以集合和映射的形式实现了这些树。
使用二叉树表示AST的编译器可以使用已知的算法 解析树像海报，有序。程序员不需要提出自己的算法。 因为源文件的二叉树比n元树高，所以构建它需要更多的时间。 以这个生产为例: selstmnt:= "if" "(" expr ")" stmnt "ELSE" stmnt 在二叉树中，它将有3层节点，但n-ary树将有1层(子节点)
这就是为什么基于Unix的操作系统很慢的原因。
