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

In summary: Child's constructor omitted for brevity this.rightChild = null; } getWeight() { return this.data.getWeight(); } setWeight(int weight) { this.data.setWeight(weight); } } Node.switchSortCriteria(String criterion) { Node leftChild = null; Node rightChild = null;
  • #1
Smiles1
8
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
  • #2
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.
 
  • #3
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? :)
 
  • #4
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);
   }
}
 

1. How does a Binary Search Tree (BST) work?

A BST is a data structure that organizes data in a binary tree format. Each node in the tree has at most two child nodes, a left child and a right child. The left child contains data that is smaller than the parent node's data, while the right child contains data that is larger. This allows for efficient searching, insertion, and deletion of data.

2. How do you sort a BST by name?

To sort a BST by name, you would need to traverse the tree in an in-order traversal, which visits the left subtree first, then the root node, and finally the right subtree. During the traversal, you would need to compare the names of each node and swap them if necessary to maintain the alphabetical order. This process is repeated for each node in the tree until the entire tree is sorted.

3. How do you sort a BST by weight?

Sorting a BST by weight is similar to sorting by name. However, instead of comparing the names of the nodes, you would compare their weights. During the in-order traversal, if the weight of a node is greater than its parent node, you would swap them to maintain the order of ascending weight. This process is repeated for each node in the tree until the entire tree is sorted.

4. What is the time complexity of sorting a BST by name or weight?

The time complexity of sorting a BST by name or weight is O(n), where n is the number of nodes in the tree. This is because the sorting process involves traversing the entire tree and comparing each node, which takes linear time.

5. Are there any other ways to sort a BST besides in-order traversal?

Yes, there are other ways to sort a BST, such as pre-order and post-order traversals. However, these traversals do not produce a sorted list in the same way as in-order traversal. They can be used to sort the tree in different ways, such as by depth or by level, but they may not result in a fully sorted list according to a specific criterion like name or weight.

Similar threads

MHB Java- CompareTo with Binary Search Tree
    • Programming and Computer Science
Replies
3
Views
3K
Java Tree Map always gets initialised but shouldn't, why is that?
    • Programming and Computer Science
Replies
4
Views
832
MHB Java- How to allow access to a different GUI menu for Learner and Admin
    • Programming and Computer Science
Replies
1
Views
1K
MHB Updating an index variable in Java
    • Programming and Computer Science
Replies
1
Views
2K
Create a binary search tree in python with the support of variables
    • Programming and Computer Science
Replies
13
Views
4K
MHB Shopping cart object problems using methods, and arrays no arrayLists. java
    • Programming and Computer Science
Replies
2
Views
2K
Can someone code review my "Distance between nodes in a BT"?
    • Programming and Computer Science
Replies
3
Views
890
Java Java. Searching and sorting a stack
    • Programming and Computer Science
Replies
5
Views
4K
An array problem involving a recursive binary search
    • Engineering and Comp Sci Homework Help
Replies
18
Views
1K
Java Android Studio: Accessing SQLite Data In RecyclerView
    • Programming and Computer Science
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top