How can I print a Binary Tree Search class Vertically?

I've been learning how to program Binary Tree Search using Linked Lists in C++. 开发者_如何转开发Everything works fine and I understand how the Binary Tree works however I would like to be able to print the tree with the head on top and all the nodes following bellow as I try to demonstrate here:

                                     [root or head]
                            [left]                    [right]

                      [left]      [right]       [left]       [right]

I am using the Console to print the tree, therefore feel free to use 'cout' or 'printf'. I believe I need to set the width of the console but I'm not sure how to start.

Thanks, Y_Y

---

As sbi mentioned, making a left-aligned version is easier than a center-aligned one. But whichever alignment you choose your fundamental algorithmic approach should be:

Traverse the tree breadth-first. Do this by using a queue with the following algorithm:

1. Declare a queue
2. Add the root node to the queue
3. While the queue contains more nodes, do 4 - 6:
4. Dequeue a node
5. Print the node. After every print that is one less than a power of 2th time (starting from 1), also print a newline.
6. Enqueue the node's children

(See http://www.cs.bu.edu/teaching/c/tree/breadth-first/ )

In order to print a center-aligned tree, also do the following (only works if the tree is complete. If it's not complete, the easiest thing to do is make a complete copy where every place that should have a node gets some kind of a null node):

• Instead of printing to the screen, "print" each line into a string in an array of strings.
• As you go, keep track of the length in characters of the longest element you print. Let's call this maxElemLen.
• Whenever you print an element, print one tab character before it and one tab character after it.
• At the very end, go back, and in every line in the array, replace each tab character with 2^(nLines - lineNum) tab characters.
• Then expand each tab that comes after a tab or newline to maxElemLen+1 spaces, and expand each tab that comes after anything else (i.e., after a printed elem) to (maxElemLen + 1 - (the number of characters elapsed since the last tab)) spaces.
• Finally, print each line of your array, in order.

---

This is the code to print binary tree - below code prints binary tree from left to right fashion

private void printTree(Node nNode,int pos){
    if (nNode==null) {
        for(int i=0;i<pos;i++) System.out.print("\t");
        System.out.println("*");
        return;
    }
    printTree(nNode.right,pos+1);
    for(int i=0;i<pos;i++) System.out.print("\t");
    System.out.println(nNode.data);
    printTree(nNode.left,pos+1);
}

Here is the output of above method

'*' in above output indicates a null

---

@IsAs's solution. 90 degree CCW rotated tree in C++. I advise this be used on trees no larger than 2^4.

print(root);
void BinarySearchTree::print(BinaryNode* n, int pos = 0){
    if (n==NULL) {
        for(int i = 0; i < pos; ++i)
            cout << "\t";
        cout << 'X' << endl;
        return;
    }
    print(n->right,pos+1);
    for(int i = 0; i < pos; i++)
        cout << "\t";
    cout << n->key << endl;
    print(n->left,pos+1);
}