在二叉树上实现随机过程

Question

在 N = 2^h - 1 个节点的完全二叉树上考虑这个随机过程

假设我有一个带有 N=2^h−1 个节点的二叉树，最初所有节点都没有标记随着时间的推移，通过这个过程节点被标记了。假设节点每次都有在[1,N]范围内的唯一标识符，我把一个节点的标识符发给你。当您收到发送的节点时。您标记它并调用以下标记规则，该规则在我发送下一个节点之前生效。

如果标记了节点及其兄弟节点，则标记了其父节点。如果标记了一个节点及其父节点，则标记了另一个兄弟节点。在发送下一个节点之前尽可能递归地应用标记规则。

我需要实施这个过程，运行它在 [10, 20] 范围内对 h 执行十次，并找出我应该发送一个节点多少次才能完全标记所有节点...

我的问题是：表示此问题的二叉树的最佳方法是什么？ 我想到的是将其视为堆并使用 int nodes[1 << h] 数组并执行 标记规则 ，或者我使用基于指针的结构，如 BST ?

另一件我难以理解的事情是，我应该如何实施上面描述的标记规则？（另外你应该注意，这个规则必须尽可能多地应用可能）我的意思是在一个以节点为参数的函数中......

Answer 1

你可以建一个Heap，把它的所有元素都初始化为0。标记可以通过设置keys为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)

在二叉树上实现随机过程

Implementing a random process on binary tree

algorithm

random

tree

binary-tree

implementation