首页 文章

如何找到树的最后一层（最右边）的最后一个节点（几乎完整的树）？

提问于
浏览 次
0

我试图在堆的最后一级找到最合适的节点（ tree representation ，以便删除最小/最大堆中的特定元素 .

几乎所有网上人都写了用最低级别的堆的最右边节点替换要删除的节点 - 我完全理解但是如何才能找到最后一个节点？

Solution according to me ：我有一个解决方案，即使用级别顺序遍历（广度优先搜索）遍历该树（堆结构），同时存储节点的地址 - 一旦在队列中只剩下一个没有子节点的元素时，我将它用于替换 . 此示例中最右边的节点是 33 ：

enter image description here

有没有其他方法/链接可以使用，因为使用队列似乎相当冗长？

c data-structures queue heap

1 回答

  • 0

    让我们看一个完整的二叉树，忽略存储在节点上的值，但是编号节点as if they were stored in an array，从根开始编号：
    Binary heap tree
    如果我们从根遍历到任何目标节点（根本身除外），左边缘（红色）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

    从根到所需节点的路径与该节点（root为1）的二进制表示相同，忽略最重要的二进制数字！

    因此，在一个完整的树中，为了到达第一个节点，根为1，我们首先找到小于 K 的两个最大幂，并按照下面的二进制数字，按降序遍历，零指示左，一个权利 .

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

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

    然后找到 i th节点， 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) 将返回指向最终节点的指针 .

    如果你想要路径，最低有效位是来自root的第一个边，你可以使用例如

    /* (*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处 . ）

    然后节点没有指针 . 为了支持删除，我们通常将索引存储到节点所在的堆数组中，但是节点只包含数据 . （如果你需要更改键值，或者删除root以外的条目，你通常会添加一个指定当前堆数组索引的数据字段 . 虽然它确实有点慢，所以通常不需要它 . 我会省略它为简单起见 . ）

    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 < n 时，索引为 2*i+1 的左子

    • 正确的孩子在索引 2*i+2 当且仅当 2*i+2 < n

    级别 k 的节点索引是连续的，从 (1 << k) - 1 到 (2 << k) - 2 ，包括（当root具有索引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;
}

    同样，上面示例中的逻辑有效 . 但是，由于示例代码是在没有经过适当审核的情况下编写的，因此可能存在错误 . 因此，如果您对示例代码有任何问题，或者确实存在任何问题回答，请在评论中告诉我，以便我可以根据需要进行检查和修复 .

    回复于

相关问题