Code-Bin #1056

untitled PHP Code
Posted by: Binary Tree | January 11, 2011 @ 3:53pm

PHP Code

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);
			}
		}

}
}

Syntax Highlighting

[Open in new window]

Author Comments

none

Rating

4.42 / 8
69 Votes