有序和无序(有根)树之间的差异

Question

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

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

根树(或无序树)是连接到多个有根树的节点(称为根).(这种多重集合称为无序森林.

我对上述文字的疑问是

1. 我在理解上述定义方面有困难.任何人都可以用例子来解释.
2. 作者对不相交的树的意思是什么？
3. 作者对多重植根树的意思是什么？

谢谢你的时间和帮助

Answer 1

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

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

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