using System;
 
namespace binarySearchTree
{
 
	//-------------------------------------------------------------------------
	//                             Klasse Bst
	//-------------------------------------------------------------------------
	// Die Klasse Bst implementiert einen binären Suchbaum für Objekte, die
	// IComparable erfüllen.
	// Die Methode visit muss bei Bedarf angepasst, d.h. in einer Subclass
	// überschrieben werden.
	public class Bst
	{
		///////////////////////////////////////////////////////////////////////
		//                         public part:
		///////////////////////////////////////////////////////////////////////
 
		//--------------exception Klassen--------------------------------------
		public sealed class EMPTY_TREE   : Exception {}
		public sealed class NO_SUCH_NODE : Exception {}
 
 
		//--------------Klasse Node--------------------------------------------
		protected sealed class Node
		{
			public Node left;			// linker Nachfolger
			public IComparable info;	// Info-Feld
			public Node right;			// rechter Nachfolger
 
			public int count;			// Zaehler fuer identische Knoten
		}
 
 
		//--------------Bst----------------------------------------------------
		public Bst()
		{
			root = null;
		}
 
        //--------------insert-------------------------------------------------
        public void insert(IComparable ding)
        {
            rec_insert(ding, ref root);
        }
 
        //--------------traverse_inorder---------------------------------------
		public void traverse_inorder( )
		{
			rec_traverse_inorder( root );
		}
 
		//--------------traverse_inorder_invert--------------------------------
		public void traverse_inorder_invert( )
		{
			rec_traverse_inorder_invert( root );
		}
 
		//--------------find---------------------------------------------------
		// Ein 'IComparable' ding im Baum suchen.
		// Erzeugt die exception NO_SUCH_NODE, falls der Knoten nicht gefunden 
		// wird. Sonst wird die Methode visit für den gefundenen Knoten 
		// ausgeführt:
		public void find( IComparable ding  ) 
		{
			rec_find( ding, root );
		}
 
        //--------------deleteAll----------------------------------------------
        // Entfernt den gesamten Knoten mit Inhalt ding. Der Wert des Zählers 
        // für identische Knoten wird dabei nicht beachtet.
        public void deleteAll(IComparable ding)
        {
            rec_deleteAll(ding, ref root);
        }
 
        //--------------depth--------------------------------------------------
		// Die Tiefe des Baums bestimmen.
		// Erzeugt evtl. die exception EMPTY_TREE
		public int depth() 
		{
			max_depth    = 0;
			actual_depth = 0;
 
			if( root == null ) throw new EMPTY_TREE();
 
			rec_depth( root );
 
			return max_depth - 1; // Baum mit einem Knoten -> Tiefe 0 !
		}
 
		//--------------nodes--------------------------------------------------
		// Liefert die Anzahl aller Knoten, mehrfach vorhandene Knoten
		// werden mitgezählt.
		public int nodes()
		{
			no_of_nodes = 0;
 
			rec_nodes( root );
 
			return no_of_nodes;
		}
 
		//--------------nodes_RString------------------------------------------
		// Liefert die Anzahl aller Knoten rechtsbündig in einem 6-stelligen 
		// string. Mehrfach vorhandene Knoten werden mitgezählt.
		public string nodes_RString()
		{
			return nodes().ToString().PadLeft( 6, ' ' );
		}
 
		//--------------non_ident_nodes----------------------------------------
		// Liefert die Anzahl nicht identischer Knoten, mehrfach vorhandene
		// Knoten werden nicht mitgezählt.
		public int non_ident_nodes()
		{
			no_of_non_ident_nodes = 0;
 
			rec_non_ident_nodes( root );
 
			return no_of_non_ident_nodes;
		}
 
		//--------------non_ident_nodes_RString--------------------------------
		// Liefert die Anzahl aller Knoten rechtsbündig in einem 6-stelligen 
		// string. Mehrfach vorhandene Knoten werden mitgezählt.
		public string non_ident_nodes_RString()
		{
			return non_ident_nodes().ToString().PadLeft( 6, ' ' );
		}
 
		//--------------reset--------------------------------------------------
		public void reset()
		{
			root = null;
			max_depth = 0;          
			actual_depth = 0;          
			no_of_nodes = 0; 
			no_of_non_ident_nodes = 0;
		}
 
 
		///////////////////////////////////////////////////////////////////////
		//                     protected / private part:
		///////////////////////////////////////////////////////////////////////
 
		private Node root;
 
		private int max_depth;             // Tiefe des Baums
		private int actual_depth;          // momentane Tiefe
		private int no_of_nodes;           // Anzahl aller Knoten
		private int no_of_non_ident_nodes; // Anzahl nicht identischer Knoten
 
 
		//--------------rec_insert---------------------------------------------
		private void rec_insert( IComparable ding , ref Node tree )
		{
			if( tree == null )// Einfügeposition gefunden, neuen Knoten anlegen:
			{
				tree = new Node();
 
				// Daten in neuen Knoten schreiben:
				tree.left  = null;
				tree.info  = ding;
				tree.right = null;
				tree.count = 1;
			}
			else
			{
				if( ding.CompareTo(tree.info) < 0 )        // links weiter suchen:
					rec_insert( ding, ref tree.left );
 
				else if ( ding.CompareTo(tree.info) > 0 )  // rechts weiter suchen:
					rec_insert( ding, ref tree.right );
 
				else   // gleiches Ding gefunden, Anzahl inkrementieren:
					tree.count = tree.count + 1;
			}
		}
 
