java - 统一递归树Java的实现

Question

我能够找到这么多树的实现，例如，

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html

现在我正在寻找Java中统一递归树的实现。本文解释了统一递归树的细节。 http://www.sciencedirect.com/science/article/pii/S0022247X05004191

在此先感谢您的帮助。

Answer 1

实际上，这并不难实现。您基本上从一棵 n 元树开始，您所要做的就是弄清楚如何将一个节点作为子节点添加到树中的现有节点之一。

对于具有k节点的树，新节点k + 1可以成为任何一个先前k节点（即集合中的任何节点{1, 2, ..., k}）的子节点。

您需要的是当前存在于树中的所有节点的列表。我会认为这是数据结构中的一个单独的内部Tree结构。然后你必须弄清楚如何选择树的节点之一。这是通过概率函数完成的。我发现这部分有点不清楚，这主要是因为我忘记了很多概率知识（而且我在学校讨厌概率）。但是这篇论文确实解释了如何计算概率。本质上，您有一系列概率质量函数。因此，如果您有一个节点1，然后是一个节点2，则节点2将附加到节点1（因为只有一个节点2可以附加）。一个节点3将附加到节点1的概率为p(2, 1)或以2的概率结点p(2, 2)。但是，您必须确保的是：

p(k, i) >= 0

和：

sigma(p(k, i)) from i = 1 to k equals 1

一个简单的实现是简单地从现有节点列表中随机选择一个节点。