Want to support development? Maybe get a nice server to do your own development on? Check out BuyVM or Vultr using our affiliate links! New users get $50 of free credit with Vultr, and BuyVM offers affordable servers with affordable, true DDoS filtering. You can also support us on Patreon.
Submitted on November 9, 2019 at 10:13 AM
Expires on February 7, 2020 at 10:13 AM (2 months from now)

New Paste 1 (Text)

package Chp8_BinaryTrees;

import java.util.Scanner;

public class TestBST_Ch72 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number;
        BinarySearchTree tree= new BinarySearchTree();

        System.out.println();
        System.out.print("Enter a positive integer to insert ");
        System.out.print("or a negative integer to stop: ");
        number=scanner.nextInt();
        while (number>=0){
            tree.insertBST(number);
            tree.traverseBST();
            System.out.println();
            System.out.print("Enter a positive integer to insert ");
            System.out.print("or a negative integer to stop: ");
            number=scanner.nextInt();
        }
        System.out.println();

        System.out.print("Enter a positive integer to remove ");
        System.out.print("or a negative integer to quit: ");
        number=scanner.nextInt();
        while (number>=0){
            tree.removeBST(number);
            tree.traverseBST();
            System.out.println();
            System.out.print("Enter a positive integer to remove ");
            System.out.print("or a negative integer to quit: ");
            number=scanner.nextInt();
        }
        System.out.println();
        System.out.println("End of Program");
        System.out.println();
    }
}



-------------------

package Chp8_BinaryTrees;

public class BinarySearchTree {
    private Node root;

    //inner class Node
    private class Node{
        private Node left, right;
        private int data;

        public Node(){
            this(0);
        }

        public Node(int data){
            left=null;
            this.data=data;
            right=null;
        }
    }

    public BinarySearchTree() {
        root = null;
    }

    public void insertBST(int num){
        root=insert(num,root);
    }

    private Node insert(int num, Node p){
        if (p==null)
            p=new Node(num);
        else{
            if (num<p.data)
                p.left=insert(num,p.left);
            else
                if (num>p.data)
                    p.right=insert(num, p.right);
                            else
                    System.out.println("Item in the tree and not inserted");}
        System.out.println("Returned value "+p.data);//**
        return p;
    }

    public void removeBST(int num){
        root = remove(num,root);
    }
    private Node remove(int num,Node p){
        if (p!=null)//start locating the node in non-empty tree
            if (num<p.data)
                p.left=remove(num,p.left);
            else
                if (num>p.data)
                    p.right=remove(num,p.right);
                else//case 1: node found at terminal location
                    if (p.left==null&&p.right==null)
                        p=null;
                    else//case 2&3: node found at non-terminal location but only one subnode exists hereafter.
                        if (p.left==null)
                            p=p.right;
                        else
                            if (p.right==null)
                                p=p.left;
                            else {//case 4: two sub-nodes (with possibly further sub-nodes) underneath and the smallest number of right sub-node (including all sub-nodes) replaces the node to be removed
                                Node t=findMin(p.right);
                                p.data=t.data;
                                p.right=remove(p.data,p.right);
                            }
                            else{//case 5: empty or item not found
            System.out.println("Item not in tree and not removed");}
                            //intermediate output
                            if(p==null)
                                System.out.println("Returned value2 null");
                            else
                                System.out.println("Returned value2 "+p.data);//**
        return p;
    }

    private Node findMin(Node p){
        if (p!=null){
            while (p.left!=null)
                p=p.left;}
        System.out.println("Returned value3 "+p.data);//**
            return p;
    }

    public void traverseBST(){
        System.out.print("The tree is: ");
        if (root!=null)
            traverse(root);
        else
            System.out.print("Empty");
        System.out.println();
    }

    public void traverse(Node ptr){
        if (ptr.left!=null)
            traverse(ptr.left);
        System.out.print(" "+ptr.data);
        if (ptr.right!=null)
            traverse(ptr.right);
    }
}