-1

我正在努力编写一个递归算法来从最大堆中提取最大（根）。堆被构造成一棵树。我知道我应该用根交换最后一个节点并递归地向下推它。但是互联网上没有伪代码或堆栈溢出来处理树。我见过的提取算法是基于数组的。

所以假设我找到了最合适的叶子。

您有什么可以建议的解决方案吗？

void find_last(heap_node* root,int level,int* last_level,bool isRight,heap_node** res){

if(root ==  NULL)
    return;

if(isRight && !root->left && !root->right && level > *last_level){
    *res = root;
    *last_level = level;
    return;

}
find_last(root->right,level+1,last_level,true,res);
find_last(root->left,level+1,last_level,false,res);
}

我做了一个这样的函数调用

            heap_node* last = NULL;
            int last_level = -1;
            find_last(root,0,&last_level,false,&last);

那就是寻找最深右节点的代码。它不工作：D

4

1 回答 1

0

有效地找到作为树实现的堆中的最后一个节点需要您维护节点数。也就是说，您知道堆中有多少项。

如果您知道堆中有多少项目，那么您将获得数字的二进制表示并使用它来跟踪树到最后一个节点。让我给你举个例子。你有这个堆：

         1
     /       \
    2         3
  /   \     /   \
 4     5   6

堆中有 6 个项目。二进制表示是110。

现在，在二进制表示中从右向左移动。您删除第一个“1”，您就位于根节点。规则是，如果数字为“1”，则向右走，如果数字为“0”，则向左走。在根节点，您有10. 因此，您向右移动并删除该数字，留下0. 您位于标记为“3”的节点处。剩下的数字是0，所以你向左走。这会将您置于堆中的最后一个节点。

无论堆是表示为数组还是树，用于向下筛选堆的算法都是相同的。当然，交换节点的实际步骤是不同的。交换节点时，必须小心正确设置子指针。人们经常忘记的一个地方是在将根节点与最后一个节点交换时。

我的建议是您编写代码，然后在调试器中单步执行，以确保您的指针分配正确。

于 2020-03-23T19:11:32.907 回答