什么时候可以在二叉树上使用简单的二叉树？

Question

很多教程都集中在二进制搜索树的实现上，这对于搜索操作来说更容易。是否存在实现简单二叉树比BST更好的应用程序或环境？还是只是作为树木的一个入门概念来教授呢？

Answer 1

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

                *
              /   \
             +     c
           /   \
          a     b

削皮堆是一种逻辑上是通用树的数据结构(即不限制节点可以拥有的子节点数量)，但它通常是使用左子右同胞二叉树实现的。与普通树相比，LCRS二叉树通常更高效、更容易处理。

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

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

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

你可以想象一棵任意深邃的树，每个层次都有问题。

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