我应该如何处理在B+中可视化C++树的任务？
我应该如何处理在B+中可视化C++树的任务？
提问于 2012-08-20 15:02:15
我和我的朋友必须在数据库上为我们的类实现一个简单的DBMS。
DBMS的主要部分已经准备好使用，这意味着所有命令(插入、删除、更新、选择)都经过了彻底的测试，并且似乎运行得很好。
现在，对于最后一个特性，我们必须实现一个B+树，这在我看来是非常困难的。
我们试图做的是首先实现一个简单的B+树，它将在主内存中工作(在实现基于文件的版本之前)。在在线阅读了B+理论和各种伪码之后，我们成功地创建了一个递归实现，我使用了VS2010的调试器来测试它，它看起来工作得很好。
问题是，我想在某种程度上可视化创建的树，因为我相信这将使我们的调试更容易。我的意思是，如果你能看到这棵树的真实情况，那么你就可以肯定地知道这个结果是否正确。
所以，让我们以最简单的例子为例。假设B+树的节点上有两个整数作为数据，以及三个指向子节点的指针。
让我们加上数字40,50,48,20,57,49。来自以下网站：http://www.seanster.com/BplusTree/BplusTree.html
我们得到以下动画：
我加了箭头。
现在，我想以以下方式在C++中打印这棵树：
[48|50]
[20|40] [48|49] [50|57]不过，我不知道该怎么做。我读过一些关于树遍历的文章，例如预排序、后期排序、无序排序，但是我不认为它们会帮助我实现我想要的。
我只知道根节点。从该根节点，我必须以以下方式遍历该树：
- 访问根
- 打印根
- 探视根的孩子
- 打印每个孩子的值
- 对于每一个根的孩子，访问它的孩子(这是根的孙子)。
- 打印大孩子的价值观
- 对其他的孩子也是这样
- 以同样的方式对待大孩子等的子女
解决这个问题最好的方法是什么？提前感谢
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-08-20 15:23:42
如果我理解你的要求正确的话，扩展一下我关于水平顺序遍历的评论--类似这样的东西应该会奏效吗？因为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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12040144
复制相关文章
相似问题
腾讯云开发者
