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

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

或许真的喜欢这个 ？

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); 
} 

类似的东西。

Answer 3

将某些东西添加到堆结构的常规方法是从根处开始并“漫游”树以找到新元素所在的位置。当你找到它的位置时，你把它放在那里，如果这意味着替换那个地方已经存在的东西，那么你采取以前的价值，并继续走下去找到它去的地方。重复，直到你点击一片叶子，然后添加你“携带”的任何价值作为该叶子的适当孩子。

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

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