Извлеките root из максимальной кучи - PullRequest
Новая
       56

Извлеките root из максимальной кучи

0 голосов
/ 21 марта 2020

Я изо всех сил пытаюсь написать рекурсивный алгоритм для извлечения максимального (root) из максимальной кучи. Куча построена как дерево. Я знаю, что я должен поменять последний узел с root и рекурсивно убрать его sh. Но в inte rnet или переполнении стека нет псевдокода для работы с деревьями. Алгоритмы извлечения, которые я видел, основаны на массивах.

Итак, допустим, я нашел самый правый лист.

Есть ли какое-нибудь решение, которое вы можете предложить? 

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

1 Ответ

0 голосов
/ 23 марта 2020

Для эффективного поиска последнего узла в куче, реализованной в виде дерева, необходимо поддерживать количество узлов. То есть вы знаете, сколько элементов в куче.

Если вы знаете, сколько элементов в куче, то вы получаете двоичное представление числа и используете его для отслеживания через дерево до последнего узел. Позвольте привести пример. У вас есть эта куча: 

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

В куче 6 предметов. Двоичное представление: 110.

Теперь, перемещаясь справа налево в двоичном представлении. Вы удаляете первую '1' и вы находитесь на узле root. Правило состоит в том, что вы go вправо, если di git равно '1', и налево, если di git равно '0' В узле root у вас есть 10. Итак, вы go правы и удалите эту ди git, оставив вам 0. Вы находитесь на узле с отметкой «3». Оставшийся ди git равен 0, поэтому вы go ушли. Это помещает вас в последний узел в куче.

Алгоритм отсеивания кучи одинаков, независимо от того, представлена ​​ли куча в виде массива или дерева. Конечно, фактические шаги, которые вы предпринимаете, чтобы поменять узлы, отличаются. При замене узлов вы должны быть осторожны, чтобы правильно установить дочерние указатели. Люди часто забывают о том, что при обмене узлом root с последним узлом.

Мое предложение заключается в том, чтобы вы кодировали это, а затем пошагово выполняли отладчик, чтобы убедиться в правильности назначения указателей. .

...