#include <iostream>

typedef int traversal_type;

const traversal_type bfs_order = 0;
const traversal_type dfs_preorder = 1;
const traversal_type dfs_inorder = 2;
const traversal_type dfs_postorder = 3;

struct node
{
	int info;
	int balance_factor; // this is only for temporary calculation.
	node *leftson, *rightson, *father;
};

class bin_tree
{
	node *root, *getnode();
	
	void rrotate (node *p); // Refer to The Design and Analysis of Algorithms by
	void lrotate (node *p); // Anani V Levitin for discussion on AVL trees
	void rlrotate (node *p);
	void lrrotate (node *p);
	int height (node *p);
	
	void preorder (node *tree);
	void inorder (node *tree);
	void postorder (node *tree);
	void bredth_first (node *tree); // this doesn't display NULL nodes
	// so don't use it for trees that are NOT almost (essentially) complete.
	
	public:
		bin_tree (node * assign = NULL) {root = assign;};
		void add_node (int a);
		void display (traversal_type);		
};

class queue
{
	struct q_node
	{
		node *info;
		q_node *next;
	};
	q_node *front, *rear;	
	public:
		queue (void) {front = NULL, rear = NULL;};
		void insert (node *element);
		node *remove (void);
		bool isempty (void);
};