均勻遞歸樹的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-ary樹開始的，你所要做的就是弄清楚如何將一個節點作爲一個子節點添加到樹中的一個現有節點上。

對於k節點，一個新節點k + 1樹可以成爲先前k節點中的任何一個的兒童（即，任何在該組{1, 2, ..., k}節點）。

你所需要的是，當前存在於樹中的所有節點的列表。我會保持這是Tree數據結構中的一個單獨的內部結構。然後你將不得不弄清楚如何選擇樹的其中一個節點。這是通過概率函數完成的。我覺得這部分有點不清楚，主要是因爲我已經忘記了很多可能的東西（並且我討厭學校的可能性）。但本文確實解釋瞭如何計算概率。基本上你有一系列概率質量函數。所以如果你有一個節點1，然後節點2，節點2將被連接到節點1（因爲只有一個節點連接到2）。節點3將以概率p(2, 1)附加到節點1或節點2，概率爲p(2, 2)。你有什麼要確保雖然是：

p(k, i) >= 0 

和：

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

一個天真的實現是簡單地選擇其中一個節點隨機從現有的節點列表中。