Binary Search Tree Implementation by iShrne

 السَلام عليكُم و رَحمَة الله و بَركَاتُه
 ، ,

Hi every body | :)

 i was study , and i wrote this program as a review for the final exam.
، .. This complete program contains the main methods of binary search tree i wrote them so please
|| IF you Have any question be free to ask.  ^^

Source Code Content:

1. Insert method
2. Remove method
3. Search method
4. Find min ( return reference )
5. Count number of  nodes less than given value
6. Count  number of nodes greater than given value
7. Check if it is Binary Search Tree or not.
8. Count Node recursively / non- recursively.
9. Traversal ( InOrder/PostOrder/PerOrder)
10.  Single Parent Count
11. Leave Count
12. Destroy Tree
13. Copy Tree
14. Max
15. If Two Trees are same ( as a nodes not content ) .  

------------------------------------------------------------------||


[ Main Class ]

import java.util.Scanner;
//-- All Rights Reserved to iShrne - 2008 student in United Arab Emirates -- //
public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // Creating a binary search tree Done
        binarysearchtree T = new binarysearchtree();
        binarysearchtree D = new binarysearchtree();
        intElement x = new intElement();
        intElement y = new intElement();
        intElement z = new intElement();
        intElement w = new intElement();
        intElement s = new intElement();
        intElement d = new intElement();
        int numElt, num, numu, numElte;
        while (true) {
            System.out.println("Enter first letter of  the task that you wanna run");
            System.out.println();
            String choice = input.next();
            int ch = choice.charAt(0);
            switch (ch) {

                case 's':
                    System.out.print("print");
                    T.printTree();
                    break;
                // Inserting a number in the tree
                case 'i':
                    System.out.println("-----|There are two tree availble , T and D|----");
                    String tree = input.next();
                    char cha = tree.charAt(0);
                    if (cha == 'T') {
                        System.out.println("-----|How many elements do you want to insert in the [ T ] |---- ");
                        numElt = input.nextInt();
                        for (int i = 1; i <= numElt; i++) {
                            System.out.println("enter the next element TTree");
                            num = input.nextInt();
                            x.setNum(num);
                            T.insert(x);
                        }
                    } else if (cha == 'D') {

                        System.out.println("-----|How many elements do you want to insert in the [ D ] |---- ");
                        numElte = input.nextInt();
                        for (int i = 1; i <= numElte; i++) {
                            numu = input.nextInt();
                            d.setNum(numu);
                            D.insert(d);
                            D.printTree();

                        }
                    } else {
                        System.out.println("|| F A I L D / Try Again ||");
                    }
                    System.out.println();
                    break;
                case 'f':
                    System.out.println(" search ");
                    System.out.println("Enter value to find: ");
                    int numb = input.nextInt();
                    y.setNum(numb);
                    if (T.search(y)) {
                        System.out.println(" :found");
                    } else {
                        System.out.println(" :not found");
                    }
                    System.out.println();
                    break;

                case 'T':
                    if (T.SimilarTree(T, D)) {
                        System.out.println(" :TRUE");
                    } else {
                        System.out.println(" :not SAME");
                    }
                    System.out.println();
                    break;
                // Deleting a number from the
                case 'r':
                    System.out.println(" Deleting a number from the ");
                    System.out.println("Enter value to delete");
                    int numba = input.nextInt();
                    z.setNum(numba);
                    if (T.search(z) == true) {
                        T.deleteNode(z);
                        T.printTree();
                    } else {
                        System.out.println(" :not found");
                    }
                    System.out.println();
                    break;

                // Traversing the tree
                case 't':
                    System.out.println(" Traversing the tree ");
                    System.out.println(" ");
                    System.out.println("Enter 1 , 2 or 3 of trevarsing way");
                    int choi = input.nextInt();
                    if (choi == 1) {
                        T.inorderTraversal();
                    } else if (choi == 2) {
                        T.postorderTraversal();
                    } else if (choi == 3) {
                        T.preorderTraversal();
                    }
                    System.out.println();
                    break;
                // Counting the number of nodes in the tree
                case 'c':
                    System.out.println(" Counting the number of nodes in the tree ");
                    System.out.println();
                    T.counter();
                    break;

                //Counting the number of leaf nodes in the tree
                case 'l':

                    System.out.println(" Counting the number of leaf nodes in the tree ");
                    System.out.println(T.treeLeavesCount());
                    System.out.println();
                    break;
                // determining whether the binary search tree is a binary search tree.
                case 'D':
                    System.out.println(" determining whether the [ binary search tree is a binary ] search tree");
                    System.out.println(T.isBST());
                    System.out.println();
                    break;
                // Counting the number of nodes in the tree whose value is greater than a given value V.
                case 'G':
                    System.out.println("Counting the number of nodes in the tree whose value is [greater] than a given value V");
                    System.out.println("Enter a value:");
                    int numbaa = input.nextInt();
                    w.setNum(numbaa);
                    System.out.println("there are " + T.FinM(w));
                    System.out.println();
                    break;
                case 'L':
                    System.out.println("Counting the number of nodes in the tree whose value is [Less] than a given value V");
                    System.out.println("Enter a value:");
                    int numbaaa = input.nextInt();
                    s.setNum(numbaaa);
                    System.out.println("there are " + T.FinL(s));
                    System.out.println();
                    break;
                // non recursive function Min to find the smallest value in a BST
                case 'M':
                    System.out.println("non recursive function Min to find the smallest value in a BST");
                    T.min();
                    System.out.println();
                    break;
                case 'P':
                    System.out.println("Count Single Parent");
                    System.out.println(T.singleParentCount());
                    System.out.println();
                    break;

                default:
                    System.out.println("INVALID / TRY ANOTHER CHARACTER");
                    System.out.println();
                    break;
            }
            System.out.println("END");
            System.out.println();
            //break;
        }

    }
}

