[Python] BinaryTree (binärer Suchbaum)

Dieses Thema im Forum "Projekte / Codes" wurde erstellt von cable, 10. Februar 2010 .

Schlagworte:
  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
  3. 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
  4. 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
  5. 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
  6. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.

Auf dieses Thema antworten