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


当前回答

关于二叉树,还有一个有趣的例子没有提到,那就是递归求值的数学表达式。从实际的角度来看,它基本上是无用的,但它是一种有趣的方式来考虑这样的表达式。

基本上,树的每个节点都有一个值,这个值要么是自身固有的,要么是通过对其子节点的值进行操作来递归计算的。

例如,表达式(1+3)*2可以表示为:

    *
   / \
  +   2
 / \
1   3

为了求表达式的值,我们要求父元素的值。这个节点又从它的子节点,一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值,并将它们相加,将4返回给返回8的乘法节点。

这种二叉树的使用在某种意义上类似于反向抛光表示法,因为执行操作的顺序是相同的。还有一点需要注意的是,它不一定是二叉树,只是最常用的操作符是二叉的。在最基本的层次上,这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

其他回答

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

关于二叉树,还有一个有趣的例子没有提到,那就是递归求值的数学表达式。从实际的角度来看,它基本上是无用的,但它是一种有趣的方式来考虑这样的表达式。

基本上,树的每个节点都有一个值,这个值要么是自身固有的,要么是通过对其子节点的值进行操作来递归计算的。

例如,表达式(1+3)*2可以表示为:

    *
   / \
  +   2
 / \
1   3

为了求表达式的值,我们要求父元素的值。这个节点又从它的子节点,一个加号运算符和一个只包含“2”的节点中获取它的值。加号运算符依次从值为“1”和“3”的子运算符中获取其值,并将它们相加,将4返回给返回8的乘法节点。

这种二叉树的使用在某种意义上类似于反向抛光表示法,因为执行操作的顺序是相同的。还有一点需要注意的是,它不一定是二叉树,只是最常用的操作符是二叉的。在最基本的层次上,这里的二叉树实际上只是一种非常简单的纯函数式编程语言。

在现代硬件上,由于糟糕的缓存和空间行为,二叉树几乎总是次优的。这也适用于(半)平衡的变种。如果您发现了它们,则说明性能不重要(或由比较函数主导),或者更可能是由于历史或无知的原因。

最常见的应用之一是高效地以排序形式存储数据,以便快速访问和搜索存储的元素。例如,std::map或std::set在c++标准库中。

二叉树作为一种数据结构,对于表达式解析器和表达式求解器的各种实现非常有用。

它也可以用来解决一些数据库问题,例如,索引。

一般来说,二叉树是一种特定的基于树的数据结构的一般概念,各种特定类型的二叉树可以构造成具有不同性质的二叉树。

二叉树最重要的应用之一是平衡二叉搜索树,比如:

红黑树 AVL树 替罪羊树

这些类型的树具有这样的特性,即通过每次插入或删除节点时进行旋转等操作,将左子树和右子树的高度差保持在较小的范围内。

因此,树的整体高度保持为log n的阶数,并且搜索、插入和删除节点等操作在O(log n)时间内执行。c++的STL也以集合和映射的形式实现了这些树。