想要打印出一个“漂亮”btree

Question

截至目前，这个程序遍历级别的顺序，但只是打印出数字。我想知道如何打印它，所以它可能看起来像下面的图片或只是一个幻想显示树的不同层次及其数量的方法。

 num1 
    / \ 
num2,num3 num4,num5 

我不事情明白的是如何分辨哪些数字是假设进入有各自level.Here是代码：

// C++ program for B-Tree insertion 
#include<iostream> 
#include <queue> 
using namespace std; 
int ComparisonCount = 0; 
// A BTree node 
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 
    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) 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); 
}; 

// Constructor for BTreeNode class 
BTreeNode::BTreeNode(int t1, bool leaf1) 
{ 
    // Copy the given minimum degree and leaf property 
    t = t1; 
    leaf = leaf1; 

    // Allocate memory for maximum number of possible keys 
    // and child pointers 
    keys = new int[2 * t - 1]; 
    C = new BTreeNode *[2 * t]; 

    // Initialize the number of keys as 0 
    n = 0; 
} 

// Function to traverse all nodes in a subtree rooted with this node 
/*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) 
{ 
ComparisonCount++; 
C[i]->traverse(); 
} 
cout << " " << keys[i]; 
} 

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

// Function to search key k in subtree rooted with this node 
BTreeNode *BTreeNode::search(int k) 
{ 
    // Find the first key greater than or equal to k 
    int i = 0; 
    while (i < n && k > keys[i]) 
     i++; 

    // If the found key is equal to k, return this node 
    if (keys[i] == k) 
    { 
     ComparisonCount++; 
     return this; 
    } 
    // If key is not found here and this is a leaf node 
    if (leaf == true) 
    { 
     ComparisonCount++; 
     return NULL; 
    } 

    // Go to the appropriate child 
    return C[i]->search(k); 
} 

// The main function that inserts a new key in this B-Tree 
void BTree::insert(int k) 
{ 
    // If tree is empty 
    if (root == NULL) 
    { 
     ComparisonCount++; 
     // Allocate memory for root 
     root = new BTreeNode(t, true); 
     root->keys[0] = k; // Insert key 
     root->n = 1; // Update number of keys in root 
    } 
    else // If tree is not empty 
    { 
     // If root is full, then tree grows in height 
     if (root->n == 2 * t - 1) 
     { 
      ComparisonCount++; 
      // Allocate memory for new root 
      BTreeNode *s = new BTreeNode(t, false); 

      // Make old root as child of new root 
      s->C[0] = root; 

      // Split the old root and move 1 key to the new root 
      s->splitChild(0, root); 

      // New root has two children now. Decide which of the 
      // two children is going to have new key 
      int i = 0; 
      if (s->keys[0] < k) 
      { 
       ComparisonCount++; 
       i++; 
      }s->C[i]->insertNonFull(k); 

      // Change root 
      root = s; 
     } 
     else // If root is not full, call insertNonFull for root 
      root->insertNonFull(k); 
    } 
} 

// A utility function to insert a new key in this node 
// The assumption is, the node must be non-full when this 
// function is called 
void BTreeNode::insertNonFull(int k) 
{ 
    // Initialize index as index of rightmost element 
    int i = n - 1; 

    // If this is a leaf node 
    if (leaf == true) 
    { 
     ComparisonCount++; 
     // The following loop does two things 
     // a) Finds the location of new key to be inserted 
     // b) Moves all greater keys to one place ahead 
     while (i >= 0 && keys[i] > k) 
     { 
      keys[i + 1] = keys[i]; 
      i--; 
     } 

     // Insert the new key at found location 
     keys[i + 1] = k; 
     n = n + 1; 
    } 
    else // If this node is not leaf 
    { 
     // Find the child which is going to have the new key 
     while (i >= 0 && keys[i] > k) 
      i--; 

     // See if the found child is full 
     if (C[i + 1]->n == 2 * t - 1) 
     { 
      ComparisonCount++; 
      // If the child is full, then split it 
      splitChild(i + 1, C[i + 1]); 

      // After split, the middle key of C[i] goes up and 
      // C[i] is splitted into two. See which of the two 
      // is going to have the new key 
      if (keys[i + 1] < k) 
       i++; 
     } 
     C[i + 1]->insertNonFull(k); 
    } 
} 

// A utility function to split the child y of this node 
// Note that y must be full when this function is called 
void BTreeNode::splitChild(int i, BTreeNode *y) 
{ 
    // Create a new node which is going to store (t-1) keys 
    // of y 
    BTreeNode *z = new BTreeNode(y->t, y->leaf); 
    z->n = t - 1; 

    // Copy the last (t-1) keys of y to z 
    for (int j = 0; j < t - 1; j++) 
     z->keys[j] = y->keys[j + t]; 

    // Copy the last t children of y to z 
    if (y->leaf == false) 
    { 
     ComparisonCount++; 
     for (int j = 0; j < t; j++) 
      z->C[j] = y->C[j + t]; 
    } 

    // Reduce the number of keys in y 
    y->n = t - 1; 

    // Since this node is going to have a new child, 
    // create space of new child 
    for (int j = n; j >= i + 1; j--) 
     C[j + 1] = C[j]; 

    // Link the new child to this node 
    C[i + 1] = z; 

    // A key of y will move to this node. Find location of 
    // new key and move all greater keys one space ahead 
    for (int j = n - 1; j >= i; j--) 
     keys[j + 1] = keys[j]; 

    // Copy the middle key of y to this node 
    keys[i] = y->keys[t - 1]; 

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

// Driver program to test above functions 
int main() 
{ 
    BTree t(4); // A B-Tree with minium degree 4 
    srand(29324); 
    for (int i = 0; i<10; i++) 
    { 
     int p = rand() % 10000; 
     t.insert(p); 
    } 

    cout << "Traversal of the constucted tree is "<<endl; 
    t.traverse(); 

    int k = 6; 
    (t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present" << endl; 

    k = 28; 
    (t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present" << endl; 

    cout << "There are " << ComparisonCount << " comparisons." << endl; 
    system("pause"); 
    return 0; 
} 

Answer 1

首先，Janus Troelsen's answer的话题Is there a way to draw B-Trees on Graphviz?显示了通过在互联网上粘贴东西进入他所链接的网络界面，或者使用本地副本GraphViz来创建维基百科中使用的专业B树图纸。所需文本文件的格式非常简单并且易于使用B树的标准遍历来生成。帕特里克·克罗伊茨把所有的东西汇集在一起​​，标题为How to draw a B-Tree using Dot。

但是，为了调试和研究正在开发的B树实现，可以非常有用地将B树作为文本进行渲染。在下文中，我会给出一个简单的C++类，可以绘制子女上述中心这样的节点：

## inserting 42... 

     [56 64 86] 

[37 42] [62] [68 72] [95 98] 

## inserting 96... 

       [64] 

    [56]   [86] 

[37 42] [62] [68 72] [95 96 98] 

这是从B树代码的实际输出取入的previous topic，在改变模量后rand()调用100以获得更小的数字（比节点更长的数字更容易看到）和构造一个带有t = 2的B树。

这里的基本问题是，在遍历子树期间，只有在节点居中所需的信息（最左侧的孙子的起始位置和最右侧的孙子的结束位置）变得可用。因此，我选择了完全遍历树并存储打印所需的所有内容的方法：节点文本和最小/最大位置信息。

这里是类的声明，有一点乏味的东西，内联把它弄出来的方式：

class BTreePrinter 
{ 
    struct NodeInfo 
    { 
     std::string text; 
     unsigned text_pos, text_end; // half-open range 
    }; 

    typedef std::vector<NodeInfo> LevelInfo; 

    std::vector<LevelInfo> levels; 

    std::string node_text (int const keys[], unsigned key_count); 

    void before_traversal() 
    { 
     levels.resize(0); 
     levels.reserve(10); // far beyond anything that could usefully be printed 
    } 

    void visit (BTreeNode const *node, unsigned level = 0, unsigned child_index = 0); 

    void after_traversal(); 

public: 
    void print (BTree const &tree) 
    { 
     before_traversal(); 
     visit(tree.root); 
     after_traversal(); 
    } 
}; 

这个类必须的BTreeNode和BTree一个朋友为了得到它需要的特权访问。许多生产质量的噪音被忽略了，为了使这个展览变得紧凑和简单，从删除所有assert()呼叫，我的手指自动插入同时编写类...

这是第一个有趣的位，通过树的完整遍历所有节点文本的收集和定位信息：

void BTreePrinter::visit (BTreeNode const *node, unsigned level, unsigned child_index) 
{ 
    if (level >= levels.size()) 
     levels.resize(level + 1); 

    LevelInfo &level_info = levels[level]; 
    NodeInfo info; 

    info.text_pos = 0; 
    if (!level_info.empty()) // one blank between nodes, one extra blank if left-most child 
     info.text_pos = level_info.back().text_end + (child_index == 0 ? 2 : 1); 

    info.text = node_text(node->keys, unsigned(node->n)); 

    if (node->leaf) 
    { 
     info.text_end = info.text_pos + unsigned(info.text.length()); 
    } 
    else // non-leaf -> do all children so that .text_end for the right-most child becomes known 
    { 
     for (unsigned i = 0, e = unsigned(node->n); i <= e; ++i) // one more pointer than there are keys 
     visit(node->C[i], level + 1, i); 

     info.text_end = levels[level + 1].back().text_end; 
    } 

    levels[level].push_back(info); 
} 

关于布局逻辑最相关的事实是，给定的节点拥有（套），水平方向的所有空间自己及其后代所覆盖;一个节点的范围的开始是其左边邻居的范围的末端加上一个或两个空白，取决于左边的邻居是兄弟姐妹还是仅仅是表亲。在遍历整个子树之后，节点范围的末尾才变得已知，此时可以通过查看最右侧子节点的末尾来查看节点的范围。

将节点转储为文本的代码通常可以在BTreeNode类的轨道中找到;对于这个职位，我已经把它添加到打印机类：

std::string BTreePrinter::node_text (int const keys[], unsigned key_count) 
{ 
    std::ostringstream os; 
    char const *sep = ""; 

    os << "["; 
    for (unsigned i = 0; i < key_count; ++i, sep = " ") 
     os << sep << keys[i]; 
    os << "]"; 

    return os.str(); 
} 

这里有一个需要的地方塞进一个小帮手：

void print_blanks (unsigned n) 
{ 
    while (n--) 
     std::cout << ' '; 
} 

这里是打印所有，这是信息的逻辑树的遍历全过程中收集：

void BTreePrinter::after_traversal() 
{ 
    for (std::size_t l = 0, level_count = levels.size(); ;) 
    {  
     auto const &level = levels[l]; 
     unsigned prev_end = 0; 

     for (auto const &node: level) 
     {   
     unsigned total = node.text_end - node.text_pos; 
     unsigned slack = total - unsigned(node.text.length()); 
     unsigned blanks_before = node.text_pos - prev_end; 

     print_blanks(blanks_before + slack/2); 
     std::cout << node.text; 

     if (&node == &level.back()) 
      break; 

     print_blanks(slack - slack/2); 

     prev_end += blanks_before + total; 
     } 

     if (++l == level_count) 
     break; 

     std::cout << "\n\n"; 
    } 

    std::cout << "\n"; 
} 

最后，原来的B树码的版本，使用这个类：

BTreePrinter printer; 
BTree t(2); 

srand(29324); 

for (unsigned i = 0; i < 15; ++i) 
{ 
    int p = rand() % 100; 
    std::cout << "\n## inserting " << p << "...\n\n"; 
    t.insert(p); 
    printer.print(t); 
}