c - 如何在树的最后一层(即堆(几乎完整的树))上找到最后一个(最右边的)节点？

Question

我试图在堆的最后一层找到最右边的节点(树表示)，以便删除最小/最大堆中的特定元素。

几乎所有的网上人们都写过用位于最低级别的堆中最右边的节点替换要删除的节点 - 我完全理解这一点，但我如何找到最后一个节点？

根据我的解决方案:我有一个解决方案，即使用级别顺序遍历(广度优先搜索)来遍历该树(堆结构)，同时存储节点的地址 - 一次当有队列中只剩下一个没有子节点的元素，我将使用它进行替换。本例中最右边的节点是 33:

我可以使用其他方法/链接吗，因为使用队列似乎很长？

Answer 1

让我们看一个完全二叉树，忽略节点存储的值，但对节点进行编号 as if they were stored in an array ，从根开始编号: 如果我们从根节点遍历到任何目标节点(除了根节点本身)，左边缘(红色)为 0，右边缘(蓝色)为 1，我们会看到一个模式:

Path     Edges   Target (binary)
─────    ──────  ───────────────
1 → 2    0       1 0
1 → 3    1       1 1
1 → 4    0 0     1 0 0
1 → 5    0 1     1 0 1
1 → 6    1 0     1 1 0
1 → 7    1 1     1 1 1
1 → 8    0 0 0   1 0 0 0
1 → 9    0 0 1   1 0 0 1
1 → 10   0 1 0   1 0 1 0
1 → 11   0 1 1   1 0 1 1
1 → 12   1 0 0   1 1 0 0
1 → 13   1 0 1   1 1 0 1
1 → 14   1 1 0   1 1 1 0
1 → 15   1 1 1   1 1 1 1

从根到所需节点的路径与该节点编号的二进制表示相同(根为1)，忽略最高有效的二进制数字!

因此，在完整的树中，要到达 K第'个节点，根为1，我们首先找到小于K的最大的2的幂，并根据其下面的二进制数字，按降序遍历，0表示左，1表示右。

假设我们的节点结构类似于

typedef  struct node  node;
struct node {
    struct node  *left;
    struct node  *right;
    /* plus node data fields */
};

然后找到i第一个节点，i = 1对于 root，可以实现为

node *ith_node(node *root, const size_t i)
{
    size_t  b = i; 

    /* Sanity check: If no tree, always return NULL. */
    if (!root || i < 1)
        return NULL;

    /* If i is 1, we return the root. */
    if (i == 1)
        return root;

    /* Set b to the value of the most significant binary digit
       set in b. This is a known trick. */
    while (b & (b - 1))
        b &= b - 1;        

    /* We ignore that highest binary digit. */
    b >>= 1;

    /* Walk down the tree as directed by b. */
    while (b) {
        if (i & b) {
            if (root->right)
                root = root->right;
            else
                return NULL; /* Not a complete tree, or outside the tree. */
        } else {
            if (root->left)
                root = root->left;
            else
                return NULL; /* Not a complete tree, or outside the tree. */
        }

        /* Next step. */
        b >>= 1;
    }

    /* This is where we arrived at. */
    return root;
}

在实践中，如果你有一个完全二叉树 N节点，ith_node(root, N)将返回指向最终节点的指针。

如果您想要路径，最低有效位是从根开始的第一个边缘，您可以使用例如

/* (*path) will contain the path to ith node, root being i=1,
   and the return value is the number of steps needed.
   Returns -1 if an error occurs. */
int  path_to_ith(const size_t i, size_t *path)
{
    size_t  b = i;
    size_t  p = 0;
    int     n = 0;

    if (i < 1)
        return -1; /* Invalid i! */

    /* Set b to the value of the most significant binary digit set. */
    while (b & (b - 1))
        b &= b - 1;        

    /* Ignore most significant digit. */
    b >>= 1;

    /* Reverse the rest of the bits in b, into p. */
    while (b) {
        p = (p << 1) + (b & 1);
        b >>= 1;
        n++;
    }

    /* Store path. */
    if (path)
        *path = p;

    /* Return the number of edges (bits) in path. */
    return n;
}

