Binary Tree Find & Delete - WIP

import java.io.*;
import java.io.IOException;
import javax.swing.*;
import java.util.*;
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.*;
import java.util.NoSuchElementException;

/**
 * This Program Will Perform The Following:
 * A Series of numbers are selected.
 * Integers: 78,39,52,28,33,14,16,4,35,105,85,92,80,97,110, & 99
 * The Numbers are added to instances of MyBinaryTreeMgr for their respective Data type.
 * A Binary Tree is Formed by making the first number the Root of The tree.
 * Numbers greater in value than the root, move to the right "Leaf" of the tree.
 * Numbers less in value than the root, move to the left "Leaf" of the tree.
 * Once the numbers are added, the tree can be traversed either InOrder, PreOrder, or PostOrder.
 * Inorder Follows the rule of Left - Root - Right.
 * PreOrder Follows the rule of Root - Left - Right.
 * PostOrder Follows the rule of Left - Right - Root.
 * A print out of each tree in each form of Traversal is provided.
 * From there specific nodes of the tree are deleted.
 * First we delete 28.
 * Then we traverse the tree Inorder, Preorder, and PostOrder again.
 * Then we delete 105.
 * Then we traverse the tree Inorder, Preorder, and PostOrder again.
 * Finally we delete 110.
 * Then we traverse the tree Inorder, Preorder, and PostOrder one last time.
 */


public class BinaryTreeNodeFinder {

    public static void main(String[] args) throws Exception {

        //Create a print write for documentation to a file and printing assistance
        PrintWriter outpt;
        outpt = new PrintWriter(new File("JavaAbsOut6.txt"));

        //Create a new instance of the Binary Tree Manager to handle Integers.
        MyBinaryTreeMgr<Integer> BtreeInt = new MyBinaryTreeMgr<Integer>();


        //Add Integers to the Binary Tree BtreeInt
        BtreeInt.insertnode(78);
        BtreeInt.insertnode(39);
        BtreeInt.insertnode(52);
        BtreeInt.insertnode(28);
        BtreeInt.insertnode(33);
        BtreeInt.insertnode(14);
        BtreeInt.insertnode(16);
        BtreeInt.insertnode(4);
        BtreeInt.insertnode(35);
        BtreeInt.insertnode(105);
        BtreeInt.insertnode(85);
        BtreeInt.insertnode(92);
        BtreeInt.insertnode(80);
        BtreeInt.insertnode(97);
        BtreeInt.insertnode(110);
        BtreeInt.insertnode(99);


        //Print the Binary Tree BTreeInt InOrder.
        System.out.println("\nPrinting The Integer Tree InOrder Left-Root-Right \n");
        BtreeInt.inorder(outpt);

        //Print the binary Tree BTreeInt in PreOrder
        System.out.println("\nPrinting The Integer Tree In Preorder Root-Left-Right \n");
        BtreeInt.PreOrder(outpt);

        //Print the Binary Tree BtreeInt in PostOrder
        System.out.println("\n Printing The Integer Tree in PostOrder Left-Right-Root\n");
        BtreeInt.PostOrder(outpt);

        //Create values for the values we're going to be deleting.
        int firstfind = 28;
        int secondfind = 105;
        int thirdfind = 110;


        //Find the First node we're attempting to delete.
        System.out.println("\nFinding: "+firstfind);
        BtreeInt.FindNode(firstfind);


        //Delete the first node we're attempting to delete from the tree.
        System.out.println("\nDeleting "+firstfind+" From The Tree");
        BtreeInt.deleteNode(firstfind);


        //Print the tree Inorder after deleting firstfind
        System.out.println("\n"+firstfind+" Has Been Deleted From The Tree. Listing Tree InOrder\n");
        BtreeInt.inorder(outpt);

        //Print the tree in PreOrder after deleting firstfind
        System.out.println("\n"+firstfind+" Has Been Deleted From The Tree. Listing Tree In PreOrder\n");
        BtreeInt.PreOrder(outpt);

        //Print the tree in PostOrder after deleting firstfind
        System.out.println("\n"+firstfind+" Has Been Deleted From The Tree. Listing Tree In PostOrder\n");
        BtreeInt.PostOrder(outpt);

        //Find the second node we're attempting to delete.
        System.out.println("\nFinding: "+secondfind);
        BtreeInt.FindNode(secondfind);

        //Delete the first node we're attempting to delete from the tree.
        System.out.println("\nDeleting "+secondfind+" From The Tree");
        BtreeInt.deleteNode(secondfind);


        //Print the tree Inorder after deleting secondfind
        System.out.println("\n"+firstfind+", & "+secondfind+" Have Been Deleted From The Tree. Listing Tree InOrder\n");
        BtreeInt.inorder(outpt);

        //Print the tree in PreOrder after deleting secondfind
        System.out.println("\n"+firstfind+", & "+secondfind+" Have Been Deleted From The Tree. Listing Tree In PreOrder\n");
        BtreeInt.PreOrder(outpt);

        //Print the tree in PostOrder after deleting secondfind
        System.out.println("\n"+firstfind+", & "+secondfind+" Have Been Deleted From The Tree. Listing Tree In PostOrder\n");
        BtreeInt.PostOrder(outpt);

        //Find the Third node we're attempting to delete.
        System.out.println("\nFinding: "+thirdfind);
        BtreeInt.FindNode(thirdfind);

        //Delete the third node we're attempting to delete from the tree.
        System.out.println("\nDeleting "+thirdfind+" From The Tree");
        BtreeInt.deleteNode(thirdfind);

        //Print the tree Inorder after deleting thirdfind
        System.out.println("\n"+firstfind+", "+secondfind+", & "+thirdfind+" Have Been Deleted From The Tree. Listing Tree InOrder\n");
        BtreeInt.inorder(outpt);

        //Print the tree in PreOrder after deleting secondfind
        System.out.println("\n"+firstfind+", "+secondfind+", & "+thirdfind+" Have Been Deleted From The Tree. Listing Tree In PreOrder\n");
        BtreeInt.PreOrder(outpt);

        //Print the tree in PostOrder after deleting secondfind
        System.out.println("\n"+firstfind+", "+secondfind+", & "+thirdfind+" Have Been Deleted From The Tree. Listing Tree In PostOrder\n");
        BtreeInt.PostOrder(outpt);

        outpt.close();

    }
}

