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 3 of 3

Thread: Binary Search Tree in Java [HELP]

  1. #1
    Junior Member
    Join Date
    Dec 2010
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Binary Search Tree in Java [HELP]

    Hi guys,
    This is a Java Implementation of Binary Search Tree
    import java.io.*;
     
    class node {
     
        int data;
        public node left;
        public node right;
     
        public node(int elem) {
            data = elem;
            left = null;
            right = null;
        }
    }
     
    public class bst {
     
        node root;
        int choice, left, right, elem;
        InputStreamReader ip;
        BufferedReader br;
        int parent;
     
        public bst() 
    	{
            choice = 0;
            root = null;
            ip = new InputStreamReader(System.in);
            br = new BufferedReader(ip);
        }
     
        public void input_element() {
            System.out.println("enter the element");
            try {
                String x = br.readLine();
                elem = Integer.parseInt(x);
            } catch (IOException e) {
                System.out.println("exception in input");
            }
        }
     
        public void inorder(node p) {
            if (p != null) {
                inorder(p.left);
                System.out.println(p.data);
                inorder(p.right);
            }
        }
     
        public void preorder(node p) {
            if (p != null) {
                System.out.println(p.data);
                preorder(p.left);
                preorder(p.right);
            }
        }
     
        public void postorder(node p) {
            if (p != null) {
                postorder(p.left);
                postorder(p.right);
                System.out.println(p.data);
            }
        }
     
        public node insert(node root) {
            if (root == null) {
                root = new node(elem);
            } else if (root.data < elem) {
                root.right = insert(root.right);
            } else if (root.data > elem) {
                root.left = insert(root.left);
            }
            return root;
        }
     
        public node delete(node root) {
            if (root != null) {
                if (root.data < elem) {
                    root.right = delete(root.right);
                } else if (root.data > elem) {
                    root.left = delete(root.left);
                } else if (root.left == null) {
                    root = root.right;
                } else if (root.right == null) {
                    root = root.left;
                } else {
                    elem = deletemin(root.right);
                    root.data = elem;
                    root.right = delete(root.right);
                }
                return root;
            }
            return root;
        }
     
        public int deletemin(node root) {
            if (root.left == null) {
                return root.data;
            } else {
                return deletemin(root.left);
            }
        }
     
        public void findparent(node root) {
            if (root == null) {
                parent = -1;
                return;
            }
            if (root.data == elem) {
                return;
            }
            parent = root.data;
            if (root.data > elem) {
                findparent(root.left);
            } else if (root.data < elem) {
                findparent(root.right);
            }
        }
     
        public void findchildren(node root) {
            if (root == null) {
                left = right = -1;
                return;
            }
            if (root.data == elem) {
                left = right = 0;
                if (root.left != null) {
                    left = root.left.data;
                }
                if (root.right != null) {
                    right = root.right.data;
                }
            }
            if (root.data > elem) {
                findchildren(root.left);
            } else if (root.data < elem) {
                findchildren(root.right);
            }
        }
     
        public void search() {
            parent = 0;
            input_element();
            findparent(root);
            if (parent != -1) {
                if (parent == 0) {
                    System.out.println(elem + "is present as the root node");
                } else {
                    System.out.println(elem + "is present as the child of" + parent);
                }
            }
        }
     
        public void findtype() {
            parent = 0;
            left = right = 0;
            input_element();
            findparent(root);
            if (parent != -1) {
                if (parent == 0) {
                    System.out.println(elem + "is the root node");
                    return;
                } else {
                    if (parent > elem) {
                        System.out.println(elem + "is present as left child of" + parent);
                    } else {
                        System.out.println(elem + "is present as the right child of " + parent);
                    }
                }
                if ((root.left == null) && (root.right == null)) {
                    System.out.println(elem + "is present as the leaf node");
                }
                if (root.left != null) {
                    System.out.println("left child is" + left);
                }
                if (root.right != null) {
                    System.out.println("rignt child is" + right);
                }
            }
        }
     
        public void getchoice() {
            System.out.println("menu\n");
            System.out.println("1.inser\n2.delete\n3.inorder\n4.preorder\n5.postorder\n6.find parent\n7.find node\n8.find type\n9.exit\n");
            System.out.println("enter the choice\t");
            try {
                String x = br.readLine();
                choice = Integer.parseInt(x);
            } catch (IOException e) {
                System.out.println("incorrect choice");
            }
     
            switch (choice) {
                case 1:
                    input_element();
                    root = insert(root);
                    break;
                case 2:
                    input_element();
                    root = delete(root);
                    break;
                case 3:
                    inorder(root);
                    break;
                case 4:
                    preorder(root);
                    break;
                case 5:
                    postorder(root);
                    break;
                case 6:
                    parent = 0;
                    input_element();
                    findparent(root);
                    if (parent == -1) {
                        System.out.println("element not present\n");
                    } else if (parent == 0) {
                        System.out.println(elem + "is at root\n");
                    } else {
                        System.out.println("parent of" + elem + "is" + parent);
                    }
                    break;
                case 7:
                    search();
                    break;
                case 8:
                    findtype();
                    break;
                case 9:
                    System.exit(0);
                    break;
                default:
                    System.out.println("wrong choice");
                    break;
            }
        }
     
        public static void main(String args[]) {
            bst m;
            m = new bst();
            while (true) {
                m.getchoice();
                System.out.println("\n");
            }
        }
    }

    Im a C++ programmer new to Java. Though the code runs fine(not checked it fully), i dont know if there is some deprecated features or errors in the code since im a beginner. Also suggest some good programming practices related to the code. Thanks in advance
    Last edited by helloworld922; December 11th, 2010 at 10:43 AM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Binary Search Tree in Java [HELP]

    In the future, please post your code here directly. Many people are suspicious of links elsewhere.

    I've copied your code here and put it into a highlight box. If you're unsure how to do this yourself, please see my signature.

    One thing I would recommend with your code is to separate all direct user interaction from your bst class. This allows your class to be more general and can be used by any interface you decide to design.

    Secondly, I would recommend renaming certain things in your code. The default Java convention is to use CamelCase.

    Classes/interfaces/enumerations begin with uppercase letters, and variable names/method names begin with lowercase letters. Also, It's general convention to spell out the name so it's clear what the name describes. Each subsequent word in an identifier is capitalized. For example, bst could be BinarySearchTree (though BST could be acceptable too since a lot of people will know what you mean by BST), and getchoice would become getChoice.

    Lastly, add some comments (both Javadoc and regular).

    Javadoc comments are used to let other people (or even yourself) know how to use your code, and describe the "contract" that that particular class/method fulfills. The other comments are mainly for you (or if someone else is going to be looking at/changing your code, them too) to be able to come back and quickly understand what the code is doing.

    I don't see any deprecated features or errors (but I only did a quick glance). The best way to find any possible errors is to test your code for general use, and also for "boundary cases" (such as trying to add two of the same item).

  3. The Following User Says Thank You to helloworld922 For This Useful Post:

    alan (February 5th, 2011)

  4. #3
    Junior Member
    Join Date
    Dec 2010
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search Tree in Java [HELP]

    Thanx bro... srry abt nt highlightin... did tht in a hurry...
    JPF looks kewl man...

Similar Threads

  1. 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
  2. Polymorphic Binary Search Tree Question
    By MJS139115 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: November 9th, 2010, 06:08 PM
  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