实施二叉树一个随机过程

考虑与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

实施二叉树一个随机过程

回答

相关问题