部分有序树是否与二叉树相同？

Question

我对部分有序的树如何工作有点困惑.它们和二叉树有什么相同之处？另外,它最适合用于什么？

例如,如果我将5,6,4,9,3,1,7插入空树中,我会得到:

      5
     / \
    4   6
  /      \
 3       9
/       /
1      7

Answer 1

二叉树是树的特定形状.具体来说,二叉树是一棵树,其中每个节点可以有0,1或2个子节点.二叉树对节点中可以存储的值或者这些值如何相互关联没有限制,因此以下所有都是有效的二叉树:

     1           4             9
    /           / \           / \
   3           2   6         3   6     
  / \         /     \       / \   \
 3   2       1       8     0   2   4 

部分排序的树是一种树,其中存在一组特定的限制,其中值可以是树中的位置.具体来说,部分排序的树 - 顺便说一下,通常称为堆排序树 - 是每个节点的值大于其每个子节点的所有值的树.(有时您会看到此属性要求每个节点的值都小于其子节点的所有值;这基本上是相同的).但是,对于部分排序的树中的每个节点可以拥有多少个子项没有限制 - 部分排序的属性表示值可以去的位置,而不是树的形状.例如,以下是一些部分排序的树:

          4            9             3
         /|\          / \             \
        3 2 1        4   5             2
       / \          /|\   \             \
      0   2        3 3 3   3             1

这两棵树的前两个是部分有序的树,但不是二叉树,而最后一个是部分有序的树和二叉树.

您询问了在哪里使用了部分排序的树.许多着名和重要的数据结构 - 二进制堆,二项式堆,斐波纳契堆等 - 被实现为部分有序树的集合,其具有额外的结构特性.这些可以用于实现快速优先级队列,这加速了许多着名的算法,如Dijkstra的算法,用于查找最短路径,Prim的算法,用于查找最小生成树.

请记住,部分有序的树是不一样的二叉搜索树.在您的原始问题中,您展示了通过将一系列值插入空二进制搜索树而形成的树的示例.虽然这是正确的,但它完全独立于部分有序的树.

希望这可以帮助!