-
Bag o' Strings
I would like someone to take a peek at my code, and perhaps add some constructive criticisms.
Problem: Write a class for a bag of strings, where the strings are stored in a binary search tree. In creating the binary search tree, you should use the string's compareTo method, which is described on page 480. The tree itself should use the BTNode class from figure 9.10 on page 471. (Main's book, Data Structures and Other Objects Using Java).
Now, I realize that you probably don't have the book, but can someone at least let me know if I'm on the right track "criteria-wise"?
I think the only things I've left out are the public static IntBTNode union (IntBTNode b1, IntBTNode b2) and the public boolean remove methods since I'm not quite sure how to implement them yet.
Thanks in advance!
hareless
Code:
public class BTNode
{
private Object item; //instance variable
private BTNode left; //instance variables
private BTNode right; //instance variables
public BTNode() //constructor
{
this(null, null, null);
}
/*============================================================*/
public BTNode(Object item) //constructor
{
setItem(item);
setLeft(left);
setRight(right);
}
/*============================================================*/
public BTNode(Object item, BTNode left, BTNode right) //constructor
{
setItem(item);
setLeft(left);
setRight(right);
}
/*============================================================*/
public void setItem(Object item) //constructor
{
this.item = item;
}
/*============================================================*/
public void setLeft(BTNode left) //constructor
{
this.left = left;
}
/*============================================================*/
public void setRight(BTNode right) //constructor
{
this.right = right;
}
/*============================================================*/
public void setLeft(Object newItem) //overloaded method (Polymorphism)
{
left = new BTNode(newItem);
}
/*============================================================*/
public void setRight(Object newItem)//overloaded method (Polymorphism)
{
right = new BTNode(newItem);
}
/*============================================================*/
public Object getItem() //accessor method
{
return item;
}
/*============================================================*/
public BTNode getLeft() //accessor methods
{
return left;
}
/*============================================================*/
public BTNode getRight() //accessor methods
{
return right;
}
/*============================================================*/
public boolean isLeaf()
{
return ( left == null && right == null );
}
/*============================================================*/
public BTNode getLeftMostNode()
{
if(this == null)
return null;
BTNode tempNode = this;
while(tempNode.left != null)
tempNode = tempNode.left;
return tempNode;
}
/*============================================================*/
public BTNode getRightMostNode()
{
if(this == null)
return null;
BTNode tempNode = this;
while(tempNode.right != null)
tempNode = tempNode.right;
return tempNode;
}
/*============================================================*/
public void insertLeft(Object newItem)
{
left = new BTNode(newItem);
}
public void insertRight(Object newItem)
{
right = new BTNode(newItem);
}
/*============================================================*/
public void removeLeftMostNode()
{
BTNode tempNode = this;
if(tempNode == null)
return;
BTNode leftNode = getLeftMostNode();
while(tempNode.left != leftNode)
tempNode = tempNode.left;
tempNode.left = null;
}
/*============================================================*/
public void removeRightMostNode()
{
BTNode tempNode = this;
if(tempNode == null)
return;
BTNode rightNode = getRightMostNode();
while(tempNode.right != rightNode)
tempNode = tempNode.right;
tempNode.right = null;
}
/*============================================================*/
//Recursive print In-order, which prints the left subtree,
//then the root, and then the right subtree.
public void printInOrder()
{
if( this != null)
printInOrder(this);
}
/*============================================================*/
//Utility method for printPreOrder()
private void printInOrder(BTNode node)
{
if( node == null) return;
printInOrder(node.left);
System.out.print(node.item + " ");
printInOrder(node.right);
}
/*============================================================*/
//Recursive print post-order, which prints the left subtree,
//then the right subtree, and then the root.
public void printPostOrder()
{
if( this != null)
printPostOrder(this);
}
/*============================================================*/
//Utility method for printPreOrder()
private void printPostOrder(BTNode node)
{
if( node == null) return;
printPostOrder(node.left);
printPostOrder(node.right);
System.out.print(node.item + " ");
}
/*============================================================*/
//Recursive print pre-order, which prints the root,
//then the right subtree, and then the right subtree.
public void printPreOrder()
{
if( this != null)
printPreOrder(this);
}
/*============================================================*/
// Utility method for printPreOrder()
private void printPreOrder(BTNode node)
{
if( node == null) return;
printPreOrder(node.left);
printPreOrder(node.right);
System.out.print(node.item + " ");
}
/*============================================================*/
public void add(IntBTNode element)
{
IntBTNode cursor = root;
boolean done = false;
if(size() == 0)
root = new BTNode(element,null,null);
else
{
while (done == false)
{
if(element.compareTo(cursor.getData())<=0)
{
if(cursor.getLeft()== null)
{
cursor.setLeft(new StringBTNode(element, null,null));
done = true;
}
else cursor = cursor.getLeft();
}
else
{
if(cursor.getRight()== null)
{
cursor.setRight(new StringBTNode(element, null,null));
done = true;
}
else cursor = cursor.getRight();
}
}
}
}
/*============================================================*/
public void addAll(IntTreeBag addend)
{
IntBTNode addroot = addend.getRoot();
if (root == addend.root)
{
addroot = IntBTNode :: treeCopy(addend, root);
addTree(addroot);
}
else
addTree(addend.root);
}
/*============================================================*/
private void addTree(IntBTNode addroot)
{
add(adroot.getData());
if(addroot.getLeft() != null)
addTree(addroot.getLeft());
if(addroot.getRight() != null)
addTree(addroot.getRight());
}
}
nicomen
-
Ok, I saw a couple of things
I have just had a quick scan of the code and it looks like its just missing
the last 5 %. I have put my remarks like this <===.
There is just couple of things that puzzles me in this code:
if (this != null)
Im trying to grasp that boolean expression logically, but I can't, can you ?
I think what you really want to do is to check the existence of a node
instance, but you can't do that in one of the non-existing objects
methods...
and the missing method you mention:
public static IntBTNode union (IntBTNode b1, IntBTNode b2)
I have never heard of a static <type> union in java before, is it
something new in java 1.5 or is it "leftovers" from the bloated hybrid
called C++ ?
Code:
public class BTNode {
private Object item; //instance variable
private BTNode left; //instance variables
private BTNode right; //instance variables
public BTNode() { //constructor
this(null, null, null); // <=== not required, null by defaulr
}
/*============================================================*/
public BTNode(Object item) { //constructor
setItem(item);
setLeft(left); // <=== not required
setRight(right); // <=== not required
}
/*============================================================*/
public BTNode(Object item, BTNode left, BTNode right) { //constructor
setItem(item);
setLeft(left);
setRight(right);
}
/*============================================================*/
public void setItem(Object item) { //constructor // <== no, its a setter
this.item = item;
}
/*============================================================*/
public void setLeft(BTNode left) { //constructor // <== no, its a setter
this.left = left;
}
/*============================================================*/
public void setRight(BTNode right) { //constructor // <== no, its a setter
this.right = right;
}
/*============================================================*/
public void setLeft(Object newItem) { //overloaded method (Polymorphism)
left = new BTNode(newItem);
}
/*============================================================*/
public void setRight(Object newItem) {
right = new BTNode(newItem);
}
/*============================================================*/
public Object getItem() { //accessor method
return item;
}
/*============================================================*/
public BTNode getLeft() { //accessor methods
return left;
}
/*============================================================*/
public BTNode getRight() { //accessor methods
return right;
}
/*============================================================*/
public boolean isLeaf() {
return (left == null && right == null);
}
/*============================================================*/
public BTNode getLeftMostNode() {
if (this == null)
return null;
BTNode tempNode = this;
while (tempNode.left != null)
tempNode = tempNode.left;
return tempNode;
}
/*============================================================*/
public BTNode getRightMostNode() {
if (this == null)
return null;
BTNode tempNode = this;
while (tempNode.right != null)
tempNode = tempNode.right;
return tempNode;
}
/*============================================================*/
public void insertLeft(Object newItem) {
left = new BTNode(newItem);
}
public void insertRight(Object newItem) {
right = new BTNode(newItem);
}
/*============================================================*/
public void removeLeftMostNode() {
BTNode tempNode = this;
if (tempNode == null)
return;
BTNode leftNode = getLeftMostNode();
while (tempNode.left != leftNode)
tempNode = tempNode.left;
tempNode.left = null;
}
/*============================================================*/
public void removeRightMostNode() {
BTNode tempNode = this;
if (tempNode == null)
return;
BTNode rightNode = getRightMostNode();
while (tempNode.right != rightNode)
tempNode = tempNode.right;
tempNode.right = null;
}
/*============================================================*/
//Recursive print In-order, which prints the left subtree, //then the root, and then the right subtree.
public void printInOrder() {
if (this != null)
printInOrder(this);
}
/*============================================================*/
//Utility method for printPreOrder()
private void printInOrder(BTNode node) {
if (node == null)
return;
printInOrder(node.left);
System.out.print(node.item + " ");
printInOrder(node.right);
}
/*============================================================*/
//Recursive print post-order, which prints the left subtree, //then the right subtree, and then the root.
public void printPostOrder() {
if (this != null)
printPostOrder(this);
}
/*============================================================*/
//Utility method for printPreOrder()
private void printPostOrder(BTNode node) {
if (node == null)
return;
printPostOrder(node.left);
printPostOrder(node.right);
System.out.print(node.item + " ");
}
/*============================================================*/
//Recursive print pre-order, which prints the root,
//then the right subtree, and then the right subtree.
public void printPreOrder() {
if (this != null)
printPreOrder(this);
}
/*============================================================*/
// Utility method for printPreOrder()
private void printPreOrder(BTNode node) {
if (node == null)
return;
printPreOrder(node.left);
printPreOrder(node.right);
System.out.print(node.item + " ");
}
/*============================================================*/
public void add(IntBTNode element) {
IntBTNode cursor = root;
boolean done = false;
if (size() == 0)
root = new BTNode(element, null, null);
else {
while (done == false) {
if (element.compareTo(cursor.getData()) <= 0) {
if (cursor.getLeft() == null) {
cursor.setLeft(new StringBTNode(element, null, null));
done = true;
}
else
cursor = cursor.getLeft();
}
else {
if (cursor.getRight() == null) {
cursor.setRight(new StringBTNode(element, null, null));
done = true;
}
else
cursor = cursor.getRight();
}
}
}
}
/*============================================================*/
public void addAll(IntTreeBag addend) {
IntBTNode addroot = addend.getRoot();
if (root == addend.root) {
addroot = IntBTNode :: treeCopy(addend, root); // <==this is C+++
addTree(addroot);
}
else
addTree(addend.root);
}
/*============================================================*/
private void addTree(IntBTNode addroot) {
add(adroot.getData());
if (addroot.getLeft() != null) {
addTree(addroot.getLeft());
}
if (addroot.getRight() != null)
addTree(addroot.getRight());
}
}
Last edited by sjalle; 05-16-2005 at 07:47 AM.
eschew obfuscation
-
First, thanks for taking the time to look at my code. I truly appreciate it!
Answering your question
There is just couple of things that puzzles me in this code:
if (this != null)
Im trying to grasp that boolean expression logically, but I can't, can you ?
I think what you really want to do is to check the existence of a node
instance, but you can't do that in one of the non-existing objects
methods...
I'm not sure, I think I may have put some extraneous code in there as I was doing it over...and over...and over *grin*. Thanks for pointing that out, however.
The other question you had
I have never heard of a static <type> union in java before, is it something new in java 1.5 or is it "leftovers" from the bloated hybrid called C++ ?
You may be right since I think the author rewrote this textbook for Java, and I've found a few things that look suspiciously C++. Hmmm...I'll fix it.
Thanks again for you time!
nicomen
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
Forum Rules
|
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL
|
Reply With Quote
Bookmarks