// MyTree.C
// burton rosenberg
// 29 Sept 1997

#include<iostream.h>

typedef char ItemType  ;

// Data structure for each of the tree nodes
struct TreeNode {
	ItemType item ;
	TreeNode * left, * right ;

// Constructors
	TreeNode(ItemType it, TreeNode * v ) { 
		item = it ; 
		left = right = v ; } 
	const ItemType  DEFAULT_ITEM = '\0' ;
	TreeNode(void) { TreeNode(DEFAULT_ITEM, NULL ) ; } 

} ;

// Tree class definition
class MyTree {
private:
	TreeNode * root ;
	TreeNode * leaf ;
	void printaux( 
		TreeNode * subroot, 
		int numbering, int level ) ;
public:
	MyTree(void) ;
	void print(void) ;
	void insert(ItemType it) ;

} ;


// Method Implementations

// Constructor
MyTree::MyTree(void) {
	leaf = new TreeNode ;
	root = new TreeNode( '\0', leaf ) ;
}

// Data "visualizer"
void MyTree::print(void) {
	this->printaux(this->root->right, 1, 0 ) ;
}

// auxillary function (private to class) for recursion.
void MyTree::printaux( TreeNode * r, int n, int l ) {

	// indent according to level l
	for ( int i=0; i<l; i++ ) cout << "  " ;

	// if leaf ..
	if ( r==leaf ) {
		cout << "-" << endl ;
		return ;
	}

	// else print item and recurse on left, then on right.
	cout << r->item << endl ;
	printaux( r->left, 2*n, l+1 ) ;
	printaux( r->right, 2*n+1, l+1 ) ;	
}


// Data mutator: insert an item.
void MyTree::insert(ItemType it) {
	TreeNode * p, * q ;
	p = root ;
	q = root->right ;

	// search the tree for it, until you find a leaf.
	// L.I. p is parent of q.
	while ( q!=leaf ) {
		p = q ;
		if ( q->item > it ) q = q->left ;
		else q = q->right ;
	}

	// check again whether to insert left or right from p.
	if ( p->item > it ) p->left = new TreeNode(it,leaf) ;
	else p->right = new TreeNode(it,leaf) ;
}
	
// Demonstrate the use of the class in the main.
int main (int argc, char * argv[] ) {

	MyTree * mt = new MyTree ;
	mt->insert('a') ;
	mt->insert('f') ;

	mt->insert('b') ;
	mt->print() ;
}