查找链接结构堆中的最后一个元素

Question

我想知道如何在堆和根元素的链接结构实现中找到最远的元素。我希望能够对元素进行 Enque 和 Deque。

一些澄清： 我的意思是，假设您有一个构成最大堆的链接结构（根元素具有最大值）。您的树在最底部的某个位置会有一个元素，您可以在该元素之后插入或删除该元素，具体取决于您是入队还是出队。你如何确定该元素？以及如何确定树的根节点？ （最上面那一张）

Answer 1

我并不完全肯定这就是您所要求的，但这是指向单链表的最后一个元素的一种方法：

T *p = NULL, *q = NULL;  // q follows p by one node
p = root;
while (p)
{
    q = p;
    p = p -> next;
}

// q now points to last node

Answer 2

将某些内容添加到堆结构的常规方法是从根开始并“遍历”树以找到新元素所在的位置。当你找到它的去向时，你就把它放在那里，如果这意味着替换该位置已有的内容，那么你就采用以前的值并继续向下查找它的去向。重复直到碰到一片叶子，然后添加您“携带”的任何值作为该叶子的适当子元素。

假设你的新值为 5，堆的根节点保存着 10。5 显然低于 10，所以你查看 10 的子节点。假设它们是 8 和 7。两者都大于 5，所以选择一个 (你如何选择一个取决于你是否试图保持堆平衡）。假设您选择 7，它有子节点 3 和 4。5 低于 7 但高于 3 或 4，因此您将 4 替换为 5，然后查看该节点的子节点以了解将 4 放在哪里。假设没有孩子，你可以添加一个包含 4 的新叶子。

至于你如何找到根的问题——通常根是你保留的指向树的唯一指针。这是您所有操作的起点。如果您从其他地方开始，我想您可以导航到根目录，但我会质疑为什么。

Answer 3

也许是这样的？

struct node {
  node *parent;
  node *children[2];
  int data; //or whatever else you want
};

struct heap {
  node *root;
  node *last;
};

不过，这比仅使用数组来实现要困难得多。这是一个假设的添加

void add(struct heap* h, int d)
{
  node* add = malloc(sizeof(node));
  add->data = d;
  node* current = h->root;
  while(current->children[1]) current = current->children[1];
  current->children[1] = add;
  add.parent = current;
  add.children[0] = NULL;
  add.children[1] = NULL; 
  h.last = add;
  percolate_up(h);
}

类似的东西。