二叉树的用法

4

在C＃中，使用Java，Python，C++（使用STL）以及其他高级语言，大部分时间您将使用内置/库 - 之一包括用于存储数据的类型，至少是当前处理的数据，所以大多数情况下您不会明确使用二叉树或其他类型的树。

这就是说，这些内置类型中的一些被实现为“在后台”的一种或另一种树，在某些情况下，您将不得不自己实现一个。

此外，你必须知道的相关事情是二分查找。这主要是在二叉树（二叉搜索树：P）中完成的，但即使没有涉及树，这个想法也可以外推到很多问题上，所以试着理解它。

编辑：现实生活中经典的例子：

试想一下，你要搜索一个特定的人在大城市的电话指导的电话号码。所有的事情都是平等的，你会在中间大概打开它，寻找那个页面中的人，看看你的“目标”是在它之前还是之后，从而将数据减半。然后在你知道你的“目标”的那一半重复这个操作，并且一次又一次地直到你找到你的“目标”。由于每次查看前一半的数据时，都需要执行一次log（base 2）n操作才能到达“目标”，其中n是数据的总大小。因此，在一百万个电话簿中，您可以在log（基数2）100万= 20的比较中找到您的目标，而不是像在线性搜索中那样逐一比较（在最差情况下是100万比较）。

请注意，这只适用于已排序的数据。

来源

2009-11-09 02:36:25 AntonioMO

0

一个简单的例子就是搜索。例如，如果您将列表数据存储在树中，则会得到O（log（n））查找时间。列表的标准数组实现将实现O（n）查找时间。

来源

2009-11-09 00:55:48

+0

因此，你可以存储任何你想存储在树中的数组？但是在树中，查找时间更少......我想这只适用于包含大量数据的数据结构。 – 2009-11-09 00:57:53

+1

@Tony：不一定。任何具有显式层次结构的东西都适用于树（可能不是二叉树，但一般树），即使它不是那么多项目。（考虑你的家谱：即使你不知道你的许多亲属仍然是一棵树！） – 2009-11-09 01:26:58

+1

二叉搜索树需要** O **（log2 * n *）比较。线性列表需要** O **（* n */2）。在8个元素中，您会发现树需要（至多）3个比较，但线性搜索需要（平均）4. – 2009-11-09 01:58:38

1

在Java中，树木被用于实现某些排序的数据结构，如TreeSet的：

http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html

它们用于在您想要的顺序是基于的某些属性数据结构元素，而不是放置顺序。

来源

2009-11-09 00:55:55 Peter

0

XML，HTML（和SGML）文档是树。

来源

2009-11-09 00:57:16

+0

但是它们不是二叉树吗？因为它们可能有两个以上属于一个节点的子节点，所以它不符合二叉树规则。 – Tarik 2009-11-09 01:07:46

+0

它们是n元树，任何节点都可以有任意数量的子节点。它用于灵活性（所以你的HTML文档可以有任何结构），其中二叉树和它的堂兄弟（红/黑等）被构建用于存储大量数据并且相对于数字非常快地插入或检索任何数据项存储在树中的东西。 – 2009-11-09 01:21:48

+0

嗯 - 现在我不记得n-ary树是否是正确的词。不过，我的其他描述还是可以的。 – 2009-11-09 01:26:10

4

Balanced binary trees，存储数据维护按排序顺序，用于实现O（log（n））查找，删除和插入时间。 “平衡”仅仅意味着在最浅和最深叶片的深度之间存在有界限，将空的左/右节点计为叶片。（最好左边和右边的子树的深度最多相差一个，有些实现可以放宽这个使算法更简单）

您可以使用二进制搜索的排序顺序来使用数组而不是树，以实现O（ log（n））查找时间，但插入/删除时间是O（n）。

某些树（特别是数据库的B-trees）在每个节点上使用2个以上的分支，以扩大树并减少最大深度（决定搜索时间）。

~~我想不出有什么理由使用未按排序顺序维护的二叉树（这里没有提到大多数答案），但也许有一些应用程序。~~ 除了排序后的二进制平衡树之外，任何具有层次结构的东西（如其他回答者已经提到的，XML或目录结构）对树来说都是一个很好的应用程序，无论是否是二元树。

编辑：回复：未排序的二叉树：我只记得LISP和Scheme都大量使用不平衡的二叉树。 cons函数接受两个参数（例如(define c (cons a b))）并返回一个树节点，其分支是两个参数。 car函数接受这样一个树节点并返回给予cons的第一个参数。 cdr函数类似，但将第二个参数返回到cons。最后nil代表一个空对象。这些是用来制作LISP和Scheme中所有数据结构的原语。列表是使用极端不平衡二叉树实现的。含有文字元素'Alabama，'Alaska，'Arizona列表，'Arkansas可以明确地构造为

(cons 'Alabama (cons 'Alaska (cons 'Arizona (cons 'Arkansas nil))))

，并且可以使用car和cdr（其中car用来获取该列表的头部和cdr被遍历用于得到不包括列表头的子列表）。这是计划如何运作，我认为LISP是相同或非常相似的。更复杂的数据结构，如二叉树（每个节点需要3个成员：两个用于保存左右节点，第三个用于保存节点值）或包含每个节点两个以上分支的树可以使用列表构造实现每个节点。

来源

2009-11-09 01:02:00

3

Unix下的目录结构如何？例如，du命令，即磁盘使用命令执行表示目录结构的树的遍历命令遍历（遍历顺序::左子节点 - >右子节点 - >根节点），以便获取该目录使用的磁盘空间。

下面的幻灯片应该有所帮助。

http://www.cse.unt.edu/~rada/CSCE3110/Lectures/Trees.ppt

欢呼

来源

2009-11-09 01:13:00 Arnkrishn

+0

很好的例子 - 尽管目录结构不是二叉树 – 2009-11-09 01:31:28

+0

是的，它们不是二叉树。托尼在他的提问中提到了一棵普通的树，我只是把它贴出来。 – Arnkrishn 2009-11-09 02:26:21

1

下面是一些例子：

解析的程序或表达的内存中表示为树。在表达式（不包括三元运算符）的情况下，该树将是二元的。
GUI的组件被组织为一棵树。
任何“包容”层次结构都可以表示为一棵树。（HTML，XML和SGML是实例。

当然而且，二进制文件（和n进制）树可以被用来表示索引，地图，组等的“通用”的数据结构。

来源

2009-11-09 02:56:54

二叉树的用法

回答

相关问题