[ Data Element Class ]

public abstract class  DataElement {

    public abstract boolean equals(DataElement otherElement);
      //Method to determine whether two objects contain the
      //same data.
      //Postcondition: Returns true if this object contains the
      //               same data as the object otherElement;
      //               otherwise, it returns false.

    public abstract int compareTo(DataElement otherElement);
      //Method to compare two objects.
      //Postcondition: Returns a value < 0 if this object is
      //                    less than the object otherElement;
      //               Returns 0 if this object is the same as
      //                    the object otherElement.
      //               Returns a value > 0 if this object is
      //                  greater than the object otherElement.

    public abstract void makeCopy(DataElement otherElement);
      //Method to copy otherElement into this object.
      //Postcondition: The data of otherElement is copied into
      //               this object.

    public abstract DataElement getCopy();
      //Method to return a copy of this object.
      //Postcondition: A copy of this object is created and
      //               a reference of the copy is returned.
}

[ intElementClass ]

/**
 *
 * @iShrne | iShrne | iShrne | ---- ! 
 */
public class intElement extends DataElement{

    protected int num;

        //default constructor
    public intElement()
    {
        num = 0;
    }

        //constructor with parameters
    public intElement(int x)
    {
        num = x;
    }

        //copy constructor
    public intElement(intElement otherElement)
    {
        num = otherElement.num;
    }

        //Method to set the value of the instance variable num
         //Postcondition: num = x;
    public void setNum(int x)
    {
        num = x;
    }

        //Method to return the value of the instance variable num
        //Postcondition: The value of num is returned
    public int getNum()
    {
        return num;
    }


    public boolean equals(DataElement otherElement)
    {
        intElement temp = (intElement) otherElement;

        return (num == temp.num);
    }

    public int compareTo(DataElement otherElement)
    {
        intElement temp = (intElement) otherElement;

        return (num - temp.num);
    }

    public void makeCopy(DataElement otherElement)
    {
          intElement temp = (intElement) otherElement;

          num = temp.num;
    }

    public DataElement getCopy()
    {
        intElement temp = new intElement(num);
        return temp;
    }

    public String toString()
    {
        return String.valueOf(num);
    }
}

[BS class  ]

import java.util.Stack;

/**
 *
 * @iShrne | iShrne | iShrne | iShrne | iShrne | ---- ! 
 */
public class binarytree {

    protected class BinaryTreeNode {

        DataElement info;
        BinaryTreeNode llink;
        BinaryTreeNode rlink;
    }
    protected BinaryTreeNode root;
    protected BinaryTreeNode root2;


    public binarytree() {
        root = null;
    }

    public int singleParentCount() {
        return singleParentCount(root);
    }

    public void printTree() {
        printTree(root);
        System.out.println();
    }
    //copy constructor

    public binarytree(binarytree otherTree) {
        if (otherTree.root == null) //otherTree is empty
        {
            root = null;
        } else {
            root = copy(otherTree.root);
        }
    }

    public boolean isEmpty() {
        return (root == null);
    }

    public void inorderTraversal() {
        inorder(root);
    }

    public boolean isBST() {
        return isBST(root);
    }

    public DataElement min() {
        return min(root);
    }

    public void preorderTraversal() {
        preorder(root);
    }

    public void postorderTraversal() {
        postorder(root);
    }

    public int treeLeavesCount() {
        return leavesCount(root);
    }

    public void destroyTree() {
        root = null;
    }

    public void copyTree(binarytree otherTree) {

        if (this != otherTree) //avoid self-copy
        {
            root = null;

            if (otherTree.root != null) //otherTree is nonempty
            {
                root = copy(otherTree.root);
            }
        }

    }

