LearningJava
asked on
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(da ta) < 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;
}
}
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(da
{ 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;
}
}
Can you post the assignment spec verbatim?
ASKER
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.
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.
did you try my suggestion?
ASKER
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 ?
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 ?
>> 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
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
ASKER
>>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?
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?
>> 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
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
ASKER
>> 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?
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?
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)
ASKER
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?
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?
ASKER
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?
Can someone tutor/help me(give me hints) without directly giving me the answer?
ASKER
Anyone out there?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks.
But next time do not give me the answer. Just help me understand the code. So that I can find the answer myself.
But next time do not give me the answer. Just help me understand the code. So that I can find the answer myself.
if (root == null) return null;
Node result = root;
while (result.left != null)
result = result.left;
return result.data;
}