本文介紹了從二叉樹中隨機選擇節點的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！
問題描述
我的樹類：
public class BT<E>{
E value;
BT<E> left, right;
public BT(E value)
{
this.value=value;
}
public BT (E value, BT left, BT right)
{
this.value = value;
this.left = left;
this.right = right;
}
在生成樹之后，我將如何從樹返回隨機節點？我知道我生成的每個樹的深度和節點數。
推薦答案
丹尼斯和杰倫的算法很容易實現，但是O(n)。我相信我的O(log n)算法稍微復雜一些。
每個節點都需要平等的被選中機會。因此，在某些樹T中，設LN(T)為左樹中的節點數，RN(T)為右樹中的節點數，N(T)為總節點數，包括此節點(因此N(T) = 1 + LN(T) + RN(T))。從0 to N(T) - 1中選擇一個隨機數R。如果R == 0，則返回此節點。如果1 <= R <= LT(N)，則在左子樹上遞歸此方法。否則，在右子樹上遞歸此方法。
未經測試的代碼(假設BT有一個.size()方法可以在O(1)中使用)：
public BT randomNode() {
int r = new Random().nextInt(this.size());
if (r == 0) {
return this;
} else if (left != null && 1 <= r && r <= left.size()) {
return left.randomNode();
} else {
return right.randomNode();
}
}
當然，您也可以將new Random()從方法中提升出來，但算法是相同的。
編輯：修復了左子樹為空時出現空指針異常的問題。
這篇關于從二叉樹中隨機選擇節點的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
