二叉树在存储层次数据时是否有特定的用途？它们的规范用途是什么？

Question

我了解二叉树的结构以及如何遍历它们。然而，我正在努力实现他们的实际用途，在程序和编程中的目的。当我想到“现实生活”中的分层数据的例子时，他们几乎肯定有两个以上的孩子。例如，在家谱中，母亲可能有两个以上的孩子。

由于处理数组和列表的时间更快，“二叉树”真的只对存储线性相关的数据有用吗？或者，它们在存储分层数据方面是否有特定的用途？如果是的话，有哪些应用二叉树的例子。一个节点最多有2个子节点的数据是什么？

Answer 1

不，二叉树不是用来存储你所想到的层次数据的。N叉树的主要用例(其中n是一个固定的数)是快速搜索能力，而不是语义层次。

还记得以前的游戏，一个人想到一个介于1到100之间的数字，而另一个人必须尽可能少地猜测它，如果你猜错了，思考这个数字的人必须告诉你你是太高还是太低？过了一段时间，你会觉得很无聊，因为你很快就会发现，你应该总是从50开始，然后再到25或75，然后再把搜索范围除以两半，再加上每次新的猜测，最终你最多可以猜出7种猜测，这是肯定的。

它可能不是一个有趣的游戏，但是这个属性使二进制(和其他n进制)树很有用:您可以用它们在很短的时间内搜索一个非常大的数据集。

Answer 2

任何树结构，其中的节点可以有无限的子，可以实现使用二叉树。

对于树中的每个节点，用右指针和左指针替换它。左指针指向节点的第一个子节点。正确的节点转到节点的下一个同级。给定节点的所有子节点都在一个由其右指针连接的链接列表中，该列表的头由其父节点的左指针指向。

你的复杂的n叉树变成了一个简单的二叉树。

我肯定这是在Knuth，Vol.1的某个地方。

Answer 3

二叉树为什么要用它们？

在编程中，您需要大量使用相同类型数据的集合。

存储这些数据的两种基本方法是:链接列表和数组。

它们都有其优点和缺点:在链接列表中，在任何位置添加元素或删除元素都很容易。但是对特定元素的访问更困难，因为您必须遍历列表，直到到达所需的元素为止。

• 它不能有效地搜索，但插入和删除是容易的。

使用数组访问特定元素很容易，但是插入或删除元素比较困难，因为插入意味着:按1扩展数组，将插入位置1之前的所有元素移到右边，然后插入元素。

• 它有效地搜索(如果排序)，但插入和删除是困难的。

因此，链表和数组都有缺点。

二叉树用于处理数组和链接列表的两个问题：

1. 容易插入和删除
2. 易搜索

因此，二叉树是为当你有大量的数据，有规律的变化。