[Python] BinaryTree (binärer Suchbaum)

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

Schlagworte:
  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen
  1. #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
     
    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
     

  2. Anzeige
  3. #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 :D

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

     
  4. #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
     
  5. #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 <=  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
    }
     

  6. Videos zum Thema
Die Seite wird geladen...
Similar Threads - Python BinaryTree binärer
  1. Antworten:
    4
    Aufrufe:
    610
  2. Antworten:
    2
    Aufrufe:
    3.761
  3. Antworten:
    7
    Aufrufe:
    2.001
  4. Antworten:
    0
    Aufrufe:
    1.636
  5. Antworten:
    1
    Aufrufe:
    1.021