    private BinaryTreeNode copy(BinaryTreeNode otherTreeRoot) {
        BinaryTreeNode temp;

        if (otherTreeRoot == null) {
            temp = null;
        } else {
            temp = new BinaryTreeNode();
            temp.info = otherTreeRoot.info.getCopy();
            temp.llink = copy(otherTreeRoot.llink);
            temp.rlink = copy(otherTreeRoot.rlink);
        }

        return temp;
    }//end copy

    private void inorder(BinaryTreeNode p) {
        if (p != null) {
            inorder(p.llink);
            System.out.print(p.info + " ");
            inorder(p.rlink);
        }
    }

    private void preorder(BinaryTreeNode p) {

        if (p != null) {
            System.out.println(p.info + " ");
            inorder(p.llink);
            inorder(p.rlink);
        }
    }

    private void postorder(BinaryTreeNode p) {
        if (p != null) {

            inorder(p.llink);
            inorder(p.rlink);
            System.out.println(p.info + " ");
        }
    }

    private int leavesCount(BinaryTreeNode p) {

        if (p == null) {// BASIC CASE
            return 0;
        } else if (p.llink == null && p.rlink == null) { // BASIC CASE
            return 1;
        } else {
            return leavesCount(p.llink) + leavesCount(p.rlink);
        }
    }

    private int singleParentCount(BinaryTreeNode p) {
        if (p == null) {
            return 0;
        } else if (p.llink == null && p.rlink != null) {
            return 1;
        } else if (p.llink != null && p.rlink == null) {
            return 1;
        } else {
            return singleParentCount(p.llink) + singleParentCount(p.rlink);
        }
    }

    private void printTree(BinaryTreeNode node) {
        if (node == null) {
            return;
        }

        // left, node itself, right
        printTree(node.llink);
        System.out.print("[ " + node.info + " ]" + "  ");
        printTree(node.rlink);
    }

    public int FinM(DataElement p) {
        BinaryTreeNode current = root;
        return conutMore(current, p);
    }

    public int FinL(DataElement p) {
        BinaryTreeNode current = root;
        return countLess(current, p);
    }

    /**
    Finds the min value in a non-empty binary search tree.
     */
    public static int conutMore(BinaryTreeNode p, DataElement b) {
        if (p == null) {
            return 0;
        } else if (p.info.compareTo(b) > 0) {
            return 1 + countNode(p.rlink) + conutMore(p.llink, b);
        } else if (p.info.equals(b)) {
            return countNode(p.rlink);
        } else {
            return conutMore(p.rlink, b);
        }

    }

    public static int countLess(BinaryTreeNode p, DataElement b) {

        if (p == null) {
            return 0;
        } else if (p.info.compareTo(b) < 0) {
            return 1 + countNode(p.llink) + countLess(p.rlink, b);
        } else if (p.info.equals(b)) {
            return countNode(p.llink);
        } else {
            return countLess(p.llink, b);
        }
    }

    private DataElement min(BinaryTreeNode p) {
        BinaryTreeNode current = p;
        while (current.llink != null) {
            current = current.llink;
        }
        System.out.println(current.info);
        return (current.info);

    }

    private boolean isBST(BinaryTreeNode p) {
        if (p == null) {
            return true;
        } else if (p.llink == null && p.rlink == null) {
            return true;
        } else if (p.llink == null && p.rlink != null) {

            if (p.info.compareTo(p.rlink.info) < 0) {
                return isBST(p.rlink);
            } else {
                return false;
            }
        } else if (p.llink != null && p.rlink == null) {
            if (p.info.compareTo(p.llink.info) > 0) {
                return isBST(p.llink);

            } else {
                return false;
            }
        } else if (p.info.compareTo(p.llink.info) > 0 && p.info.compareTo(p.rlink.info) < 0) {

            return isBST(p.llink) && isBST(p.rlink);
        } else {
            return false;
        }


    }

//
    public void counter() {
        int count = 0;
        Stack stack = new Stack();
        BinaryTreeNode curr = root;
        while ((curr != null) || (!stack.empty())) {
            if (curr != null) {

                stack.push(curr);
                curr = curr.llink;
            } else {
                curr = (BinaryTreeNode) stack.peek();
                count++;
                stack.pop();
                curr = curr.rlink;
            }
        }
        System.out.println(count);
        System.out.println();
    }

    public static int max(BinaryTreeNode p) {
        int count = 0;
        BinaryTreeNode current = p;
        while (current.rlink != null) {
            count++;
            current = current.llink;
        }
        System.out.println(count);
        return (count);

    }

