Обход порядка порядка B-дерева

Question

Я пишу симулятор B-дерева. Я читал здесь stackoverflow, что лучший способ - использовать очередь, чтобы пройти обход уровня. Но я понятия не имею, как это сделать. Я работаю над реализацией в C++ от geeksforgeeks. Возможно, кто-то знает, как перестроить обход порядка (код ниже) для обхода порядка порядка.

Классы и constuctors:

class BTreeNode 
{ 
    int *keys; // An array of keys 
    int t;  // Minimum degree (defines the range for number of keys) 
    BTreeNode **C; // An array of child pointers 
    int n;  // Current number of keys 
    int j; 
    bool leaf; // Is true when node is leaf. Otherwise false 
public: 
    BTreeNode(int _t, bool _leaf); // Constructor 

    // A utility function to insert a new key in the subtree rooted with 
    // this node. The assumption is, the node must be non-full when this 
    // function is called 
    void insertNonFull(int k); 

    // A utility function to split the child y of this node. i is index of y in 
    // child array C[]. The Child y must be full when this function is called 
    void splitChild(int i, BTreeNode *y); 

    // A function to traverse all nodes in a subtree rooted with this node 
    void traverse(); 



// A function to search a key in subtree rooted with this node. 
    BTreeNode *search(int k); // returns NULL if k is not present. 

// Make BTree friend of this so that we can access private members of this 
// class in BTree functions 
friend class BTree; 
}; 

// A BTree 
class BTree 
{ 
    BTreeNode *root; // Pointer to root node 
    int t; // Minimum degree 
public: 
    // Constructor (Initializes tree as empty) 
    BTree(int _t) 
    { root = NULL; t = _t; } 

    // function to traverse the tree 
    void traverse() 
    { if (root != NULL) 
    cout << "root"; 
    root->traverse(); } 


    // function to search a key in this tree 
    BTreeNode* search(int k) 
    { return (root == NULL)? NULL : root->search(k); } 

    // The main function that inserts a new key in this B-Tree 
    void insert(int k); 
}; 

Симметричного обхода:

void BTreeNode::traverse() 
{ 
    // There are n keys and n+1 children, travers through n keys 
    // and first n children 

    int i; 

    for (i = 0; i < n; i++) 
    { 
     // If this is not leaf, then before printing key[i], 
     // traverse the subtree rooted with child C[i]. 
     if (leaf == false) 

      C[i]->traverse(); 
     cout << " " << keys[i]; 
    } 


    // Print the subtree rooted with last child 
    if (leaf == false) 
     C[i]->traverse(); 
} 

Answer 1

Здесь вы можете увидеть алгоритм Depth-First-Search (wiki) рекурсивную реализацию.
Для обхода уровня по уровню вам, вероятно, понадобится Breadth-First-Search (wiki).

Для этого мы выполним 2 шага.
Первый шаг: написать рекуррентные свободной ДФС:

void BTreeNode::traverse() 
{ 
    std::stack<BTreeNode*> stack; 
    stack.push(this); 
    while (!stack.empty()) 
    { 
     BTreeNode* current = stack.top(); 
     stack.pop(); 
     int i; 
     for (i = 0; i < n; i++) 
     { 
      if (leaf == false) 
       stack.push(current->C[i]); 
      cout << " " << current->keys[i]; 
     } 
     if (leaf == false) 
      stack.push(current->C[i]); 
    } 
} 

Второй этап: использование очереди вместо стека:

void BTreeNode::traverse() 
{ 
    std::queue<BTreeNode*> queue; 
    queue.push(this); 
    while (!stack.empty()) 
    { 
     BTreeNode* current = queue.front(); 
     queue.pop(); 
     int i; 
     for (i = 0; i < n; i++) 
     { 
      if (leaf == false) 
       stack.push(current->C[i]); 
      cout << " " << current->keys[i]; 
     } 
     if (leaf == false) 
      stack.push(current->C[i]); 
    } 
} 

Итак, это делается!