c++ - 我应该如何处理在 C++ 中可视化 B+ 树的任务？

Question

我和我的 friend 们必须为我们的数据库类(class)实现一个简单的 DBMS。

DBMS 的主要部分已准备就绪，这意味着所有命令(插入、删除、更新、选择)都已经过全面测试，似乎工作得很好。

现在对于最后一个特性，我们必须实现 B+ 树，老实说这非常困难。

我们尝试做的是首先实现一个简单的 B+ 树，它可以在主内存中工作(在实现基于文件的版本之前)。在网上阅读了 B+ 理论并研究了各种伪代码后，我们设法创建了一个递归实现，我使用 VS2010 的调试器对其进行了测试，它似乎工作得很好。

问题是，我想稍微形象化创建的树，因为我相信这将使我们的调试工作更轻松。我的意思是，如果您能看到树的实际情况，那么您就可以确定结果是否正确。

所以，让我们以最简单的情况为例。假设 B+ 树的节点上有 2 个整数作为数据和三个指向子节点的指针。

让我们插入数字 40,50,48,20,57,49。来自以下网站:http://www.seanster.com/BplusTree/BplusTree.html

我们得到以下动画:

我添加了箭头。

现在我想用 C++ 按以下方式打印这棵树:

          [48|50]
  [20|40] [48|49] [50|57]

但是我不确定我应该怎么做。我已经阅读了有关树遍历的信息，例如前序、后序、中序，但我认为它们不会帮助我实现我想要的。

我所知道的只是根节点。从该根节点开始，我必须按以下方式遍历树:

1. 访问根目录
2. 打印根
3. 访问根的 child
4. 打印每个 child 的值
5. 对于根的每个 child ，访问它的 child (即根的孙子)。
6. 打印孙子的值(value)观
7. 对其他孙子做同样的事情
8. 以同样的方式为孙子等的 child 做同样的事情

解决此问题的最佳方法是什么？提前致谢

Answer 1

扩展我对级别顺序遍历的评论 - 如果我正确理解您的问题，这样的事情应该有效吗？嗯，它实际上不会工作，因为 myNode 和诸如此类的东西没有定义，但希望它能展示这个想法。

std::vector<std::vector<std::string> > reprVect;

void visit(myNode n) { 
    if (reprVect.size() < myNode.level)
        reprVect.push_back(std::vector<std::string>());
    }
    reprVect[myNode.level].push_back(myNode.string_repr());
}

// [...]

std::queue<myNode> q;
q.push_back(rootNode);
while (!q.empty()) {
    myNode curNode = q.front();
    q.pop_front();
    visit(q);
    if (curNode.left != NULL) {
        q.push_back(curNode.left);
    } else { /*insert blank into the reprVect */ }
    if (curNode.right != NULL) {
        q.push_back(curNode.right);
    } else { /*insert blank into the reprVect */ }
}

// use cout to print contents of reprVect