我和我的 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]
但是我不确定我应该怎么做。我已经阅读了有关树遍历的信息,例如前序、后序、中序,但我认为它们不会帮助我实现我想要的。
我所知道的只是根节点。从该根节点开始,我必须按以下方式遍历树:
- 访问根目录
- 打印根
- 访问根的 child
- 打印每个 child 的值
- 对于根的每个 child ,访问它的 child (即根的孙子)。
- 打印孙子的值(value)观
- 对其他孙子做同样的事情
- 以同样的方式为孙子等的 child 做同样的事情
解决此问题的最佳方法是什么?提前致谢
最佳答案
扩展我对级别顺序遍历的评论 - 如果我正确理解您的问题,这样的事情应该有效吗?嗯,它实际上不会工作,因为 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
关于c++ - 我应该如何处理在 C++ 中可视化 B+ 树的任务?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12040144/