Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Binary Search Tree

  1. #1
    Junior Member
    Join Date
    Jan 2011
    Posts
    13
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Binary Search Tree

    hi, I'm new to this forum, so first of all I think I should introduce myself, hi I'm lex.... So basically the other day I was given the following assignment: 'Given the following interface (BST) and the following class (BSTNode), create your very own Binary Search Tree implementation'.

    public final class BSTNode {
        private int key;
        private String value;
        private BSTNode left;
        private BSTNode right;
     
        public BSTNode() {
        }
     
        public int getKey() {
            return key;
        }
     
        public void setKey(int key) {
            this.key = key;
        }
     
        public BSTNode getLeft() {
            return left;
        }
     
        public void setLeft(BSTNode left) {
            this.left = left;
        }
     
        public BSTNode getRight() {
            return right;
        }
     
        public void setRight(BSTNode right) {
            this.right = right;
        }
     
        public String getValue() {
            return value;
        }
     
        public void setValue(String value) {
            this.value = value;
        }
     
        @Override
        public String toString() {
            return "<" + key + "=" + value + ">";
        }
    }
     
    public class BSTImpl implements BST{
     
        private BSTNode root;
     
        public  BSTImpl(){
            root=null;
        }
     
        private String findRic(int key, BSTNode node){
            if(node==null) return null;
            if(node.getKey()==key) return node.getValue();
            if(key<node.getKey()) return findRic(key, node.getLeft());
            else return findRic(key, node.getRight());
        }
     
        public String find(int key) {
           return findRic(key, root);
        }
     
        private void findAllRic(int key, BSTNode node, List list){
            if(node==null) return;
            if(node.getKey()==key){
                list.add(node.getValue());
                findAllRic(key,node.getRight(),list);
            }
            if(key<node.getKey()) findAllRic(key, node.getLeft(), list);
            else findAllRic(key, node.getRight(), list);
        }
     
        public List<String> findAll(int key) {
            List result = new LinkedList();
            findAllRic(key,root,result);
            return result;
        }
     
        private void insertIfAintEmpty(int key, String value, BSTNode node){
            if(key>=node.getKey()){
                if(node.getRight()==null){
                    BSTNode child = new BSTNode();
                    child.setKey(key);
                    child.setValue(value);
                    node.setRight(child);
                }
                else insertIfAintEmpty(key,value,node.getRight());
            }
            else{
                if(node.getLeft()==null){
                    BSTNode child = new BSTNode();
                    child.setKey(key);
                    child.setValue(value);
                    node.setLeft(child);
                }
                else insertIfAintEmpty(key,value,node.getLeft());
            }
        }
     
        public void insert(int key, String value) {
            if(root==null){
                BSTNode node=new BSTNode();
                node.setKey(key);
                node.setValue(value);
                root=node;
            }
            else insertIfAintEmpty(key,value,root);
        }
     
        public boolean isEmpty() {
            return root==null;
        }
     
        public BSTNode root() {
            return root;
        }
     
        private int sizeRic(BSTNode node){
            if(node==null) return 0;
            else return 1 + sizeRic(node.getLeft()) + sizeRic(node.getRight());
        }
     
        public int size() {
            return sizeRic(root);
        }
     
        private void removeIt(int key, BSTNode node) {
            BSTNode temp=root;
            while(temp.getKey()>key){
                temp=node.getLeft();
            }
            root=temp;
        }
     
        private int min(int key, BSTNode node){
            while(node.getLeft()!=null){
                node=node.getLeft();
            }
            return node.getKey();
        }
     
        private void removeRic(int key, BSTNode node){
            if(node==null) return;
            if(node.getLeft().getKey()>key) removeRic(key, node.getLeft());
            if(node.getRight().getKey()>key && node.getRight()!=null){
               node.setRight(node.getRight().getLeft());
            }
            if(node.getRight().getKey()<key) removeRic(key, node.getRight());
    }
     
        public void removeHigh(int k) {
            removeRic(key,root);
        }
     
        private int max(int key, BSTNode node) {
             while(node.getRight()!=null){
                node=node.getRight();
            }
            return node.getKey();
        }
     
        public void print(){
            printRic(root);
        }
     
        private void printRic(BSTNode node){
            if(node.getLeft()!=null) printRic(node.getLeft());
            System.out.println(node);
            if(node.getRight()!=null) printRic(node.getRight());
        }
     
    }
     
    import java.util.*;
     
    public interface BST{
     
        public String find(int key);
     
        public List<String> findAll(int key);
     
        public void insert(int key, String value);
     
        public boolean isEmpty();
     
        public BSTNode root();
     
        public int size();
     
        public void removeHigh(int k);
    }

    What I am really having a problem with is removeHigh which is supposed to remove any nodes whose key's greater than k, only thing is I've always been bad at deletions especially when it comes to trees... any help would be immensely appreciated


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,529
    My Mood
    Hungover
    Thanks
    144
    Thanked 647 Times in 552 Posts

    Default Re: Binary Search Tree

    What are you having trouble with? What did you try? What worked, what didn't work? How didn't it work? Be specific. Saying "I'm bad at this" doesn't really give us much to go off.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Junior Member
    Join Date
    Jan 2011
    Posts
    13
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree

    Quote Originally Posted by KevinWorkman View Post
    What are you having trouble with? What did you try? What worked, what didn't work? How didn't it work? Be specific. Saying "I'm bad at this" doesn't really give us much to go off.
    It all goes smooth except for removeHigh... which doesn't seem to do anything...

    here's the tester I used


     public static void main(String[] x){
            BSTImpl dic = new BSTImpl();
            dic.insert(3, "3");
            dic.insert(2, "2");
            dic.insert(5, "5");
            dic.insert(4, "4");
            dic.insert(6, "6");
            dic.insert(1, "1");
            dic.removeHigh(1);
            dic.print();
            System.out.println(dic.size());

    what it does is it removes 5 and 6

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,529
    My Mood
    Hungover
    Thanks
    144
    Thanked 647 Times in 552 Posts

    Default Re: Binary Search Tree

    Well what does removeRic() do? I would presume that simply calling that method from your removeHigh() method will not be enough.

    Think about how you would do this "by hand" without any code. Write out the steps in English, and then translating that to code will be much easier.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Binary Search Tree in Java [HELP]
    By alan in forum Algorithms & Recursion
    Replies: 2
    Last Post: February 5th, 2011, 06:44 AM
  2. Need help fixing Binary Search Tree code
    By fistpunch in forum What's Wrong With My Code?
    Replies: 6
    Last Post: December 6th, 2010, 11:22 AM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 04:58 AM
  4. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 01:23 AM

Tags for this Thread