algorithm - 在二叉树上实现随机过程

Question

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

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

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

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

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

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

Answer 1

你可以构建一个Heap，并将它的所有元素初始化为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)