java - How to print in alphabetical order from a Binary Search Tree? -


using bst class, able print out strings, cannot figure out how print them in alphabetical order. please help. need create method in bst class elements printed out in alphabetical order. thanks.

public class binarysearchtree<anytype extends comparable<? super anytype>>     {         /**          * construct tree.          */         private binarynode<anytype> root;         public binarysearchtree( )     {         root = null;     }      /**      * insert tree; duplicates ignored.      * @param x item insert.      */     public void insert( anytype x )     {         root = insert( x, root );     }      /**      * remove tree. nothing done if x not found.      * @param x item remove.      */     public void remove( anytype x )     {         root = remove( x, root );     }      /**      * find smallest item in tree.      * @return smallest item or null if empty.      */     public anytype findmin( )     {         if( isempty( ) )             throw new underflowexception("no elements found");         return findmin( root ).element;     }      /**      * find largest item in tree.      * @return largest item of null if empty.      */     public anytype findmax( )     {         if( isempty( ) )             throw new underflowexception("no elements found");         return findmax( root ).element;     }      /**      * find item in tree.      * @param x item search for.      * @return true if not found.      */     public boolean contains( anytype x )     {         return contains( x, root );     }      /**      * make tree logically empty.      */     public void makeempty( )     {         root = null;     }      /**      * test if tree logically empty.      * @return true if empty, false otherwise.      */     public boolean isempty( )     {         return root == null;     }      /**      * print tree contents in sorted order.      */     public void printtree( )     {         if( isempty( ) )             system.out.println( "empty tree" );         else             printtree( root );     }      /**      * internal method insert subtree.      * @param x item insert.      * @param t node roots subtree.      * @return new root of subtree.      */     private binarynode<anytype> insert( anytype x, binarynode<anytype> t )     {         if( t == null )             return new binarynode<anytype>( x, null, null );          int compareresult = x.compareto( t.element );          if( compareresult < 0 )             t.left = insert( x, t.left ); // if new item < x --> insert left         else if( compareresult > 0 )              t.right = insert( x, t.right ); //if new item > x ---> insert right         else             ;  // duplicate; nothing         return t;     }      /**      * internal method remove subtree.      * @param x item remove.      * @param t node roots subtree.      * @return new root of subtree.      */     private binarynode<anytype> remove( anytype x, binarynode<anytype> t )     {         if( t == null )             return t;   // item not found; nothing          int compareresult = x.compareto( t.element );          if( compareresult < 0 )             t.left = remove( x, t.left );         else if( compareresult > 0 )             t.right = remove( x, t.right );         else if( t.left != null && t.right != null ) // 2 children         {             t.element = findmin( t.right ).element;             t.right = remove( t.element, t.right );         }         else             t = ( t.left != null ) ? t.left : t.right;         return t;     }      /**      * internal method find smallest item in subtree.      * @param t node roots subtree.      * @return node containing smallest item.      */     private binarynode<anytype> findmin( binarynode<anytype> t )     {         if( t == null )             return null;         else if( t.left == null )             return t;         return findmin( t.left );     }      /**      * internal method find largest item in subtree.      * @param t node roots subtree.      * @return node containing largest item.      */     private binarynode<anytype> findmax( binarynode<anytype> t )     {         if( t != null )             while( t.right != null )                 t = t.right;          return t;     }      /**      * internal method find item in subtree.      * @param x item search for.      * @param t node roots subtree.      * @return node containing matched item.      */     private boolean contains( anytype x, binarynode<anytype> t )     {         if( t == null )             return false;          int compareresult = x.compareto( t.element );          if( compareresult < 0 )             return contains( x, t.left );         else if( compareresult > 0 )             return contains( x, t.right );         else             return true;    // match     }      /**      * internal method print subtree in sorted order.      * @param t node roots subtree.      */     private void printtree( binarynode<anytype> t )     {         if( t != null )         {             printtree( t.left );             system.out.println( t.element );             printtree( t.right );         }     }      /**      * internal method compute height of subtree.      * @param t node roots subtree.      */     private int height( binarynode<anytype> t )     {         if( t == null )             return -1;         else             return 1 + math.max( height( t.left ), height( t.right ) );         }      // node object stores element + left , right nodes of same type     //*********************************************new class*******************************************     private static class binarynode<anytype>     {             // constructors         binarynode( anytype theelement )         {             this( theelement, null, null );         }          binarynode( anytype theelement, binarynode<anytype> lt, binarynode<anytype> rt )         {             element  = theelement;             left     = lt;             right    = rt;         }          anytype element;            // data in node         binarynode<anytype> left;   // left child         binarynode<anytype> right;  // right child     }  } class underflowexception extends runtimeexception {     /**      * construct exception object.      * @param message error message.      */     public underflowexception( string message )     {         super( message );     } } 

when in-order traversal on bst, gives nodes in sorted order.

the idea in java-like pseudo code:

public void printsorted(node) {    if (node == null) return;    printsorted(node.left);    system.out.println(node.value); //or other manipulation of node    printsorted(node.right); } 

(p.s. better design suggested make recursive call method of binarynode<anytype>, , before recursing check if this.left == null , this.right == null, , recurse on them. pretty easy modify above pseudo code).


Comments

Popular posts from this blog

Payment information shows nothing in one page checkout page magento -

tcpdump - How to check if server received packet (acknowledged) -