//The Class MyBinaryTreeMgr, Generically handles Binary Trees
class MyBinaryTreeMgr<T extends Comparable<T>> {
    protected TreeNode<T> root;
    protected int number;
    protected T nodevalue;
    protected TreeNode<T> left;
    protected TreeNode<T> right;

    //Inner Class for a single Tree Node
    private static class TreeNode<T extends Comparable> {
        protected T nodevalue;
        protected TreeNode<T> left;
        protected TreeNode<T> right;

        public TreeNode(T x) {
            nodevalue = x;
            left = null;
            right = null;
        }

    }

    protected TreeNode<T> foundnode;
    protected TreeNode<T> foundleftchild;
    protected TreeNode<T> foundrightchild;
    protected TreeNode<T> foundnodeparent;
    protected TreeNode<T> currentnode;
    protected TreeNode<T> currentleft;
    protected TreeNode<T> currentright;
    protected TreeNode<T> parentnode;

    public MyBinaryTreeMgr() {
        root = null;
        int number = 0;
    }

    //Getter to find the number of nodes in a tree.
    public int getnumber() {
        return number;
    }

    //Method to find and print the parent node of a found node.
    public void printparent() {
        if (foundnodeparent == null) {
            System.out.println("Parent null");
        } else {
            System.out.println(foundnodeparent.nodevalue);
        }
    }

    //Method to find and print the left node of a found node.
    public void printleft() {
        if (foundleftchild == null) {
            System.out.println("Left Child null");
        } else {
            System.out.println(foundleftchild.nodevalue);
        }
    }

    //Method to find and print the right node of a found node.
    public void printright() {
        if (foundrightchild == null) {
            System.out.println("Right child null");
        } else {
            System.out.println(foundrightchild.nodevalue);
        }
    }

    //Method used to create a node within the binary tree
    protected TreeNode<T> CreateNode(T x) {
        return new TreeNode(x);
    }

