1

我和我的朋友必须为我们的数据库类实现一个简单的 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]

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

我所知道的只是根节点。从那个根节点开始，我必须通过以下方式遍历树：

  1. 访问根
  2. 打印根
  3. 拜访根的孩子
  4. 打印每个孩子的价值观
  5. 对于根的每个孩子，访问它的孩子（这是根的孙子）。
  6. 打印孙子的价值观
  7. 为其他孙子做同样的事情
  8. 以同样的方式为孙子的孩子做同样的事情等

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

4

1 回答 1

0

扩展我对级别顺序遍历的评论-如果我理解您的要求正确，这样的事情应该可以工作？好吧，它实际上不会起作用，因为 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
于 2012-08-20T15:23:42.633 回答