部分排序的树与二叉树相同吗？(Are partially ordered trees the same as binary trees?)

部分排序的树与二叉树相同吗？(Are partially ordered trees the same as binary trees?)

我对部分有序的树是如何工作有点困惑。 它们与二叉树相同吗？ 另外，它最适合用于什么？

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

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

I'm a little confused about how partially ordered trees work. Are they kind of the same way as binary trees? Also, what is it best use for?

For example if I inserted 5,6,4,9,3,1,7 into an empty tree, I would get:

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

最满意答案

二叉树是树的特殊形状 。 具体而言，二叉树就是一棵树，每个节点可以有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寻找最小生成树的算法。

请记住，部分排序的树与二叉搜索树不同。 在你的原始问题中，你展示了一个将通过将一系列值插入空的二叉搜索树形成的树的示例。 虽然这是正确的，但它完全独立于部分有序的树。

希望这可以帮助！

A binary tree is a particular shape of tree. Specifically, a binary tree is a tree where each node can have either 0, 1, or 2 children. Binary trees make no restrictions about what values can be stored in the nodes or how those values relate to one another, so all of the following are valid binary trees:

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

A partially-ordered tree is a tree in which there is a specific set of restrictions on which values can be where in the tree. Specifically, a partially-ordered tree - which, by the way, is often called a heap-ordered tree - is one in which every node's value is greater than all of the values of each of its children. (Sometimes you see this property as requiring that every node's value is less than all of its children's values; that's essentially the same). However, there are no restrictions on how many children each node in a partially-ordered tree can have - the partially-ordered property says where the values can go, but not what the shape of the tree is. For example, here are some partially-ordered trees:

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

The first two of these trees are partially-ordered trees but not binary trees, while the last is both a partially-ordered tree and a binary tree.

You asked about where you'd use a partially-ordered tree. Many famous and important data structures - binary heaps, binomial heaps, Fibonacci heaps, etc. - are implemented as collections of partially-ordered trees with extra structural properties imposed on them. These can be used to implement fast priority queues, which speed up many famous algorithms like Dijkstra's algorithm for finding shortest paths and Prim's algorithm for finding minimum spanning trees.

Keep in mind that partially-ordered trees are not the same as binary search trees. In your original question, you showed an example of the tree that would be formed by inserting a series of values into an empty binary search tree. While that's right, that's entirely independent of the partially-ordered trees.

Hope this helps!