How to print BST in C ++

Question

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

However, I want to make something a little more complicated. I want to print the values ​​the way they will look if someone painted a tree on paper. He would have a root in the center above, he left a child to his right and left, and he was a right child to his right and right. The remaining nodes will be drawn accordingly.

How can i do this?

Answer 1

This article contains the code for what you need seems to be:

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

Edit: This site is down.

Here is another one exploring some other parameters.

Answer 2

Here's an example pseudo code to do this. The main idea is to walk the tree in stages, printing all the nodes in each layer on one line. Each node is divided twice as much space as the nodes below it. Since the tree does not have the same depth, it is artificially supplemented by virtual nodes that occupy spaces where the nodes do not 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 printed space represents the width of one numeric field. Suppose the tree has a depth of D = 4. Then the print will look 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: nnnnnnnn 0 1 1 1 1 1 1 1 

Answer 3

One way is to use graphviz. In particular, use your "spot" program, but it may not be possible to get the result for viewing exactly as you describe.

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

well, in the terminal it is difficult ... as it may not correspond. But there are graphic drawing libraries that can take nice photos for you. There is graphite, which is one of the most popular.

edit: if you really just want to print the text, the graph has a markup language that the user can transmit to the graph, which in turn takes nice pictures.