#1 10. Februar 2010 BinaryTree (binärer Suchbaum) Hoi! Hatte heute ein wenig Langeweile und hab mal einen Binärbaum in Python zusammengeschrieben. Die Grundfunktionalitäten sind implementiert, d.h.: Werte einfügen, Werte löschen, InOrder Traversierung, kleinster Wert finden, größter Wert finden. Geschrieben mit Python 3.1.1, sollte aber auch mit 2.5/6 laufen. Wenn ein Element schon vorhanden sein sollte, dann wird es NICHT eingefügt, sondern ignoriert. Ich habe die Funktionalitäten rudimentär getestet. Wenn ihr Fehler findet, dann gebt mir Bescheid! Beispielcode: PHP: import random bTree = BinaryTree ( 6 ) #initialisiert den Baum mit der Zahl 6 for i in range ( 100 ): bTree . insert ( random . randint ( 1 , 9999 ) #fuellt den Baum mit Zufallszahlen (1-9999) for i in bTree . inOrder (): print( i ) #gibt den Baum in aufsteigender Reihenfolge aus b = bTree . find ( 5 ) #sucht den Knoten mit der Value 5 if b : bTree . remove ( b ) #wenn b vorhanden ist, dann entferne den Knoten del bTree #gibt alle Knoten frei und loescht den Baum Classes: PHP: class BinaryNode : def __init__ ( self , value , parent = None ): self . __value = value self . __left = None self . __right = None self . __parent = parent def __del__ ( self ): del self . __left del self . __right del self . __parent del self . __value def getValue ( self ): return self . __value def setValue ( self , value ): self . __value = value def getLeft ( self ): return self . __left def setLeft ( self , left ): self . __left = left def getRight ( self ): return self . __right def setRight ( self , right ): self . __right = right def getParent ( self ): return self . __parent def setParent ( self , parent ): self . __parent = parent Value = property ( getValue , setValue ) Left = property ( getLeft , setLeft ) Right = property ( getRight , setRight ) Parent = property ( getParent , setParent ) class BinaryTree : def __init__ ( self , rootval ): self . __root = BinaryNode ( rootval ) def __del__ ( self ): while self . __root . Right or self . __root . Left : if self . __root . Left : self . remove ( self . __root . Left ) else: self . remove ( self . __root . Right ) del self . __root def insert ( self , value ): if self .Empty: self . __root . Value = value else: self . __insertRecur ( value , self . __root ) def __insertRecur ( self , value , start ): if value < start . Value : if not start . Left : start . Left = BinaryNode ( value , start ) else: self . __insertRecur ( value , start . Left ) elif value > start . Value : if not start . Right : start . Right = BinaryNode ( value , start ) else: self . __insertRecur ( value , start . Right ) def getRoot ( self ): return self . __root Root = property ( getRoot ) def isEmpty ( self ): if self . __root . Value : return False else: return True Empty = property ( isEmpty ) def inOrder ( self ): inorder = [] self . __inOrderRecur ( self . __root , inorder ) return inorder def __inOrderRecur ( self , start , elems ): if start . Left : self . __inOrderRecur ( start . Left , elems ) elems . append ( start . Value ) if start . Right : self . __inOrderRecur ( start . Right , elems ) def findMin ( self ): return self . __findMinBelow ( self . __root ) def __findMinBelow ( self , start ): tmp = start while tmp . Left : tmp = tmp . Left return tmp def findMax ( self ): return self . __findMaxBelow ( self . __root ) def __findMaxBelow ( self , start ): tmp = start while tmp . Right : tmp = tmp . Right return tmp def find ( self , value ): return self . __findIter ( self . __root , value ) def __findIter ( self , start , value ): tmp = start while True : if value == tmp . Value : return tmp elif value < tmp . Value : if tmp . Left : tmp = tmp . Left else: return None else: if tmp . Right : tmp = tmp . Right else: return None def remove ( self , node ): if node . Left == None and node . Right == None : self . __removeLeaf ( node ) elif node . Left == None or node . Right == None : self . __removeSingle ( node ) else: minRight = self . __findMinBelow ( node . Right ) node . Value = minRight . Value self . remove ( minRight ) def __removeLeaf ( self , node ): if node is self . __root : self . __root . Value = None else: if node . Parent . Right is node : node . Parent . Right = None else: node . Parent . Left = None del node def __removeSingle ( self , node ): child = None if node . Left : child = node . Left else: child = node . Right if node is self . __root : self . __root = child child . Parent = None del node else: parent = node . Parent if node is parent . Left : parent . Left = child else: parent . Right = child child . Parent = parent del node greez + Multi-Zitat Zitieren
#2 10. Februar 2010 AW: BinaryTree (binärer Suchbaum) mir war ein wenig langweilig auf der arbeit, deshalb hab ich den code mal zu php5.3 portiert PHP: <? php $tree = new xbinary :: Tree ( 6 ); // "::" mit "\" ersetzen for( $i = 0 ; $i < 100 ; ++ $i ) $tree -> insert ( rand ( 1 , 9999 )); foreach( $tree -> inOrder () as $value ) print $value . "<br />\n" ; $node = $tree -> find ( 5 ); if( null !== $node ) $tree -> remove ( $node ); unset( $tree ); PHP: <? php namespace xbinary ; // node class Node { public $value , $left = null , $right = null , $parentNode ; //"parent" is reserved /** * constructor * * @param int value * @param Node|null parent */ public function __construct ( $value , Node & $parent = null ) { $this -> value = $value ; $this -> parentNode = $parent ; } public function __destruct () { if( $this -> right ) unset( $this -> right ); } } //tree class Tree { private $_root ; public function __construct ( $rootval ) { $this -> _root = new Node ( $rootval ); } public function __destruct () {} public function insert ( $value ) { $this -> insertRecur ( $value , $this -> _root ); } protected function insertRecur ( $value , Node & $start ) { if( $value < $start -> value ) { if( null === $start -> left ) $start -> left = new Node ( $value , $start ); else $this -> insertRecur ( $value , $start -> left ); } elseif( $value > $start -> value ) { if( null === $start -> right ) $start -> right = new Node ( $value , $start ); else $this -> insertRecur ( $value , $start -> right ); } } public function inOrder () { $stack = array(); $this -> inOrderRecur ( $this -> _root , $stack ); return $stack ; } protected function inOrderRecur ( Node & $start , array & $stack ) { if( null !== $start -> left ) $this -> inOrderRecur ( $start -> left , $stack ); $stack [] = $start -> value ; if( null !== $start -> right ) $this -> inOrderRecur ( $start -> right , $stack ); } public function findMin ( $int = false ) { $tmp = $this -> findMinBelow ( $this -> _root ); return $int ? $tmp -> value : $tmp ; } protected function findMinBelow ( Node $node ) { while( null !== $node -> left ) $node = $node -> left ; return $node ; } public function findMax ( $int = false ) { $tmp = $this -> findMaxBelow ( $this -> _root ); return $int ? $tmp -> value : $tmp ; } protected function findMaxBelow ( Node $node ) { while( null !== $node -> right ) $node = $node -> right ; return $node ; } public function find ( $value , $limit = 0 ) { if(! is_int ( $limit ) || $limit === 0 ) $limit = PHP_MAX_INT ; $tmp = $this -> _root ; $itr = 0 ; do { if( $value == $tmp -> value ) return $int ? $tmp -> value : $tmp ; if( $value < $tmp -> value ) { if( null === $tmp -> left ) return null ; $tmp = $tmp -> left ; continue; } else { if( null === $tmp -> right ) return null ; $tmp = $tmp -> right ; continue; } } while(++ $itr < $limit ); } public function remove ( Node & $node ) { if( null === $node -> left && null === $node -> right ) $this -> removeLeaf ( $node ); elseif( null === $node -> left || null === $node -> right ) $this -> removeSingle ( $node ); else { $minRight = $this -> findMinBelow ( $node -> right ); $node -> value = $minRight -> value ; $this -> remove ( $minRight ); } } protected function removeLeaf ( Node & $node ) { if( null !== $node -> parentNode -> right ) $node -> parentNode -> right = null ; else $node -> parentNode -> left = null ; unset( $node ); } protected function removeSingle ( Node & $node ) { if( null !== $node -> right ) { if( $node === $this -> _root ) { $node -> right -> parentNode = null ; $this -> _root = $node -> right ; } else { $node -> right -> parentNode = $node -> parentNode ; $node -> parentNode -> right = $node -> right ; } } else { if( $node === $this -> _root ) { $node -> left -> parentNode = null ; $this -> _root = $node -> right ; } else { $node -> left -> parentNode = $node -> parentNode ; $node -> parentNode -> left = $node -> left ; } } unset( $node ); } } + Multi-Zitat Zitieren
#3 5. März 2010 AW: BinaryTree (binärer Suchbaum) Hab mal 2 kleine Fehler behoben. Hatte wohl am Ende nicht mehr so viel Lust und dann ein Logikfehler drin :/ Nun sollte alles richtig funktionieren greez + Multi-Zitat Zitieren
#4 28. Dezember 2010 AW: BinaryTree (binärer Suchbaum) Hier noch eine C#.NET Konsolenanwendungs-Variante: Main Program PHP: using System ; using BinaryTreeLib ; namespace TreeTest { // class TreeTest definition public class TreeTest { // test class Tree static void Main ( string [] args ) { Tree tree = new Tree (); int insertValue ; int deleteValue = 0 ; Console . WriteLine ( "Delete nothing:" ); tree . DeleteNode ( 1 ); Console . WriteLine ( "Inserting values: " ); Random random = new Random (); // insert 10 random integers from 0-99 in tree for ( int i = 1 ; i <= 10 ; i ++ ) { insertValue = random . Next ( 100 ); Console . Write ( insertValue + " " ); tree . InsertNode ( insertValue ); } // perform preorder traversal of tree Console . WriteLine ( "\n\nPreorder traversal" ); tree . PreorderTraversal (); // perform inorder traversal of tree Console . WriteLine ( "\n\nInorder traversal" ); tree . InorderTraversal (); // perform postorder traversal of tree Console . WriteLine ( "\n\nPostorder traversal" ); tree . PostorderTraversal (); while ( true ) { Console . Write ( "\n\nEnter a Value to delete (Stop with -1): " ); deleteValue = Convert . ToInt32 ( Console . ReadLine ()); if ( deleteValue == - 1 ) break; tree . DeleteNode ( deleteValue ); // perform preorder traversal of tree Console . WriteLine ( "\n\nPreorder traversal" ); tree . PreorderTraversal (); // perform inorder traversal of tree Console . WriteLine ( "\n\nInorder traversal" ); tree . InorderTraversal (); // perform postorder traversal of tree Console . WriteLine ( "\n\nPostorder traversal" ); tree . PostorderTraversal (); Console . WriteLine (); } Console . Read (); } } // end class TreeTest } Class BinaryTreeLib PHP: using System ; using System . Collections . Generic ; using System . Linq ; using System . Text ; namespace BinaryTreeLib { // class TreeNode definition class TreeNode { private TreeNode leftNode ; private int data ; private TreeNode rightNode ; // initialize data and make this a leaf node public TreeNode ( int nodeData ) { data = nodeData ; leftNode = rightNode = null ; // node has no children } // LeftNode property public TreeNode LeftNode { get { return leftNode ; } set { leftNode = value ; } } // Data property public int Data { get { return data ; } set { data = value ; } } // RightNode property public TreeNode RightNode { get { return rightNode ; } set { rightNode = value ; } } // insert TreeNode into Tree that contains nodes; // ignore duplicate values public void Insert ( int insertValue ) { // insert in left subtree if ( insertValue < data ) { // insert new TreeNode if ( leftNode == null ) leftNode = new TreeNode ( insertValue ); // continue traversing left subtree else leftNode . Insert ( insertValue ); } // insert in right subtree else if ( insertValue > data ) { // insert new TreeNode if ( rightNode == null ) rightNode = new TreeNode ( insertValue ); // continue traversing right subtree else rightNode . Insert ( insertValue ); } } // end method Insert // delete TreeNode from Tree that contains nodes; public void Delete ( int deleteValue ) { if ( deleteValue < Data ) //Value in left Side of Tree { if ( LeftNode . Data == deleteValue ) { if ( LeftNode . IsLeaf ()) { LeftNode = null ; //delete Console . WriteLine ( "Value found and deleted (was a Leaf on the left Side)." ); } else if ( LeftNode . HasAChild ()) { if ( LeftNode . LeftNode == null ) //Replace with its Child != null LeftNode = LeftNode . RightNode ; else LeftNode = LeftNode . LeftNode ; Console . WriteLine ( "Value found and replaced with its next (found on the left Side)." ); } else { TreeNode tmp = LeftNode . RightNode . GetMinNode (); //Get smallest Node of the right Side tmp . LeftNode = LeftNode . LeftNode ; tmp . RightNode = LeftNode . RightNode ; LeftNode = tmp ; //Replace searched Value with the smallest Node of the right Side Console . WriteLine ( "Value replaced with smallest Node (Value found on left Side)." ); } } else { Console . WriteLine ( "Searching for Value on the left Side..." ); LeftNode . Delete ( deleteValue ); } } else if ( deleteValue > Data ) //Value in right Side of Tree { if ( RightNode . Data == deleteValue ) { if ( RightNode . IsLeaf ()) { RightNode = null ; //delete Console . WriteLine ( "Value found and deleted (was a Leaf on the right Side)." ); } else if ( RightNode . HasAChild ()) { if ( RightNode . LeftNode == null ) //Replace with its Child != null RightNode = RightNode . RightNode ; else RightNode = RightNode . LeftNode ; Console . WriteLine ( "Value found and replaced with its next (found on the right Side)." ); } else { TreeNode tmp = RightNode . RightNode . GetMinNode (); //Get smallest Node of the right Side tmp . LeftNode = RightNode . LeftNode ; tmp . RightNode = RightNode . RightNode ; RightNode = tmp ; //Replace searched Value with the smallest Node of the right Side Console . WriteLine ( "Value replaced with smallest Node (Value found on right Side)." ); } } else { Console . WriteLine ( "Searching for Value on the right Side..." ); RightNode . Delete ( deleteValue ); } } else Console . WriteLine ( "The searched Value is the root Value - it's not deletable" ); } // end method DeleteNode //Helper Methods private bool IsLeaf () { if ( this . LeftNode == null && this . RightNode == null ) return true ; else return false ; } private bool HasAChild () { if (( this . LeftNode != null && this . RightNode == null ) || ( this . LeftNode == null && this . RightNode != null )) return true ; else return false ; } private TreeNode GetMinNode () { if ( LeftNode . LeftNode != null && LeftNode != null ) return LeftNode . GetMinNode (); else { int value = LeftNode . Data ; LeftNode = LeftNode . RightNode ; return new TreeNode ( value ); } } } // end class TreeNode // class Tree definition public class Tree { private TreeNode root ; // construct an empty Tree of integers public Tree () { root = null ; } // Insert a new node in the binary search tree. // If the root node is null, create the root node here. // Otherwise, call the insert method of class TreeNode. public void InsertNode ( int insertValue ) { lock ( this ) { if ( root == null ) root = new TreeNode ( insertValue ); else root . Insert ( insertValue ); } } public void DeleteNode ( int deleteValue ) { lock ( this ) { if ( root == null ) Console . WriteLine ( "Baum leer - kann nicht gelöscht werden.\n" ); else root . Delete ( deleteValue ); } } // begin preorder traversal public void PreorderTraversal () { lock ( this ) { PreorderHelper ( root ); } } // recursive method to perform preorder traversal private void PreorderHelper ( TreeNode node ) { if ( node == null ) return; // output node data Console . Write ( node . Data + " " ); // traverse left subtree PreorderHelper ( node . LeftNode ); // traverse right subtree PreorderHelper ( node . RightNode ); } // begin inorder traversal public void InorderTraversal () { lock ( this ) { InorderHelper ( root ); } } // recursive method to perform inorder traversal private void InorderHelper ( TreeNode node ) { if ( node == null ) return; // traverse left subtree InorderHelper ( node . LeftNode ); // output node data Console . Write ( node . Data + " " ); // traverse right subtree InorderHelper ( node . RightNode ); } // begin postorder traversal public void PostorderTraversal () { lock ( this ) { PostorderHelper ( root ); } } // recursive method to perform postorder traversal private void PostorderHelper ( TreeNode node ) { if ( node == null ) return; // traverse left subtree PostorderHelper ( node . LeftNode ); // traverse right subtree PostorderHelper ( node . RightNode ); // output node data Console . Write ( node . Data + " " ); } } // end class Tree } + Multi-Zitat Zitieren