印刷 B+ C语言中的树

Question

我已经在 C 中实现了 B+ 树，并希望以树形式打印其键。我遵循以下算法来打印它，但出现了一些分段错误。

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

此代码打印根的键值和根的第一个连续节点，然后获取分段错误。您能帮我找出这段代码有什么问题吗？

Answer 1

我还没有检查完整的代码，但是这些部分真的很奇怪：

bplusTemp->bplusNode = bplusNode;

bplusNode 这里是什么？没看到它的声明。

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

这简直就是胡说八道:)

Answer 2

层序遍历是通过两个队列完成的，一个用于访问当前层中的元素，另一个用于构建下一层的队列。我已经成功地为二叉搜索树实现了这一点。您可以对 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;
}

沙什

Answer 3

这行代码在您的 bplus_Enqueue 函数中看起来很奇怪：

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

基本上您是在用于队列的链表中设置下一个节点，但在分配 next< 后释放它/code> 指向链表前一个末尾的指针。这意味着倒数第二个节点指向已释放的内存而不是有效的链表节点，这将在访问时导致分段错误。在第一行之后，bplusTemp 节点指向的内存现在由列表“拥有”...您无法对该指针调用 free，或者否则，指向该内存的每个其他指针（在本例中为queue->next）也指向已释放的内存，并且在尝试访问该内存时将出现段错误。

这也解释了为什么您能够打印前两个节点值（根节点及其子节点之一），然后出现段错误。基本上，当队列为空时，您永远不会调用这些行，并且您要添加第一个节点。因此，当您添加 root 时，就可以了...您无需对其调用 free 。然后将其出队，当您这样做时，队列再次为空。因此，root 的下一个子级被添加到队列中，这也很好，因为因为队列是空的，所以您不会在 bplusNew< 上调用 free /代码>。但是现在，当您添加根的任何其他子级并且队列不为空时，您最终会在 bplusNew 上调用 free，导致队列仅包含单个值价值。换句话说，queue->next 指向的第一个节点（即链表中的第二个节点）实际上不再可访问......您已调用 free 在那段记忆上。

其次，在您的 bplus_Dequeue 函数中，您有内存泄漏......特别是在这里：

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

您正在重新分配链表的前面，而没有释放作为列表原始头的节点。现在您不再有指向该节点的指针，并且它被视为泄漏内存。