draw_bst_tpl.cpp

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

using namespace std;

template <typename T>
struct BST_node
{
	T data;
	BST_node<T> * left, * right;
	BST_node<T>() : left(NULL), right(NULL) {};
	BST_node<T>(T _data) : data(_data), left(NULL), right(NULL) {};
};

template <typename T>
BST_node<T> * insert(BST_node<T> * root, T _value)
{		
	if (root == NULL)
		return new BST_node<T>(_value);
		
	if (_value < root->data)
		root->left = insert(root->left, _value);
		
	else
		root->right = insert(root->right, _value);
		
	return root;
}

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

template <typename T>
void BST_queue(T* queue, BST_node<T> * 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);
	}
}

template <typename T>
void BST_draw(BST_node<T> * root, int block_width)
{
	int depth = BST_depth<T>(root);
	int max_blocks = pow(2, depth - 1);
	int blocks_count = 0;
	for (int i = 0; i < depth; ++i)
	{
		blocks_count += pow(2,i);
	}
	
	T * queue = new T[blocks_count];
	BST_queue<T>(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] != 0)
				cout << queue[j];
			else
				cout << "X";
		}
		begin += pow(2,i);
		cout << "\n";
	}
}
	
int main(int argc, char ** argv)
{
	unsigned int value, size;
	cin >> size;
	BST_node<int> * root = NULL;
	for (int i = 0; i < size; ++i)
	{
		cin >> value;
		root = insert(root, value);
	}
	BST_draw(root, 4);
	return 0;
}