MHB Binary Search Tree - Sort the same BSTree by name or by weight

AI Thread Summary
The discussion revolves around implementing a binary search tree (BST) that can sort dog objects by either name or weight. The user has successfully created methods to delete, retrieve weights, and sort the tree, but encounters issues when switching sorting criteria. Specifically, sorting by name first leads to incorrect weight ordering when switching to weight sorting. To resolve this, the user considers whether they need to reset the tree and re-add the dog objects each time the sorting criteria change. They seek a more efficient method to reorganize the tree without starting from scratch. Ultimately, the user finds a solution by transferring the data into an ArrayList, resetting the tree, and re-adding the data based on the selected criteria. Additionally, suggestions are made to enhance the BST implementation, such as creating separate trees for each sorting criterion or adding a field to manage sorting order within the same tree. This approach could simplify the management of sorting without needing to reset the entire tree each time.
Smiles1
Messages
7
Reaction score
0
I've tackled a lot so far! I've created methods to delete, get the weight, and sort the tree by name.

My goal is to have my switch criteria change how the tree is sorted, either by weight or by name.
I haven't figured out how to implement it within my switchCriteria() method, so I've been trying to use my addDogObject() method to sort them as they are added to the tree.

When I run my program and enter to sort by weight first, all of my numbers are sorted correctly.
However, if I sort by name first, then sort by weight, all of the weights are ordered incorrectly?

This makes me think that my name sort is incorrect.

How can I reassemble each node in my tree to be sorted by name, and then by weight and vice versa?
Would I need to reset the tree to null each time and then add in the dog objects again?

Is there way to do this without adding all the objects in again and starting from scratch each time?

I'm currently looking through Big Java Late Objects but can't find a solution that makes sense with what I have currently.

App:
Code: 
import java.util.Scanner;public class App {

    public static void main(String[] args) {
        BSTree dogOTree = new BSTree();
        Scanner scan = new Scanner(System.in);
        System.out.println("Sort by! name || weight ?");
        String criteria = scan.nextLine();
        
        dogOTree.switchSortCriteria(criteria);
        Dog dogO1 = new Dog("Jackson", 65.28);
        Dog dogO2 = new Dog("Tick", 69.88);
        Dog dogO3 = new Dog("Nia", 75.44);
        //Layla is my dog! She was named after the Eric Clapton song.
        Dog dogO4 = new Dog("Layla", 32.02);
        Dog dogO5 = new Dog("Bagel", 21.06);
        Dog dogO6 = new Dog("Milo", 24.73);
        //Populate DogOTree
        dogOTree.addDogObject(dogO1);
        dogOTree.addDogObject(dogO2);
        dogOTree.addDogObject(dogO3);
        dogOTree.addDogObject(dogO4);
        dogOTree.addDogObject(dogO5);
        dogOTree.addDogObject(dogO6);
        dogOTree.addDogInfo("Baconater", 33.44);
        dogOTree.addDogInfo("FoodBurgular", 22.32);
        dogOTree.addDogInfo("SnackSnatcher", 66.92);
        dogOTree.addDogInfo("ActuallyABlowHorn", 88.26);
        dogOTree.addDogInfo("Clifford", 555.02);

        System.out.println("Sorted by" + criteria);
        dogOTree.displayInOrder();
        //Testing .containsDog()
        System.out.println("Exists: " + dogOTree.containsDog("Layla"));
        System.out.println("Exists: " + dogOTree.containsDog("NonexistantDogO"));
        //Delete successful
        //dogOTree.deleteDog(dogO4);
        //System.out.println("List without DogO4, Baconater");
        //dogOTree.displayInOrder();
        //getDogWeight() successful
        System.out.println(dogOTree.getDogWeight("Layla"));
        System.out.println(dogOTree.getDogWeight("Nia"));
        System.out.println(dogOTree.getDogWeight("Clifford"));
        System.out.println(dogOTree.getDogWeight("Jackson"));
        System.out.println(dogOTree.getDogWeight("Non-existantDogO"));
        
        System.out.println("Sort by! name || weight ?");
        criteria = scan.nextLine();

        dogOTree.switchSortCriteria(criteria);
        dogOTree.displayInOrder();   
  
       
        //getDogWeight() successful
        System.out.println(dogOTree.getDogWeight("Layla"));
        System.out.println(dogOTree.getDogWeight("Nia"));
        System.out.println(dogOTree.getDogWeight("Clifford"));
        System.out.println(dogOTree.getDogWeight("Jackson"));
        System.out.println(dogOTree.getDogWeight("Non-existantDogO"));
    }

}