    //Method to insert a value into the binary tree.
    public int insertnode(T x) {
        if (root == null) {
            root = CreateNode(x);
            number = 1;
            return number;
        } else {
            TreeNode<T> parent = null;
            TreeNode<T> current = root;
            while (current != null)
                if (x.compareTo(current.nodevalue) < 0) {
                    parent = current;
                    current = current.left;
                } else if (x.compareTo(current.nodevalue) > 0) {
                    parent = current;
                    current = current.right;
                } else return -99;

            if (x.compareTo(parent.nodevalue) < 0) {
                parent.left = CreateNode(x);
            } else parent.right = CreateNode(x);
        }
        number++;
        return number;
    }

    //Method to Find a Node within a Binary Tree.
    public int FindNode(T x) {
        int Nsearch = 0;
        if (number == 0) {
            Nsearch = 0;
            return Nsearch;
        } else {
            if (x.compareTo(root.nodevalue) == 0) {
                Nsearch = 2;
                foundnodeparent = parentnode = root;
                foundleftchild = root.left;
                foundrightchild = root.right;
                return Nsearch;
            } else {
                parentnode = root;
                currentnode = root;
                currentleft = root.left;
                currentright = root.right;
            }
            while (x.compareTo(currentnode.nodevalue) != 0) {
                if (x.compareTo(currentnode.nodevalue) > 0) {
                    parentnode = currentnode;
                    if (currentnode.right == null) {
                        Nsearch = 0;
                        return Nsearch;
                    }
                    currentnode = currentnode.right;
                } else {
                    foundnodeparent = parentnode = currentnode;
                    if (currentnode.left == null) {
                        Nsearch = 0;
                        return Nsearch;
                    }
                    currentnode = currentnode.left;
                }
            }
            foundleftchild = currentnode.left;
            foundrightchild = currentnode.right;
            Nsearch = 1;
        }
        return Nsearch;
    }

    //Method to Delete a value from a Binary Tree

    // This method mainly calls deleteRec()
    void deleteNode(T key)
    {
        root = deleteRec(root, key);
    }

    /* A recursive function to insert a new key in BST */
    TreeNode<T> deleteRec(TreeNode<T> root, T key)
    {
        /* Base Case: If the tree is empty */
        if (root == null)  return root;

        /* Otherwise, recur down the tree */
        //if (x.compareTo(root.nodevalue) == 0)
        if (key.compareTo(root.nodevalue) < 0)
            root.left = deleteRec(root.left, key);
        else if (key.compareTo(root.nodevalue) > 0)
            root.right = deleteRec(root.right, key);

            // if key is same as root's key, then This is the node to be deleted
        else
        {
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with two children: Get the inorder successor (smallest in the right subtree)
            root.nodevalue = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.nodevalue);
        }

        return root;
    }
    T minValue(TreeNode<T> root)
    {
        T minv = root.nodevalue;
        while (root.left != null)
        {
            minv = root.left.nodevalue;
            root = root.left;
        }
        return minv;
    }



    //Methods to print a Binary Tree InOrder
    public void inorder(PrintWriter outp) {
        //Start From Root Node
        inorder(root, outp);
    }

    protected void inorder(TreeNode<T> root, PrintWriter outp) {
        if (root == null) return;
        //Left
        inorder(root.left, outp);
        //Root
        System.out.println(root.nodevalue + " ");
        outp.print(root.nodevalue + " ");
        //Right
        inorder(root.right, outp);
    }

    //Methods to print a Binary Tree in PreOrder
    public void PreOrder(PrintWriter outp) {
        // start from Root Node
        PreOrder(root, outp);
    }

    protected void PreOrder(TreeNode<T> root, PrintWriter outp) {
        if (root == null) return;
        // Root
        System.out.println(root.nodevalue + " ");
        outp.print(root.nodevalue + " ");

        // Left
        PreOrder(root.left, outp);

        // Right
        PreOrder(root.right, outp);
    }

    //Methods to print a Binary Tree in Post Order
    public void PostOrder(PrintWriter outp) {
        // start from root node
        PostOrder(root, outp);
    }

    protected void PostOrder(TreeNode<T> root, PrintWriter outp) {
        if (root == null) return;
        // Left
        PostOrder(root.left, outp);

        // Right
        PostOrder(root.right, outp);

        // Root
        System.out.println(root.nodevalue + " ");
        outp.print(root.nodevalue + " ");
    }
}