очередь приоритетов, куда вставить?

Question

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

Вот что у меня есть:

void pq_insert(struct tnode* p)
{
    struct tnode* curr=NULL;
    struct tnode* prev=NULL;
   printf("inserting:%c,%f\n",p->symbol,p->freq);
   if(qhead==NULL) /*qhead is null*/
   {
    qhead = p;
        /*TODO: write code to insert when queue is empty*/
   }
   /*TODO: write code to find correct position to insert*/
    curr = qhead;
    while (curr != NULL){//I think this is wrong
        if ((curr -> left) == NULL){
            curr = curr -> right;
        }
        else{
            curr = curr -> left;
        }   
    }

   if(curr==qhead)
   {
        /*TODO: write code to insert before the current start*/

   }
   else /*insert between prev and next*/
   {
        /*TODO: write code to insert in between*/
   }
}

Answer 1

Я не знаю точно, что вы делаете с этим циклом while.

while (curr != NULL){//I think this is wrong
    if ((curr -> left) == NULL){
        curr = curr -> right; // Why to go right here?!, isn't this an empty node?
    }
    else{
        curr = curr -> left;
    }   
}

Если я ищу ближайший пустой (NULL) левый узел, я сделаю это

while (curr != NULL){
    if ((curr -> left) == NULL){//The left node is NULL. Great, I found empty node.
        curr = NULL;
    }
    else{ //hmmm, left node is not empty. Lets go left for more nodes. 
        curr = curr -> left;
    }   
}

Но вот так поиск будет идти только влево. после некоторых вставок дерево не будет сбалансировано.

Если вы дадите больше подробностей, это будет более понятным.

Answer 2

Да, код, который вы считаете неправильным:

while (curr != NULL){//I think this is wrong
    if ((curr -> left) == NULL){
        curr = curr -> right;
    }
    else{
        curr = curr -> left;
    }   
}

неправильно. Вы перемещаетесь по курсору к некоторой части вашего дерева независимо от вашего текущего узла.

Вы, вероятно, хотите изменить свой внутренний, если что-то вроде:

if (p->freq < curr->freq)