		//--------------rec_traverse_inorder-----------------------------------
		private void rec_traverse_inorder( Node tree )
		{
            if (tree != null)
            {
                rec_traverse_inorder(tree.left);
                visit(tree.info, tree.count);
                rec_traverse_inorder(tree.right);
            }
        }
 
		//--------------rec_traverse_inorder_invert----------------------------
		private void rec_traverse_inorder_invert( Node tree )
		{
            if (tree != null)
            {
                rec_traverse_inorder_invert(tree.right);
                visit(tree.info, tree.count);
                rec_traverse_inorder_invert(tree.left);
            }
        }
 
        //--------------rec_find-----------------------------------------------
        private void rec_find(IComparable ding, Node tree)
        {
 
            if (tree == null)
            {
                throw new NO_SUCH_NODE();
            }
            else 
            {
                if (ding.CompareTo(tree.info) < 0)
                {
                    rec_find(ding, tree.left);
                }
                else if (ding.CompareTo(tree.info) > 0)
                {
                    rec_find(ding, tree.right);
                }
                else if (ding.CompareTo(tree.info) == 0)
                {
                    Console.WriteLine("Knoten mit Inhalt '" + tree.info + "' wurde gefunden");
                }
            }
        }
 
        //--------------findMin------------------------------------------------
        // Sucht kleinstes Element im Baum tree.
        // Diese Methode wird von rec_deleteAll aufgerufen.
        private Node findMin(Node tree)
        {
            if (tree == null)
            {
                throw new NO_SUCH_NODE();
            }
            else
            {
                if (tree.left == null)
                {
                    return tree;
                }
                else
                {
                    return findMin(tree.left);
                }
            }
        }
 
        //--------------rec_deleteAll------------------------------------------
        private void rec_deleteAll(IComparable ding, ref Node tree)
        {
            if (tree == null)
                throw new NO_SUCH_NODE();
            else
            {
                if (ding.CompareTo(tree.info) < 0)
                    rec_deleteAll(ding, ref tree.left);
                else if (ding.CompareTo(tree.info) > 0)
                    rec_deleteAll(ding, ref tree.right);
                else
                {
                    //Knoten ist Blatt -> Ref auf ihn wird gelöscht
                    if (tree.left == null && tree.right == null)
                    {
                        tree = null;
                    }
                    //Knoten hat keinen rechten Nachfolger
                    else if (tree.left != null && tree.right == null)
                    {
                        tree = tree.left;
                        tree.left = null;
                    }
                    //Knoten hat keinen linken Nachfolger
                    else if (tree.left == null && tree.right != null)
                    {
                        tree = tree.right;
                        tree.right = null;
                    }
 
                    //Knoten hat zwei Childs
                    else if (tree.left != null && tree.right != null)
                    {                        
                        tree.info = findMin(tree.right).info;
                        tree.count = findMin(tree.right).count;
                        rec_deleteAll(tree.info, ref tree.right);
                    }
                }
            }
        }
 
        //--------------visit--------------------------------------------------
		// visit wird beim Besuch eines Knotens ausgeführt.
		// Hier: ding und die entspr. Anzahl werden in einer Zeile auf der 
		// Console ausgegeben.
		//
		// visit muss in Subclasses angepasst, also überschrieben werden.
		//
		protected virtual void visit( IComparable ding, int anzahl )
		{
			int zProZeile = 60;  // Zeichen pro Ausgabezeile
 
			string str = ( anzahl.ToString() + 
                           Environment.NewLine ).PadLeft( zProZeile, '.' );
 
			str = ding + str.Substring( ding.ToString().Length, 
										str.Length - ding.ToString().Length );
 
			Console.Write( str );
		}
 
		//--------------rec_depth----------------------------------------------
		// Berechnet die maximale Tiefe des Baums.
		// Zur Implementation: Vor jedem rekursiven Aufruf wird der Zähler  
		// inkrementiert (beim "Abstieg"), nach jedem rekursiven Aufruf wird 
		// der Zähler dekrementiert (beim "Aufstieg").
		private void rec_depth( Node tree )
		{
			if( tree != null )
			{
				actual_depth = actual_depth + 1;
				if ( actual_depth > max_depth )
					max_depth = actual_depth;
 
				rec_depth( tree.left);
 
                //actual_depth = actual_depth - 1;
                //actual_depth = actual_depth + 1;
                //if (actual_depth > max_depth)
                //    max_depth = actual_depth;
 
				rec_depth( tree.right);
 
				actual_depth = actual_depth - 1;
			}
		}
 
		//--------------rec_nodes----------------------------------------------
		// Zählt alle Knoten mit einer preorder-Durchmusterung.
		private void rec_nodes( Node tree )
		{
			if (tree != null)
			{
				no_of_nodes = no_of_nodes + tree.count;
 
				rec_nodes( tree.right);
				rec_nodes( tree.left);
			}
		}
 
		//--------------rec_non_ident_nodes------------------------------------
		// Zählt alle nicht identischen Knoten mit einer preorder-Durchmusterung.
		private void rec_non_ident_nodes( Node tree )
		{
			if (tree != null)
			{
				no_of_non_ident_nodes = no_of_non_ident_nodes + 1;
 
				rec_non_ident_nodes( tree.right);
				rec_non_ident_nodes( tree.left);
			}
		}
 
	}
}