BSTree:

Code: 
public class BSTree {

    class Node {

        private Dog data;
        private Node leftChild;
        private Node rightChild;

        Node(Dog data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    private Node root;
    private Node tempNode;
    private String criteria;

    public BSTree() {
        root = null;
        tempNode = null;
        criteria = "";
    }

    public boolean addDogObject(Dog data) {
        if(criteria.equalsIgnoreCase("weight")) {
        root = addRecursiveByWeight(root, data);
        }
        else if(criteria.equalsIgnoreCase("name")){
        root = addRecursiveByName(root, data);
        }
        return true;
    }
    //Adds a Dog object to the tree.  Returns true on success or false on failure (if Dog with that name already exists).

    public boolean addDogInfo(String name, double weight) {
        return this.addDogObject(new Dog(name, weight));
    }

    private Node addRecursiveByWeight(Node current, Dog data) {
        if (current == null) { // If it's root
            return new Node(data);
        } else if (data.getWeight() < current.data.getWeight()) { //navigate left
            //Vrrooom vrroom go left
            current.leftChild = addRecursiveByWeight(current.leftChild, data);
            return current;
        } else if (data.getWeight() > current.data.getWeight()) {
            current.rightChild = addRecursiveByWeight(current.rightChild, data);
            return current;
        } else {
            return current;
        }
    }

    private Node addRecursiveByName(Node current, Dog data) {
        if (current == null) {
            return new Node(data);
        } else if (data.getName().compareToIgnoreCase(current.data.getName()) < 0) { //navigate left
            //Vrrooom vrroom go left
            current.leftChild = addRecursiveByWeight(current.leftChild, data);
            return current;
        } else if (data.getName().compareToIgnoreCase(current.data.getName()) > 0) {
            current.rightChild = addRecursiveByWeight(current.rightChild, data);
            return current;
        } else {
            return current;
        }
    }

    public void switchSortCriteria(String userCriteria) {
        //Specifies whether your tree is sorted by the dog's name or weight. If the tree contains elements already, 
        //it will re-order those elements using the criteria specified.  The “criteria” parameter may be equal to “name” or “weight”.
//        if(criteria.equalsIgnoreCase("weight")){
//                      ///Silently screaming
//                      
//        }
//        else if(criteria.equalsIgnoreCase("name")){
//                      //Also silently screaming
//        }
          criteria = userCriteria;
    }

    public boolean containsDog(String name) {
        return containsRecursive(root, name);
        //Start at the root and looks for data
    }

    private boolean containsRecursive(Node current, String name) {
        if (current == null) {
            return false;
        }
        if (name.compareToIgnoreCase(current.data.getName()) == 0) {
            tempNode = current;
            return true;
        }

        boolean inLeft = containsRecursive(current.leftChild, name);

        if (!inLeft) {
            return (containsRecursive(current.rightChild, name));
        }
        return true;
    }    /*
    While node is not null 
    recursively traverse left child
    Display node's value
    recursively traverse right child
     */
    public void displayInOrder() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(" " + node.data);
            inOrderTraversal(node.rightChild);
        }
    }

    public double getDogWeight(String name) {
        //Returns the weight of the dog with the specified name if it exists in the tree, or returns -1 otherwise.
        if (containsRecursive(root, name) == true) {
            return tempNode.data.getWeight();
        } else {
            return -1;
        }

    }

    public void deleteDog(Dog data) {
        root = deleteRecursive(root, data);
    }

    private Node deleteRecursive(Node current, Dog data) {

        if (current == null) {
            return current;
        }

        if (data.getWeight() < current.data.getWeight()) {
            current.leftChild = deleteRecursive(current.leftChild, data);
        } else if (data.getWeight() > current.data.getWeight()) {
            current.rightChild = deleteRecursive(current.rightChild, data);
        } else {
            if (current.leftChild == null) {
                return current.rightChild;
            } else if (current.rightChild == null) {
                return current.leftChild;
            }

            current.data.setWeight(findMinVal(current.rightChild));
            current.rightChild = deleteRecursive(current.rightChild, current.data);
        }

        return current;
    }

