Loading:


Metoda sortowania - Sortowanie przez Drzewo - Tree Sort [JAVA]

Skrypt ukazuje jak wygląda oraz jak działa metoda sortowania typu Tree Sort (Sortowanie przez Drzewo). Kod ten można wykorzystać do sortowania liczb.



Napisz Artyku³

Listing

/*
 * Created on Nov 29, 2003
 */

package sorting;
import treeStructures.*;

/**
 * @author Funkcje.net
 */

public class SortowaniePrzezDrzewo {

        public void sortowanie(Comparable[] items) {
                BinarySearchTree tree = new BinarySearchTree();
                for (int i=0;i<items.length;i++)
                {
                        tree.insert(items[i]);
                }
                tree.inOrderTraverse(items);
        }

}

//kolejna klasa


package treeStructures;

/**
 * @author Funkcje.net
 */

public class BinarySearchTree {
        BinaryTreeNode root;
        int numberOfItems;
       
        public BinarySearchTree()
        {
                root=null;
                numberOfItems=0;
        }

        public void insert(Comparable object)
        {
                if (root==null)
                {
                        root=new BinaryTreeNode(object);
                } else {
                        insert(object,root);
                }
                numberOfItems++;
        }

    private void insert(Comparable object, BinaryTreeNode top)
    {
                if (top.compareTo(object)>0)
                {
                        if (top.getLeft()==null)
                        {
                                top.setLeft(new BinaryTreeNode(object));
                        } else {
                                insert(object,top.getLeft());
                        }
                } else {
                        if (top.getRight()==null)
                        {
                                top.setRight(new BinaryTreeNode(object));
                        } else {
                                insert(object,top.getRight());
                        }
                }
        }

    public boolean isEmpty()
    {
        return root==null;
    }
   
    public boolean remove(Comparable object)
    {
        if (retrieve(object)==null)
        {
                return false;
        }
        root = remove(object,root);
        if (retrieve(object)!=null)
        {
                numberOfItems--;
                return true;
        } else {
                return false;
        }
    }
   
   
        private BinaryTreeNode remove( Comparable x, BinaryTreeNode t )
        {
                if( t == null )
                        return t;   // rzecz nie znaleziona, wtedy nic nie robi
                if( x.compareTo( t.getData() ) < 0 )
                        t.setLeft (remove( x, t.getLeft() ));
                else if( x.compareTo( t.getData() ) > 0 )
                        t.setRight(remove( x, t.getRight() ));
                else if( t.getLeft() != null && t.getRight() != null ) // dwoje elementów
                {
                        t.setData( findMin( t.getRight() ).getData());
                        t.setRight( remove( t.getData(), t.getRight() ));
                }
                else
                        t = ( t.getLeft() != null ) ? t.getLeft() : t.getRight();
                return t;
        }

        private BinaryTreeNode findMin( BinaryTreeNode t )
        {
                if( t == null )
                        return null;
                else if( t.getLeft() == null )
                        return t;
                return findMin( t.getLeft() );
        }

        private BinaryTreeNode findMax( BinaryTreeNode t )
        {
                if( t != null )
                        while( t.getRight() != null )
                                t = t.getRight();
                return t;
        }



        private BinaryTreeNode retrieve(BinaryTreeNode cursor,
                                                                          Comparable element)
        {
                if ( cursor == null)
                {
                        return null;
                } else if (element.compareTo(cursor.getData()) < 0)
                {
                        return retrieve(cursor.getLeft(),element);
                } else if (element.compareTo(cursor.getData()) > 0)
                {
                        return retrieve(cursor.getRight(),element);
                } else {
                        return cursor;
                }
        }

        public Comparable retrieve (Comparable element)
        {
                BinaryTreeNode n = retrieve(root,element);
                if (n == null)
                {
                        return null;
                }
                return n.getData();
        }

        public String inOrderTraverse()
        {
                StringBuffer string=new StringBuffer();
                string=inOrderTraverse(root,string);
                return string.toString();
        }
       
        private StringBuffer inOrderTraverse(BinaryTreeNode node, StringBuffer string)
        {
                StringBuffer sb;
                if (node.getLeft() != null)
                {
                        inOrderTraverse(node.getLeft(),string);
                }
                sb=(StringBuffer) string.append(node.getData().toString()+"\n");
                if (node.getRight() != null)
                {
                        inOrderTraverse(node.getRight(),sb);
                }
                return sb;
        }
       
        public void inOrderTraverse(Comparable[] items)
        {
                if (items.length >= numberOfItems)
                {
                        inOrderTraverse(root,items,0);
                }
        }
       
        private int inOrderTraverse(BinaryTreeNode node,
                                                                 Comparable[] items,
                                                                 int location)
        {
                StringBuffer sb;
                int loc=location;
                if (node.getLeft() != null)
                {
                        loc=inOrderTraverse(node.getLeft(),items,location);
                }
                items[loc]=node.getData();
                loc++;
                if (node.getRight() != null)
                {
                        loc=inOrderTraverse(node.getRight(),items,loc);
                }
                return loc;
        }
       

        public String preOrderTraverse()
        {
                StringBuffer string=new StringBuffer();
                string=preOrderTraverse(root,string);
                return string.toString();
        }
       
        private StringBuffer preOrderTraverse(BinaryTreeNode node, StringBuffer string)
        {
                StringBuffer sb;
                if (node.getLeft() != null)
                {
                        inOrderTraverse(node.getLeft(),string);
                }
                sb=(StringBuffer) string.append(node.getData().toString()+"\n");
                if (node.getRight() != null)
                {
                        inOrderTraverse(node.getRight(),sb);
                }
                return sb;
        }

        public static void main (String[] args)
        {
                BinarySearchTree tree=new BinarySearchTree();
                String[] ints={"50","11","78","80","35",
                                           "63","04","16","22","60"};
                for (int i=0; i<ints.length;i++)
                {
                        tree.insert(ints[i]);   
                }
               
                System.out.println(tree.inOrderTraverse());
               
                tree.remove("50");
                System.out.println(tree.inOrderTraverse());
        }

}
 




Dodano przez: divix
Ranga: Administrator serwisu Punktów: 38523
Komentarze użytkowników
    • Tre¶æ komentarza
      Kod do komentarza (opcjonalnie)
      PHP JavaScript MySQL Smarty SQL HTML CSS ActionScript
      Autor
      Token
      token

       

       








funkcje.net
Wszelkie prawa zastrzeżone©. | Funkcje.net 2008-2024 v.1.5 | design: diviXdesign & rainbowcolors