How to print out a BST in C++

My C++ program creates a binary search tree. I know how to print out the values in pre-order, post-order, and in-order.

However, I want to do something a little more difficult. I want to print out the values the way they would look if someone drew the tr开发者_JAVA百科ee on paper. It would have the root at the center at the top, it's left child right under and to the left of it, and it's right child right under and to the right of it. The rest of the nodes would be drawn accordingly.

How can I do that?

This article contains code for what you need, it seems:

alt text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

Edit: that site went offline

Here's another one exploring some other options.

Here's approximate pseudo-code to do it. The basic idea is walk the tree layer-by-layer, printing all the node in each layer on one line. Each node is separated by twice as much space as the nodes below it. Since the tree is not all of uniform depth, it is artificially padded with virtual nodes to take up the blank spaces where nodes don't exist.

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
}

Each space that is printed is the width of one numeric field. Suppose the tree has depth D = 4. Then the printing goes like this:

// 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

    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);
        }
    }

One way is to use graphviz. Specifically, use its "dot" program, but getting the output to look exactly as you describe may not be possible.

well, in a terminal it's hard...since it may not fit. But there are graph drawing libraries out there that can make nice pictures for you. There is graphvis that is one of the most popular.

edit: if you really just wan to print text, graphvis has a markup language that a user can pass to graphvis that in turn makes the nice pictures.