algorithm - 有序和无序(有根)树之间的区别

Question

我正在阅读 Robert Sedwick 的算法。书中的一些定义如下所示。

A tree (also an ordered tree) is a node (called the root) connected to a sequence of disjoint trees. Such a sequence is called a forest.

A rooted tree (or unordered tree) is a node (called the root) connected to a multiset of rooted trees. (such a multiset is called an unordered forest.

我对以上文字的问题是

1. 我很难理解上述定义。谁能举例说明一下。
2. 作者所说的不相交树是什么意思？
3. 作者所说的多重集根树是什么意思？

感谢您的时间和帮助

Answer 1

1. 根据此定义，树或多或少就是我们通常对树的理解:连接到有序(子)树序列的节点。这是一个递归定义:如果序列为空，则该节点称为叶，如果不是，则序列中的每棵树也是“连接到(子)树的有序序列的节点” ”
2. 作者所说的不相交意味着子树没有共同的节点。
3. 定义意味着根树的子树没有特定的顺序，它们可以重复。 multiset有点像一个允许倍数的集合。

有序树(第一个定义的“树”)具有特定顺序的子树，并且子树序列不能包含同一棵树两次，因为子树必须是不相交的。有根树没有这些限制；根据这个定义，一个根可能有两次子树，其结构类似于一个循环。

我没有 Sedwick 的书来检查这个定义是否有意义或为什么有意义；更常见的定义或有根树将使用普通集作为子树，而不是多重集。可能的目的是允许节点与其子节点之间存在多个链接，同时不允许其他类型的循环，例如 sibling 和表亲之间的链接。