    public double findMinVal(Node current) {
        double min = current.data.getWeight();

        while (current.leftChild != null) {
            min = current.leftChild.data.getWeight();
            current = current.leftChild;
        }
        return min;
    }
}

Dog class:

Code: 
public class Dog {
    private String name;
    private double weight;

    public Dog(String name, double weight) {
        this.name = name;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Dog {" + " name= " + name + ", weight= " + weight;
    }
    
}

Any help, hints or advice is greatly appreciated!
 
Technology news on Phys.org
This is solved! :-)

I transferred all of my data into an ArrayList, reset the tree, and then added the data back into the tree from the ArrayList using whichever criteria.
 
Smiles said:
This is solved! :-)

I transferred all of my data into an ArrayList, reset the tree, and then added the data back into the tree from the ArrayList using whichever criteria.

Hi Smiles!

Sorry we couldn't help you in time, but would you mind posting your solution so another person might benefit from it in the future? :)
 
Smiles,
A binary search tree is a binary tree together with ONE total ordering of the nodes. So with different orders for Dog data, you can't have just one binary search tree. Here's a solution that just adds a field orderByName (specifying the order for this tree) to BSTree; the compareTo method of Node is computed according to this orderByName.

Since you seem to be just now learning about trees, I've included several non-recursive methods in class BSTree. Certainly, recursion is a very good way to implement methods for trees, but I think non-recursive implementation aids the understanding.

Code: 
public class App {
   public static void main(String[] args) {
      BSTree nameTree = new BSTree(true);
      BSTree weightTree = new BSTree(false);

      nameTree.addDog("Jackson", 65.28);
      nameTree.addDog("Tick", 69.88);
      nameTree.addDog("Nia", 75.44);
      //Layla is my dog! She was named after the Eric Clapton song.
      nameTree.addDog("Layla", 32.02);
      nameTree.addDog("Bagel", 21.06);
      nameTree.addDog("Milo", 24.73);

      nameTree.displayInOrder();

      weightTree.addDog("Jackson", 65.28);
      weightTree.addDog("Tick", 69.88);
      weightTree.addDog("Nia", 75.44);
      //Layla is my dog! She was named after the Eric Clapton song.
      weightTree.addDog("Layla", 32.02);
      weightTree.addDog("Bagel", 21.06);
      weightTree.addDog("Milo", 24.73);

      weightTree.displayInOrder();

   }
   
}

Code: 
public class BSTree {
   boolean orderedByName;
   BSTree(boolean byName) {
      orderedByName = byName;
      root = null;
   }

   class Node {

      Dog data;
      Node leftChild;
      Node rightChild;

      Node(Dog data) {
         this.data = data;
         this.leftChild = null;
         this.rightChild = null;
      }

      public int compareTo(Dog t) {
         if (orderedByName) {
            return (t.getName().compareToIgnoreCase(data.getName()));
         }
         return ((int) (t.getWeight() - data.getWeight()));
      }

   }

    private Node root;
  
    
   public BSTree() {
      root = null;
   }

   public boolean add(Dog data) {
      if (contains(data)) {
         return (false);
      }
      Node ng = new Node(data);
      root = addRecursive(root, ng);
      return true;
   }
    
   // upon entry, no node of the tree has node.data == data
    private Node addRecursive(Node current, Node toAdd) {
      if (current == null) { // If it's root OR fell off the tree
         return (toAdd);
      } else if (current.compareTo(toAdd.data) < 0) { //navigate left
         //Vrrooom vrroom go left
         current.leftChild = addRecursive(current.leftChild, toAdd);
         return current;
      } else {
         current.rightChild = addRecursive(current.rightChild, toAdd);
         return current;
      }
   }

    
    public void displayInOrder() {
        inOrderTraversal(root);
    }

