draw_bst.cpp

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

struct BST_node
{
	int data;
	BST_node * left, * right;
	BST_node() : left(NULL), right(NULL) {};
	BST_node(int _data) : data(_data), left(NULL), right(NULL) {};
};

BST_node * BST_insert(BST_node * root, int _value)
{		
	if (root == NULL)
		return new BST_node(_value);
		
	if (_value < root->data)
		root->left = BST_insert(root->left, _value);
		
	else
		root->right = BST_insert(root->right, _value);
		
	return root;
}

unsigned int BST_depth(BST_node * root)
{
	if (root == NULL)
		return 0;
		
	unsigned int left_depth = BST_depth(root->left);
	unsigned int right_depth = BST_depth(root->right);
	
	return (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;
}

void BST_queue(int * queue, BST_node * root, int index)
{
	if (root == NULL)
		return;
		
	if (index == 0)
		queue[0] = root->data;
	
	if (root->left != NULL)
	{
		queue[2*index + 1] = root->left->data;
		BST_queue(queue, root->left, 2*index+1);
	}
	if (root->right != NULL)
	{
		queue[2*index + 2] = root->right->data;
		BST_queue(queue, root->right, 2*index+2);
	}
}

void BST_draw(BST_node * root, int block_width)
{
	int depth = BST_depth(root);
	int max_blocks = pow(2, depth - 1);
	int blocks_count = 0;
	for (int i = 0; i < depth; ++i)
	{
		blocks_count += pow(2,i);
	}
	
	int * queue = new int[blocks_count];
	for (int i = 0; i < blocks_count; queue[i++] = -1);
	BST_queue(queue, root, 0);
	
	int width = max_blocks * block_width;
	int begin = 0;
	for (int i = 0; i < depth; ++i)
	{
		int current_width = width / pow(2,i);
		for (int j = begin; j < begin+pow(2,i); ++j)
		{
			if (j == begin)
				cout << setw(current_width/2);
			else
				cout << setw(current_width);
				
			if (queue[j] != -1)
				cout << queue[j];
			else
				cout << " ";
		}
		begin += pow(2,i);
		cout << "\n";
	}
}
	
int main(int argc, char ** argv)
{
	unsigned int value, size;
	cin >> size;
	BST_node * root = NULL;
	for (int i = 0; i < size; ++i)
	{
		cin >> value;
		root = BST_insert(root, value);
	}
	BST_draw(root, 4);
	return 0;
}