Results 1 to 6 of 6

Thread: BSTree

  1. #1
    Fotis is offline Member
    Join Date
    May 2012
    Posts
    6
    Rep Power
    0

    Default BSTree

    Hi programmers.

    Please check if the following BSTree is ok?

    I only want to crate a BSTree of Strings, nothing else.

    Java Code:
    import java.util.Scanner;
    
    class Node {
        private Node left;
        private String number;
        private Node right;
    
        public Node() {
            left = null;
            number = "0";
            right = null;
        }
    
        public Node(String x) {
            left = null;
            number = x;
            right = null;
        }
    
        public String getNumber() {
            return number;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setNum(String x){
            number = x;
        }
    
        public void setLeft(Node leftNode) {
            left = leftNode;
        }
    
        public void setRight(Node rightNode) {
            right = rightNode;
        }
    
    }
    
      class BST{
        private Node root;
    
        public BST(){
            root = null;
        }
    
    
    
        public boolean isEmpty(){
                return root == null;
        }
    
    
        public void insert(String x){
            insertData(x, root);
        }
    
    
        private void insertData(String n, Node p){
            if(p == null){
                p = new Node(n);
                root = p;
            } else if(n.compareTo(p.getNumber()) < 0){
                if(p.getLeft() == null){
                    p.setLeft(new Node(n));
                } else {
                    p = p.getLeft();
                    insertData(n,p);
                }
            } else {
                if(p.getRight() == null){
                    p.setRight(new Node(n));
                } else {
                    p = p.getRight();
                    insertData(n, p);
                }
            }
        }
    }
    
     public class BinarySearchTree{
            public static void main(String[] args){
                BST tree = new BST();
                Scanner in = new Scanner(System.in);        
                for (int y=0; y<5;y++){                      
                    String x = in.nextLine();
                    tree.insert(x);
    }
    
            }
        }
    Thank you.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default Re: BSTree

    Quote Originally Posted by Fotis View Post
    Please check if the following BSTree is ok?
    Why should we check it? Have you checked it yourself? Does it work? If not, tell us what exactly doesn't work but don't assume we figure it out all by ourselves.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Fotis is offline Member
    Join Date
    May 2012
    Posts
    6
    Rep Power
    0

    Default Re: BSTree

    I made it and i don't know if it is a correct Binary Search Tree.

    Just i want be sure for this.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default Re: BSTree

    Quote Originally Posted by Fotis View Post
    I made it and i don't know if it is a correct Binary Search Tree.

    Just i want be sure for this.
    Does it do what you want it to do? Have you tested it? Do you want a formal correctness proof?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Fotis is offline Member
    Join Date
    May 2012
    Posts
    6
    Rep Power
    0

    Default Re: BSTree

    Quote Originally Posted by JosAH View Post
    Do you want a formal correctness proof?
    Just this.
    I believe that it is correct. I just want be sure.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default Re: BSTree

    Quote Originally Posted by Fotis View Post
    Just this.
    I believe that it is correct. I just want be sure.
    Ok, if you want an answer without asking a proper question: no that is not a proper search tree; it isn't balanced.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •