Bag o' Strings


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Bag o' Strings

  1. #1
    Join Date
    Nov 2004
    Location
    Northern CA
    Posts
    17

    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

  2. #2
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560

    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

  3. #3
    Join Date
    Nov 2004
    Location
    Northern CA
    Posts
    17
    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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center