我想知道二叉树的具体应用是什么。你能举几个例子吗?
当前回答
当大多数人谈论二叉树时，他们通常会想到二叉搜索树，所以我将首先介绍它。
非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况的形式，即链表，因为简单的二叉树是不平衡的。
一个很好的例子:我曾经不得不修复一些软件，它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:
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趋于无穷时会发生什么。有些人可能不同意，但如果你确定数据集将保持在某个大小以下，只要没有其他现成的数据，使用冒泡排序甚至是可以的:-)
至于二叉树的其他用途，还有很多，例如:
二进制堆，其中较高的键高于或等于较低的键，而不是在左侧(或低于或等于或右); 哈希树，类似于哈希表; 用于计算机语言编译的抽象语法树 霍夫曼树用于数据压缩; 用于网络流量的路由树。
考虑到我为搜索树生成了很多解释，我不愿详细介绍其他搜索树，但如果您愿意，这应该足以研究它们了。
其他回答
二叉树的应用:
实现路由器中的路由表。 数据压缩码 表达式解析器和表达式求解器的实现 解决数据库问题，如索引。 表达式求值
当大多数人谈论二叉树时，他们通常会想到二叉搜索树，所以我将首先介绍它。
非平衡二叉搜索树实际上只对教育学生了解数据结构有用。这是因为，除非数据以相对随机的顺序进入，否则树很容易退化为最坏情况的形式，即链表，因为简单的二叉树是不平衡的。
一个很好的例子:我曾经不得不修复一些软件，它将数据加载到二叉树中进行操作和搜索。它把数据以排序的形式写出来:
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趋于无穷时会发生什么。有些人可能不同意，但如果你确定数据集将保持在某个大小以下，只要没有其他现成的数据，使用冒泡排序甚至是可以的:-)
至于二叉树的其他用途，还有很多，例如:
二进制堆，其中较高的键高于或等于较低的键，而不是在左侧(或低于或等于或右); 哈希树，类似于哈希表; 用于计算机语言编译的抽象语法树 霍夫曼树用于数据压缩; 用于网络流量的路由树。
考虑到我为搜索树生成了很多解释，我不愿详细介绍其他搜索树，但如果您愿意，这应该足以研究它们了。
几乎所有的数据库(和类数据库)程序都使用二叉树来实现它们的索引系统。
在c++ STL中，以及许多其他语言的标准库中，如Java和c#。二叉搜索树用于实现set和map。
我认为“纯”二叉树没有任何用处。(教育用途除外) 平衡二叉树，如红黑树或AVL树更有用，因为它们保证O(logn)运算。普通的二叉树最终可能是一个列表(或几乎是列表)，在使用大量数据的应用程序中并没有真正的用处。
平衡树通常用于实现映射或集合。 它们也可以用于O(nlogn)排序，即使存在更好的方法。
也可以用于搜索/插入/删除哈希表，它通常比二叉搜索树(平衡与否)有更好的性能。
在需要搜索/插入/删除和排序的应用程序中，(平衡的)二叉搜索树将是有用的。排序可以在适当的位置(几乎，忽略递归所需的堆栈空间)，给定一个就绪的构建平衡树。它仍然是O(nlogn)，但有一个更小的常数因子，不需要额外的空间(除了新的数组，假设数据必须放入数组中)。另一方面，哈希表不能排序(至少不能直接排序)。
也许它们在一些复杂的算法中也很有用，但说实话，我什么也想不起来。如果我发现更多，我会编辑我的帖子。
其他树如f.e.b +树也广泛应用于数据库中
