The Code-Bin
Links
Home
Add your code!
All Listings
About
Latest Entry
Featured Scripts
Author's Website
Latest Entries
FFMPEG Thumbnail Scr...
PHP, 0.8KB
Jul. 29, 10:24pm
John
Z80 Assembler, 190 bytes
Feb. 17, 3:36am
John
Z80 Assembler, 176 bytes
Sep. 13, 2:19am
John
Z80 Assembler, 77 bytes
Sep. 13, 2:18am
John
Z80 Assembler, 209 bytes
Sep. 13, 2:17am
untitled PHP Code
Posted by: Binary Tree | January 11, 2011 @ 3:53pm
PHP Code
[
Download
]
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
http://codebin.yi.org/1056
page generated in 0.00 seconds