   private void inOrderTraversal(Node node) {
      if (node != null) {
         inOrderTraversal(node.leftChild);
         System.out.println(" " + node.data);
         inOrderTraversal(node.rightChild);
      }
   }
    //Adds a Dog object to the tree.  Returns true on success or false on failure (if Dog with that name already exists).
   public boolean addDog(String name, double weight) {
      return this.add(new Dog(name, weight));
   }
// returns true iff the tree contains a node with data t
   public boolean contains(Dog t) {
      if (root == null) {
         return (false);
      }
      Node p = root;
      int comp;
      while (p != null) {
         comp = p.compareTo(t);
         if (comp == 0) {
            return (true);
         }
         if (comp < 0) {
            p = p.leftChild;
         } else {
            p = p.rightChild;
         }
      }
      return (false);
   }
   
/* The following are two non-recursive binary tree traversal.  They both use
   a stack data structure.
   */    
   void preTrav() {
      ArrayDeque stk = new ArrayDeque();
      Node p;
      stk.push(root);
      while (!stk.isEmpty()) {
         p = (Node) stk.pop();
         System.out.println(p.data);
         if (p.rightChild != null) {
            stk.push(p.rightChild);
         }
         if (p.leftChild != null) {
            stk.push(p.leftChild);
         }
      }
   }
   
   void inTrav() {
      ArrayDeque stk = new ArrayDeque();
      Node p = root;
      while (true) {
         while (p != null) {
            stk.push(p);
            p = p.leftChild;
         }
         if (stk.isEmpty()) {
            break;
         }
         p = (Node) stk.pop();
         System.out.println(p.data);
         p = p.rightChild;
      }
   }
// Here's a non-recursive method that adds a node with data dg.   
   boolean insert(Dog dg) {
      Node ng = new Node(dg);
      Node p = root, q = null;
      int comp = 0;
      while (p != null) {
         q = p;
         comp = p.compareTo(dg);
         if (comp == 0) {
            return (false);  // already in tree
         }
         if (comp < 0) {
            p = p.leftChild;
         } else {
            p = p.rightChild;
         }
      }
      if (q == null) {
         root = ng;
      } else {
         if (comp < 0) {
            q.leftChild = ng;
         } else {
            q.rightChild = ng;
         }
      }
      return (true);
   }
// Here's the "standard" non-recursive method that deletes THE node with data dg.   
   boolean remove(Dog dg) {
      Node p = root, parentOfP = null, q, parentOfQ;
      int comp;
      boolean leftFromParent = true;
      while (p != null) {
         comp = p.compareTo(dg);
         if (comp == 0) {
            break;
         }
         if (comp < 0) {
            parentOfP = p;
            p = p.leftChild;
         } else {
            parentOfP = p;
            p = p.rightChild;
         }
         leftFromParent = comp < 0;
      }
      if (p == null) { // dg NOT in tree
         return (false);
      }
      if (p.rightChild != null) {
         q = p.rightChild;
         parentOfQ = null;
         while (q.leftChild != null) {
            parentOfQ = q;
            q = q.leftChild;
         }
         if (parentOfQ != null) {
            parentOfQ.leftChild = q.rightChild;
            q.rightChild = p.rightChild;
         }
         q.leftChild = p.leftChild;
      } else {
         q = p.leftChild;
      }
      if (parentOfP == null) {
         root = q;
      } else {
         if (leftFromParent) {
            parentOfP.leftChild = q;
         } else {
            parentOfP.rightChild = q;
         }
      }
      return (true);
   }
}
 

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Learning data structures and algorithms in different programming languages'

I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
View full post »

Similar threads

Java Java- CompareTo with Binary Search Tree
Replies
3
Views
4K
Java Java Tree Map always gets initialised but shouldn't, why is that?
Replies
4
Views
1K
Python Create a binary search tree in python with the support of variables
Replies
13
Views
4K
Java Java. Searching and sorting a stack
Replies
5
Views
4K
Printing a Binary Tree: Solving the Space Issue
Replies
8
Views
3K
C/C++ Find Nearest Record in Binary Search Tree | C++ Implementation
Replies
1
Views
7K
Why Are My AVL Tree Nodes Disappearing During Insertion?
Replies
0
Views
2K
Java Fix Java Linked List Output Issue & Error
Replies
1
Views
3K
C/C++ Code : Binary Search Tree C++
Replies
7
Views
75K
Java Android Studio: Accessing SQLite Data In RecyclerView
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top