Question for CEHJ - Binary Search Trees

Hi:
    I need to write a method of the Tree class Comparable smallest() that returns the smallest element of a tree. Can you help me get started(do not give me the answer)?

public class TreeTest
{  public static void main(String[] args)
   {  Tree staff = new Tree();
      staff.insert("Romeo");
      staff.insert("Juliet");
      staff.insert("Tom");
      staff.insert("Dick");
      staff.insert("Harry");

      staff.print();
   }
}

/**
   This class implements a binary search tree whose
   nodes hold objects that implement the Comparable
   interface.
*/

class Tree
{  /**
      Constructs an empty tree.
   */
   public Tree()
   {  root = null;
   }
   
   /**
      Inserts a new node into the tree.
      @param obj the object to insert
   */
   public void insert(Comparable obj)
   {  Node newNode = new Node();
      newNode.data = obj;
      newNode.left = null;
      newNode.right = null;
      if (root == null) root = newNode;
      else root.insertNode(newNode);
   }
   
   /**
      Prints the contents of the tree in sorted order.
   */
   public void print()
   {  if (root != null)
         root.printNodes();
   }
   
   /**
   Method to return the smallest element in a tree.
   @return
   */
   public Comparable smallest()
   {  
     return "something";
   }
   
 
   private Node root;

   private class Node
   {  /**
         Inserts a new node as a descendant of this node.
         @param newNode the node to insert
      */
      public void insertNode(Node newNode)
      {  if (newNode.data.compareTo(data) < 0)
         {  if (left == null) left = newNode;
            else left.insertNode(newNode);
         }
         else
         {  if (right == null) right = newNode;
            else right.insertNode(newNode);
         }
      }

      /**
         Prints this node and all of its descendants
         in sorted order.
      */
      public void printNodes()
      {  if (left != null)
            left.printNodes();
         System.out.println(data);
         if (right != null)
            right.printNodes();
      }
   
      public Comparable data;
      public Node left;
      public Node right;
   }
}
LearningJavaAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
Venci75Connect With a Mentor Commented:
check this method:
public void insertNode(Node newNode) {  
  if (newNode.data.compareTo(data) < 0) {  
    if (left == null) left = newNode;
    else left.insertNode(newNode);
  } else {  
    if (right == null) right = newNode;
    else right.insertNode(newNode);
  }
}
...
When you insert the smallest node - you will first get the bottom-left node of the tree and put a new 'left' child to it.

If you want two methods - in the Tree class and in the Node class - use something like this:
// Tree class
public Comparable smallest() {
    if (root == null) return null;
    else return root.smallest();
}
// Node class
public Comparable smallest() {
    if (left == null) return data;
    else return left.smallest();
}

 
0
 
Venci75Commented:
Comparable smallest() {
  if (root == null) return null;
  Node result = root;
  while (result.left != null)
    result = result.left;
  return result.data;
}
0
 
CEHJCommented:
Can you post the assignment spec verbatim?
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
LearningJavaAuthor Commented:
Hi CEHJ:

I have to write a method of the Tree class Comparable smallest() that returns the smallest element of a tree. Then I am told that I may also need to add a method to the Node class.

(Remember don't give me the the answer just help me)

Thanks.
0
 
Venci75Commented:
did you try my suggestion?
0
 
LearningJavaAuthor Commented:
I am trying to understand the code for the TreeTest program.

I can see that program uses the Comparable Interface but does not  use the Implement command. By declaring the data variable as Comparable; does the variable implement the interface? Or does it inherit the properities of Comparable?

Why does newNode.data = obj ?


0
 
Venci75Commented:
>> Why does newNode.data = obj
The tree nodes are instances of the Node class. Each node has corresponding Comparable object.

>> I can see that program uses the Comparable Interface but does not  use the Implement command

the objects that are added to the tree have to implement this interface - this is the only thing that the Tree class requires. The String class implements this interface - so - there is no problem to use this tree with strings
0
 
LearningJavaAuthor Commented:
>>the objects that are added to the tree have to implement >>this interface - this is the only thing that the Tree >>class requires. The String class implements this >>interface - so - there is no problem to use this tree >>with strings

Do you mean that the String class automatically implements the Comparable Interface and therefore I does need to use the implement command in the TreeTest program?

java.lang.String implements Comparable

>>The tree nodes are instances of the Node class. Each >>node has corresponding Comparable object.

So in order for the program to work both the node object and the data must be Comparable?

And both the node object and data are able to use Comparable because is a been implemented by the String class?



0
 
Venci75Commented:
>> Do you mean that the String class automatically implements the Comparable Interface and therefore I does need to use the implement command in the TreeTest program?

this code:
staff.insert("Romeo");

calls the insert command with a string object containing "Romeo". This is possible, because of the declaration of the String class as:
class java.lang.String implements Comparable
...

>> So in order for the program to work both the node object and the data must be Comparable?

no - the Node class does not need to implement Comparable - only the data object have to


0
 
LearningJavaAuthor Commented:
>> Why does newNode.data = obj
The tree nodes are instances of the Node class. Each node has corresponding Comparable object.

>> So in order for the program to work both the node object and the data must be Comparable?

no - the Node class does not need to implement Comparable - only the data object have to

What do mean by each Node has a Comparable object?
0
 
Venci75Commented:
the Tree.insert(Comparable) method actually adds a Node object to the tree. To the 'data' member of this node object is the Comparable that you are trying to insert (which in this case is String)
0
 
LearningJavaAuthor Commented:
Comparable smallest() {
 if (root == null) return null;
 Node result = root;
 while (result.left != null)
   result = result.left;
 return result.data;
}

I am not clear on how the above method finds the smallest element. Can you explain it to me?

0
 
LearningJavaAuthor Commented:
My master tell me that he wants two methods. One method in the Tree class and a helper method in the node class.

Can someone tutor/help me(give me hints) without directly giving me the answer?
0
 
LearningJavaAuthor Commented:
Anyone out there?
0
 
LearningJavaAuthor Commented:
Thanks.

But next time do not give me the answer. Just help me understand the code. So that I can find the answer myself.
0
All Courses

From novice to tech pro — start learning today.