data-structures - 我们什么时候可以在二叉搜索树上使用简单二叉树？

Question

很多教程侧重于二叉搜索树的实现，搜索操作更容易。是否存在实现简单二叉树比 BST 更好的应用程序或情况？或者它只是作为树木的介绍性概念教授的？

标签： data-structuresbinary-treebinary-search-tree

Answer 1

当您的结构需要一个父级和最多两个子级时，您可以使用二叉树（而不是二叉搜索树）。例如，考虑一棵树来表示数学表达式。表达式(a+b)*c变为：

                *
              /   \
             +     c
           /   \
          a     b

Paring heap是一种逻辑上是通用树的数据结构（即对节点可以拥有的子节点数量没有限制），但它通常使用左子右兄弟二叉树来实现。LCRS 二叉树通常比一般树更有效且更易于使用。

二叉堆也是二叉树，但不是二叉搜索树。

玩家回答一堆是/否问题以获得答案的古老猜谜游戏是二叉树的另一个例子。在下面的树中，左孩子是“否”的答案，右孩子是“是”的答案

                           Is it an animal?
                        /                    \
                 Is it a plant?          Is is a mammal?
                                         /            \
                                     A reptile?      A dog?

您可以想象一个任意深度的树，每个级别都有问题。

这些只是几个例子。我发现二叉树在很多不同的情况下都很有用。