    public static int countNode(BinaryTreeNode p) {
        if (p == null) {
            return 0;
        } else {
            return 1 + countNode(p.llink) + countNode(p.rlink);
        }
    }

    public boolean SimilarTree(binarysearchtree p, binarysearchtree k) {
        BinaryTreeNode a = p.root;
        BinaryTreeNode b = k.root;
        if (a == b) {
            return true;
        } else if (countNode(a.llink) == countNode(b.llink) && (countNode(a.rlink) == countNode(b.rlink))) {
            return true;
        } else {
            return false;
        }
    }
}

[ BST class ]

/**
 *
 * @author USER
 */
public class binarysearchtree extends binarytree{

    //default constructor
    //Postcondition: root = null;

    public binarysearchtree() {
        super();
    }

    //copy constructor
    public binarysearchtree(binarysearchtree otherTree) {
       super(otherTree);
    }

    
    public boolean search(DataElement searchItem) {
        BinaryTreeNode current;
        boolean found = false;
        if (root == null) {
            System.out.println("Cannot search an empty tree.");
        } else {
            current = root;
            while (current != null && !found) {
                if (current.info.equals(searchItem)) {
                    found = true;
                } else if (current.info.compareTo(searchItem) > 0) {
                    System.out.println("path "+current.info);
                    current = current.llink;
                } else {
                    System.out.println("path "+current.info);
                    current = current.rlink;
                }
            }

        }
        System.out.println(found);
        return found;


    }//end search
    // Method to find the element and return the value of this elment.


    //Method to insert insertItem in the binary search tree.
    //Postcondition: If no node in the binary search tree has
    //               the same info as insertItem, a node with
    //               the info insertItem is created and inserted
    //               in the binary search tree.

    public void insert(DataElement insertItem) {
        BinaryTreeNode current;
        BinaryTreeNode trailCurrent = null;
        BinaryTreeNode newNode;
        newNode = new BinaryTreeNode();
        newNode.info = insertItem.getCopy();
        newNode.llink = null;
        newNode.rlink = null;
        if (root == null) {
            root = newNode;
        } else {
            current = root;
            while (current != null) {
                trailCurrent = current;
                if (current.info.equals(insertItem))
                {
                    System.err.print("Item is already in the list");
                    return;
                        }
                else if (current.info.compareTo(insertItem) > 0)
                        {
                            current = current.llink;
                        }
                        else {
                            current = current.rlink;
                        }
                    }

                    if (trailCurrent.info.compareTo(insertItem) > 0) {
                        trailCurrent.llink = newNode;
                    } else {
                        trailCurrent.rlink = newNode;
                    }
                }


        }//end insert

    //Method to delete deleteItem from the binary search tree
    //Postcondition: If a node with the same info as deleteItem
    //               is found, it is deleted from the binary
    //               search tree.

    public void deleteNode(DataElement deleteItem) {
        BinaryTreeNode current;
        BinaryTreeNode trailCurrent;
        boolean found = false;
        if (root == null) {
            System.err.println("Cannot delete from the empty tree.");
        } else {
            current = root;
            trailCurrent = root;
            while (current != null && !found) {
                if (current.info.equals(deleteItem)) {
                    found = true;
                } else {
                    trailCurrent = current;

                    if (current.info.compareTo(deleteItem) > 0) {
                        current = current.llink;
                    } else {
                        current = current.rlink;
                    }
                }
            }//end while
            if (current == null) {
                System.out.println("The delete item is not in the tree.");
            } else if (found) {
                if (current == root) {
                    root = deleteFromTree(root);
                } else if (trailCurrent.info.compareTo(deleteItem) > 0) {
                    trailCurrent.llink = deleteFromTree(trailCurrent.llink);
                } else {
                    trailCurrent.rlink = deleteFromTree(trailCurrent.rlink);
                }
            }
        }



    }//end deleteNode

  
    private BinaryTreeNode deleteFromTree(BinaryTreeNode p) {
        {
            BinaryTreeNode current;
            BinaryTreeNode trailCurrent;
            if (p == null) {
                System.err.println("Error: Can not delete null.");
            } else if (p.llink == null && p.rlink == null) {
                p = null;
            } else if (p.llink == null) {
                p = p.rlink;
            } else if (p.rlink == null) {
                p = p.llink;
            } else {
                current = p.llink;
                trailCurrent = null;
                while (current.rlink != null) {
                    trailCurrent = current;
                    current = current.rlink;
                }
                p.info = current.info;

                if (trailCurrent == null) {
                    p.llink = current.llink;
                } else {
                    trailCurrent.rlink = current.llink;
                }
            }

            return p;
        }
    }
 
    }//end deleteFromTree

Hope this is useful material to share , good luck to you all.
iShrne.