c++ - 如何在 C++ 中打印出 BST

Question

我的 C++ 程序创建了一个二叉搜索树。我知道如何打印出预购、后购和有序的值。

但是，我想做一些更困难的事情。我想打印出有人在纸上画树时的样子。它的根在顶部的中心，它的左孩子在它的正下方和左侧，它的右孩子在它的正下方和右侧。其余节点将相应绘制。

我怎样才能做到这一点？

Answer 1

本文包含您需要的代码，似乎：

替代文字 http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

编辑：该网站离线

这是另一个探索其他选择的人。

Answer 2

这是执行此操作的近似伪代码。基本思想是逐层遍历树，将每一层中的所有节点打印在一行上。每个节点之间的间距是其下方节点的两倍。由于这棵树的深度并不完全一致，因此它被人为地用虚拟节点填充以占据不存在节点的空白区域。

measure the depth of the tree, call that D
have two queues, called Q1 and Q2
enque the top node of the tree in Q1
for (i = D; --i>=0; ){
  foreach node in Q1 {

    on first iteration of this inner loop, print 2^i - 1 spaces,
    else print 2^(i+1) - 1 spaces.

    if node == null print blank
    else print node.value

    if node.left exists enque node.left in Q2
    else enque null in Q2

    if node.right exists enque node.right in Q2
    else enque null in Q2
  }
  copy Q2 to Q1
  clear Q2
  print end-of-line
}

打印的每个空格都是一个数字字段的宽度。假设树的深度 D = 4。然后打印如下：

// it looks like this, and the space sequences are
i = 3: -------n 7
i = 2: ---n-------n 3 7
i = 1: -n---n---n---n 1 3 3 3
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1

Answer 3

    void print(node *p,int start)
    {
        start++;
        if (p->right != NULL)
        {
            print(p->right,start);
        }
        for (int i = 0; i <= start; i++)
        {
            cout<<"    ";
        } 
        cout << p->value<<endl;
        if (p->left != NULL)
        {
            print(p->left, start);
        }
    }

Answer 4

一种方法是使用graphviz。具体来说，使用它的“点”程序，但是让输出看起来完全像你描述的那样可能是不可能的。

Answer 5

好吧，在终端中很难......因为它可能不适合。但是有一些绘图库可以为您制作精美的图片。有graphvis是最受欢迎的之一。

编辑：如果您真的只是想打印文本，graphvis 有一种标记语言，用户可以将其传递给 graphvis，从而制作精美的图片。