?
Solved

Question for CEHJ - Binary Search Trees

Posted on 2003-03-17
15
Medium Priority
?
399 Views
Last Modified: 2012-03-15
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;
   }
}
0
Comment
Question by:LearningJava
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 6
15 Comments
 
LVL 9

Expert Comment

by:Venci75
ID: 8151578
Comparable smallest() {
  if (root == null) return null;
  Node result = root;
  while (result.left != null)
    result = result.left;
  return result.data;
}
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 8153138
Can you post the assignment spec verbatim?
0
 

Author Comment

by:LearningJava
ID: 8156987
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 9

Expert Comment

by:Venci75
ID: 8157375
did you try my suggestion?
0
 

Author Comment

by:LearningJava
ID: 8158853
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
 
LVL 9

Expert Comment

by:Venci75
ID: 8158910
>> 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
 

Author Comment

by:LearningJava
ID: 8159030
>>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
 
LVL 9

Expert Comment

by:Venci75
ID: 8159093
>> 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
 

Author Comment

by:LearningJava
ID: 8159185
>> 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
 
LVL 9

Expert Comment

by:Venci75
ID: 8159225
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
 

Author Comment

by:LearningJava
ID: 8160395
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
 

Author Comment

by:LearningJava
ID: 8163016
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
 

Author Comment

by:LearningJava
ID: 8163741
Anyone out there?
0
 
LVL 9

Accepted Solution

by:
Venci75 earned 1000 total points
ID: 8164838
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
 

Author Comment

by:LearningJava
ID: 8166138
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

Featured Post

Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question