algorithm - 有序和无序（有根）树之间的区别

Question

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

树（也是有序树）是连接到一系列不相交树的节点（称为根）。这样的序列称为森林。

有根树（或无序树）是连接到多个有根树的节点（称为根）。（这样的多重集称为无序森林。

我对上述文字的问题是

1. 我很难理解上述定义。任何人都可以用例子解释一下。
2. 作者所说的不相交的树是什么意思？
3. 作者所说的多重有根树是什么意思？

感谢您的时间和帮助

Answer 1

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

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

我没有塞德威克的书来检查这个定义是否或为什么有意义；更常见的定义或有根树将为子树使用正常集，而不是多重集。也许目的是允许节点与其子节点之间存在多个链接，同时不允许其他类型的循环，例如兄弟姐妹和堂兄弟之间的链接。