實施二叉樹一個隨機過程

考慮與N = 2^h的完整二進制樹該隨機過程 - 1個節點實施二叉樹一個隨機過程

假設我有N = 2^H-1個節點的二進制樹中，最初所有節點都未標記隨着時間的推移，通過此過程節點被標記。假設節點每次有[1，N]範圍內的唯一標識符，我向你發送一個節點的標識符。當你收到一個發送的節點。您將其標記並調用以下標記規則，該規則在發送下一個節點之前生效。

如果節點及其兄弟標記被標記，則其父標記被標記。如果一個節點及其父節點被標記，另一個兄弟節點被標記。標記規則在發送下一個節點之前儘可能遞歸地應用。

我需要實現這一進程，並運行它用於h十倍範圍[10，20]，看看有多少次我應該向完全標記的所有節點的節點...

我的問題是：什麼是最好的方式來表示這個問題的二叉樹？ 我腦海裏想的是把它當作一堆，並使用int nodes[1 << h]的數組，並做標記規則，或者我使用基於指針的結構像BST？

另一件我很難理解的事情是，我應該如何實現上述的標記規則？（你也應該注意，這個規則必須儘可能多地使用）我的意思是以一個節點作爲參數的函數和...

來源

2015-01-14 Rachmaninoff

你可以構建一個堆並將它的所有元素初始化爲0標記可以通過將鍵設置爲1.然後您可以使用以下程序：

MARK(A, i) 
l = LEFT(i) 
r = RIGHT(i) 
p = PARENT(i) 
if(i <= A.heap-size and A[i] == 0) 
    A[i] = 1 
    if(l <= A.heap-size and r <= A.heap-size) 
     if(A[l] == 1) 
      if(A[r] == 0) 
       MARK(A, r) 
     else if(A[r] == 1) 
      MARK(A, l) 
    if(p != NIL) 
     CHECK(A, p) 

CHECK(A, i) 
l = LEFT(i) 
r = RIGHT(i) 
if(l <= A.heap-size and A[l] == 1 and r <= A.heap-size and A[r] == 1) 
    MARK(A, i)

來源

2015-01-14 08:11:37

實施二叉樹一個隨機過程

回答

相關問題