Results 1 to 6 of 6

Thread: tree sort

  1. #1
    bigdoggy is offline Member
    Join Date
    Apr 2008
    Posts
    2
    Rep Power
    0

    Smile tree sort

    Hi guys,

    I need to use tree sort in order to sort through an ordered binary tree. I can't find any useful info on it and was looking for some pointers.

    Thanks in advance

  2. #2
    danielstoner's Avatar
    danielstoner is offline Senior Member
    Join Date
    Apr 2008
    Location
    Canada
    Posts
    191
    Rep Power
    7

    Default

    I am not sure what you mean... ordered means sorted.
    Daniel @ [www.littletutorials.com]
    Language is froth on the surface of thought

  3. #3
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default

    by sort do you mean search.
    My IP address is 127.0.0.1

  4. #4
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Here are a couple of possible resources:
    Scroll down to Section 4 on Binary Trees.
    Section 11.4 Binary Trees.

  5. #5
    bigdoggy is offline Member
    Join Date
    Apr 2008
    Posts
    2
    Rep Power
    0

    Default

    Hi guys

    Thanks for the replies. I have a class
    Java Code:
    import java.util.*;
    public class OBTComparable <T extends Comparable<T>>
    {				
      private T value;
      private OBTComparable left;
      private OBTComparable right;
      private boolean empty;
      //create an empty tree
      public OBTComparable()
      {
        setEmpty();
      }
      
      //make this tree into an empty tree
      private void setEmpty()
      {
        empty = true;
        value = null;
        left = null;
        right = null;
      }
      
      //see if this is an empty (sub)tree
      public boolean isEmpty()
      { return empty; }
      
      //get the value which is here
      public T getValue()
      { return value; }
      
      //get the left sub tree
      public OBTComparable getLeft()
      { return left; }
      
      //get the right sub tree
      public OBTComparable getRight()
      { return right; }
      
      //store a value in this position in the tree
      private void setValue(T requiredValue)
      {
        if(empty)
        {
          empty = false;
          left = new OBTComparable(); //makes new empty tree
          right = new OBTComparable(); //makes new empty tree
        }
        value = requiredValue;
      }
      
      //insert a value, allowing multiple instances
      public void insert(T insertValue)
      {
        if(empty)
          setValue(insertValue);
        else if(value.compareTo(insertValue)==1)
          left.insert(insertValue);
        else
          right.insert(insertValue);
      }
      
      public boolean find(T findValue)
      {
        if(empty)
          return false;
        else if(findValue==value)
          return true;
        else if(findValue.compareTo(value)==-1)
          return left.find(findValue);
        else
          return right.find(findValue);
      }
      
      public int getSize()
      {
        if(empty)
          return 0;
        else
          return (left.getSize() + 1 + right.getSize());
      }
      
      public int getDepth()
      {
        if(empty)
          return 0;
        else
        {
          int leftDepth = left.getDepth();
          int rightDepth = right.getDepth();
          if(leftDepth > rightDepth)
    	return leftDepth +1;
          else
    	return rightDepth +1;
        }
      }
      public Iterator elementsAscending()
      {
        ArrayList<T> elementsList = new ArrayList<T>();
        addElementsAscending(elementsList);
        return elementsList.iterator();
      }
      private void addElementsAscending(List elementsList)
      {
        if(!empty)
        {
          left.addElementsAscending(elementsList);
          elementsList.add(value);
          right.addElementsAscending(elementsList);
        }
      }
      
    }
    and now what I need to do is write a separate class which takes a list of strings from standard input and produce an ascending,sorted version of the list using tree sort, and I don't know how to use my class above combined with the tree sort...?

  6. #6
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java Code:
    import java.util.*;
    
    public class BTTest {
        public static void main(String[] args) {
            String[] strs = {
                "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
            };
            OBTComparable root = new OBTComparable();
            for(int i = 0; i < strs.length; i++) {
                root.insert(strs[i]);
            }
            Iterator elements = root.elementsAscending();
            while(elements.hasNext()) {
                System.out.print(elements.next() + " ");
            }
            System.out.println();
        }
    }
    
    class OBTComparable <T extends Comparable<T>>
    {				
        private T value;
        private OBTComparable left;
        private OBTComparable right;
        private boolean empty;
    
        //create an empty tree
        public OBTComparable()
        {
          setEmpty();
        }
    
        //make this tree into an empty tree
        private void setEmpty()
        {
            empty = true;
            value = null;
            left = null;
            right = null;
        }
    
        //see if this is an empty (sub)tree
        public boolean isEmpty()
        { return empty; }
    
        //get the value which is here
        public T getValue()
        { return value; }
    
        //get the left sub tree
        public OBTComparable getLeft()
        { return left; }
    
        //get the right sub tree
        public OBTComparable getRight()
        { return right; }
    
        //store a value in this position in the tree
        private void setValue(T requiredValue)
        {
            if(empty)
            {
                empty = false;
                left = new OBTComparable();  //makes new empty tree
                right = new OBTComparable(); //makes new empty tree
            }
            value = requiredValue;
        }
    
        //insert a value, allowing multiple instances
        public void insert(T insertValue)
        {
            insert(this, insertValue);
    /*
            if(empty)
                setValue(insertValue);
            else if(value.compareTo(insertValue)==1)
                left.insert(insertValue);
            else
                right.insert(insertValue);
    */
        }
    
        private void insert(OBTComparable<T> node, T insertValue)
        {
            if(node.isEmpty())
            {
                node.setValue(insertValue);
            }
            else
            {
                if(insertValue.compareTo(node.getValue()) < 0)
                    insert(node.left, insertValue);
                else
                    insert(node.right, insertValue);
            }
        }
    
        public boolean find(T findValue)
        {
            if(empty)
                return false;
            else if(findValue==value)
                return true;
            else if(findValue.compareTo(value)==-1)
                return left.find(findValue);
            else
                return right.find(findValue);
        }
    
        public int getSize()
        {
            if(empty)
                return 0;
            else
                return (left.getSize() + 1 + right.getSize());
        }
    
        public int getDepth()
        {
            if(empty)
                return 0;
            else
            {
                int leftDepth = left.getDepth();
                int rightDepth = right.getDepth();
                if(leftDepth > rightDepth)
                    return leftDepth +1;
                else
                    return rightDepth +1;
            }
        }
    
        public Iterator elementsAscending()
        {
            List<T> elementsList = new ArrayList<T>();
            addElementsAscending(elementsList);
            return elementsList.iterator();
        }
    
        private void addElementsAscending(List elementsList)
        {
            if(!empty)
            {
                left.addElementsAscending(elementsList);
                elementsList.add(value);
                right.addElementsAscending(elementsList);
            }
        }
    }

Similar Threads

  1. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 09:04 PM
  2. Need Help With Tree Adt
    By avi in forum New To Java
    Replies: 0
    Last Post: 03-20-2008, 04:11 AM
  3. Pakage tree
    By Thewhitelynx in forum New To Java
    Replies: 1
    Last Post: 03-17-2008, 03:53 AM
  4. Creating a tree
    By Preethi in forum AWT / Swing
    Replies: 0
    Last Post: 01-07-2008, 02:04 PM
  5. Tree controls using Swing
    By kabir in forum AWT / Swing
    Replies: 1
    Last Post: 01-05-2008, 10:48 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •