tree sort

[bigdoggy]

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

[danielstoner]

I am not sure what you mean... ordered means sorted.

[Zosden]

by sort do you mean search.

[hardwired]

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

[bigdoggy]

Hi guys

Thanks for the replies. I have a class

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...?

[hardwired]

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