Печать B + дерево в C

Question

Я реализовал B+ дерево в C и хочу напечатать его ключи в виде дерева.Я использовал следующие алгоритмы для его печати, но получил ошибку сегментации.

1. Начиная с root, прежде всего поставив его в очередь.Затем убираем в очередь, пока очередь не станет равной нулю.

2. Поскольку каждый узел содержит оба ключа и их значения (указатели на узлы следующего уровня), каждое из этих значений также ставится в очередь при достижении определенного узла.

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

           typedef struct QUEUE{
            BPLUS bplusNode;
            struct QUEUE * next;
                    }*ENQUEUE;

Следующий код предназначен для постановки в очередь узлов дерева. (Я собираюсь реализовать поиск по ширине)

      void bplus_Enqueue(BPLUS bplusNew){
          ENQUEUE bplusTemp;
          if (queue == NULL){
          queue = (ENQUEUE)malloc(sizeof(ENQUEUE));
          queue->bplusNode= bplusNew;
          queue->next = NULL;
              }
               else {
               bplusTemp = (ENQUEUE)malloc(sizeof(ENQUEUE));
               bplusTemp->bplusNode = bplusNew;
               bplusTemp->next = NULL;
        while(queue->next != NULL) {
                queue = queue->next;
                      }
                queue->next = bplusTemp;
                free(bplusTemp);
                   }
             }

Следующий код предназначен для снятия с очереди

          BPLUS bplus_Dequeue( void ){
          BPLUS bplusTemp = queue->bplusNode;
          queue = queue->next;
          return bplusTemp;
           }

Следующий код предназначен для печати дерева.

   void  bplus_PrintBplus(BPLUS root){
   int i;
   BPLUS tempBplus;
   queue = NULL;
   bplus_Enqueue(root);
   if(queue == NULL){
     printf("Sala kaam garena\n");
    }
   while(queue != NULL){
   tempBplus = bplus_Dequeue();
          for(i=0;i<tempBplus->numKeys;i++){
          printf("%d -----> %d\n",i,tempBplus->keys[i]);
             }
          if(tempBplus->next != NULL){
             for(i=0;i<=tempBplus->numKeys;i++)
           bplus_Enqueue(tempBplus->pointers[i]);
            }
        }
    }

Этот код печатает значение ключа root и первый последующий узел root, а затем получает ошибку сегментации.Не могли бы вы помочь мне выяснить, что не так с этим кодом?

Answer 1

Уровень обхода порядка осуществляется через две очереди, одна для доступа к элементам текущего уровня, а другая для построения очереди для следующего уровня.Я успешно реализовал это для бинарного дерева поиска.Вы можете использовать ту же логику для деревьев B +.

void BinarySearchTree::printLevelBased()
{
    Queue<Node *> *nodeQueue1 = new Queue<Node *>();
    Queue<Node *> *nodeQueue2 = new Queue<Node *>();;
    Node *currentNode;
    int numOfLevels = 0;

    nodeQueue1->put(mRoot);

    while(false == nodeQueue1->isEmpty())
    {
        numOfLevels++;
        Queue<Node *> *temp = nodeQueue1;
        nodeQueue1 = nodeQueue2;
        nodeQueue2 = temp;

        while(false == nodeQueue2->isEmpty())
        {
            currentNode = nodeQueue2->get(); // Dequeue
            PRINT_NODE_DATA(currentNode);
            if(currentNode->hasLeft())
            {
                nodeQueue1->put(currentNode->mLeft); // Enqueue
            }
            if(currentNode->hasRight())
            {
                nodeQueue1->put(currentNode->mRight);
            }
        }
        cout << endl;
    }

    return;
}

Shash

Answer 2

Эта строка кода выглядит странно в вашей bplus_Enqueue функции:

queue->next = bplusTemp;
free(bplusTemp);

в основном вы устанавливаете следующий узел в связанном списке, который вы используете для своей очереди, но затем освобождаете его после назначения указателя next на предыдущий конец связанного списка. Это будет означать, что ваш предпоследний узел указывает на освобожденную память, а не на действительный узел связанного списка, что вызовет ошибку сегментации при обращении к нему. Память, на которую указывает узел bplusTemp, после первой строки теперь "принадлежит" списку ... вы не можете вызвать free для этого указателя или для любого другого указателя, который указывает на эту память ( в этом случае queue->next) также указывает на свободную память и при попытке доступа к этой памяти произойдет сбой.

Это также имеет смысл в том, почему вы можете напечатать первые два значения узла (корень и одно из его дочерних элементов), а затем получить ошибку сегмента. По сути, вы никогда не вызываете эти строки, когда очередь пуста, и вы добавляете первый узел. Поэтому, когда вы добавляете root, все в порядке ... вы не звоните free. Затем вы удаляете его из очереди, и когда вы делаете это, очередь снова пуста. Таким образом, следующий дочерний элемент root добавляется в очередь, и это снова хорошо, поскольку, поскольку очередь пуста, вы не будете вызывать free на bplusNew. Но теперь, когда вы добавляете любые другие дочерние элементы корня, и очередь не пуста, вы в конечном итоге вызываете free для bplusNew, в результате чего ваша очередь содержит только одно значение. Другими словами, первый узел, на который указывает queue->next (т. Е. Второй узел в связанном списке), фактически больше недоступен ... вы вызвали free в этой памяти.

Во-вторых, в вашей функции bplus_Dequeue есть утечка памяти ... в частности, здесь:

BPLUS bplusTemp = queue->bplusNode;
queue = queue->next;

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

Answer 3

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

bplusTemp->bplusNode = bplusNode;

Что здесь за bplusNode? Не видел его декларации.

queue->next = bplusTemp;
free(bplusTemp);

это просто орешки :)