我想知道二叉树的具体应用是什么。你能举几个例子吗?


当前回答

使用二叉树表示AST的编译器可以使用已知的算法 解析树像海报,有序。程序员不需要提出自己的算法。 因为源文件的二叉树比n元树高,所以构建它需要更多的时间。 以这个生产为例: selstmnt:= "if" "(" expr ")" stmnt "ELSE" stmnt 在二叉树中,它将有3层节点,但n-ary树将有1层(子节点)

这就是为什么基于Unix的操作系统很慢的原因。

其他回答

BST是一种二叉树,在Unix内核中用于管理一组虚拟内存区域(vma)。

摩尔斯电码的结构是二叉树。

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

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

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

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

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

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

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

主要应用是二叉搜索树。这是一种数据结构,其中搜索、插入和删除都非常快(大约log(n)次操作)