请注意，上面的函数是在树完整的情况下进行的:即，除了最后一层之外的所有级别都已填充，最后一层的所有最左边的节点都已填充。也就是说，如果按照上图编号的节点N被填充，那么节点1到N-1也必须被填充。

上面例子中的逻辑是有效的。然而，由于示例代码是一次性编写的，没有经过适当的审查，因此可能存在错误。因此，如果您对示例代码或本答案中的任何地方有任何问题，请在评论中告诉我，以便我可以根据需要进行检查和修复。

<小时/>

请注意，二进制堆通常使用数组表示。

(为了使用正确的数组索引，我们在这里切换到从零开始的索引；即从此时开始，根位于索引 0 处。)

节点没有指针。为了支持删除，我们通常将索引存储到节点所在的堆数组中，否则节点只有数据。 (如果您需要更改键值，或删除根以外的条目，通常会添加一个指定当前堆数组索引的数据字段。不过，它确实会减慢速度，因此通常不需要。我将省略它为简单起见。)

typedef  double  heap_key;

typedef struct {
    /* Data only! */
} heap_data;

typedef struct {
    heap_key   key;
    heap_data *val;
} reference;

typedef struct {
    size_t     max;  /* Current max heap size, nodes */
    size_t     len;  /* Number of nodes in this heap */
    reference *ref;  /* Array of references to nodes */
} heap;
#define  HEAP_INIT { 0, 0, NULL }

static inline void heap_init(heap *h)
{
    if (h) {
        h->max = 0;
        h->len = 0;
        h->ref = NULL;
    }
}

注意 heap 中的引用数组根据需要动态分配/重新分配，因此堆的大小没有固有的限制(当然，内存除外)。

HEAP_INIT宏允许在声明时初始化堆。换句话说，heap h = HEAP_INIT;相当于 heap h; heap_init(&h); .

向这样的堆中添加新元素非常简单:

static int heap_add(heap *h, heap_data *d, const heap_key k)
{
    size_t  i;

    if (!h)
        return -1; /* No heap specified. */

    /* Ensure there is room for at least one more entry. */
    if (h->len >= h->max) {
        size_t     max;
        reference *ref;

        /* Minimum size is 15 references; then double up
           to 1966080 entries; then set next multiple of
           1024*1024 + 1024*1024-2. */
        if (h->len < 15)
            max = 15;
        else
        if (h->len < 1966080)
            max = 2 * h->len;
        else
            max = (h->len | 1048575) + 1048574;

        ref = realloc(h->ref, max * sizeof h->ref[0]);
        if (!ref)
            return -2; /* Out of memory; cannot add more. */

        h->max = max; 
        h->ref = ref;
    }

    i = h->len++;
    h->ref[i].key = key;
    h->ref[i].val = data;

    /* Omitted:  Percolate 'i' towards root,
                 keeping the heap order property for keys. */

    /* if (!i) "i is root";
       For all other cases, the parent is at index ((i-1)/2), and
       if (i&1) "i is a left child, sibling is (i+1)";
       else     "i is a right child, sibling is (i-1)";
    */

    return 0;
}

在堆数组中，如果有n节点，索引处的节点 i (根索引为 0)有

• 父级索引 (i - 1)/2当且仅当i > 0

• 索引 2*i+1 处的左子元素当且仅当2*i+1 < n

• 索引 2*i+2 处的右子节点当且仅当2*i+2 < n

k级别节点的索引是连续的，从 (1 << k) - 1至(2 << k) - 2 ，包含在内(当根的索引为 0 且级别为 0 时)。

索引为 i 的节点(根具有索引 0 和级别 0)位于级别 k ，是floor(log2(i+1))或者通过例如以下函数获得:

static inline size_t  ith_level(size_t  i)
{
    size_t  n = 0;
    size_t  t = (i + 1) / 2;

    while (t) {
        t >>= 1;
        n++;
    }

    return n;
}

同样，上面示例中的逻辑是有效的。然而，由于示例代码是一次性编写的，没有经过适当的审查，因此可能存在错误。因此，如果您对示例代码或本答案中的任何地方有任何问题，请在评论中告诉我，以便我可以根据需要进行检查和修复。