如何在C ++中打印出BST

Question

我的C ++程序创建了一个二进制搜索树。我知道如何在预订，后订单和订购中打印出值。

但是，我想做一些更困难的事情。我想以他们在纸上画树的方式打印出他们的外观。它的根部将在顶部的中心，其左下方是右下方和左侧的左子女，并且在其右下方和右侧的右子。其余的节点将相应地绘制。

我怎样才能做到这一点？

Answer 1

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

Alt Text 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

一种方法是使用GraphViz。具体来说，使用其“点”程序，但是使输出完全符合您描述的状态可能是不可能的。

Answer 4

    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 5

好吧，在终端很难……因为它可能不合适。但是，那里有图形图库可以为您制作漂亮的图片。有Graphvis是最受欢迎的图像之一。

编辑：如果您真的只是要打印文本，则GraphVis具有一种标记语言，用户可以将其传递给GraphVis，从而使图片构成不错的图片。