在C中打印B +樹

Question

我已經在C中實現了B+樹，並且想要以樹形式打印它的密鑰。我遵循以下算法打印它，但得到了一些分段錯誤。

1. 從root開始，首先對它進行排隊。然後出隊，直到隊列變爲零。由於每個節點都包含密鑰及其值（指向下一級節點的指針），因此每個節點在到達特定節點時也會排隊等待。

以下是排隊，出隊和打印葉的代碼。請讓我知道這個partmaticcode有什麼問題。

  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密鑰值和根的第一連續節點，然後得到段故障。你能幫我弄清楚這段代碼有什麼問題嗎？

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

詞shash

Answer 3

這行代碼看起來很奇怪你bplus_Enqueue功能：

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

基本上你要設置的下一個節點的鏈表您正在使用您的隊列，但在將next指針指向鏈接列表的上一個末尾之後釋放它。這意味着您的倒數第二個節點指向已釋放的內存而不是有效的鏈接列表節點，這會在訪問它時導致分段錯誤。 bplusTemp節點指向的內存在第一行之後現在由列表「擁有」......您不能在該指針上調用free，否則每隔一個指向該內存的其他指針（在此例中爲queue->next ）也指向釋放內存，並在嘗試訪問該內存時會發生段錯誤。

這對你爲什麼能夠打印前兩個節點值（root和它的一個子節點），然後得到段錯誤也是有意義的。基本上，當隊列爲空時，你永遠不會調用這些行，並且你正在添加第一個節點。所以當你添加root時，你沒關係......你不要打電話給free就可以了。然後您將它出列，當您這樣做時，隊列又是空的。所以root的下一個孩子被添加到隊列中，並且這很好，因爲由於隊列是空的，所以您不要致電bplusNew上的free。但是現在，當您添加根的其他任何子項並且隊列不爲空時，您最終將調用freebplusNew，導致您排隊僅包含一個值。換句話說，queue->next（即，鏈接列表中的第二個節點）指向的第一個節點實際上不再可用了......您已在該內存上調用free。

其次，在你的bplus_Dequeue功能，您有內存泄漏......具體位置：

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

你重新分配鏈表的前方，而不釋放，這是原來的頭節點的名單。現在你再也沒有指向該節點的指針了，它被認爲是泄漏的內存。