二叉搜索树

package Tree;

import sun.tools.tree.ThisExpression;

import java.util.Stack;

public class MyBinaryTree {
    public class BinaryNode implements Comparable<Integer> {
        BinaryNode lChild;
        BinaryNode rChild;
        Integer ele;

        BinaryNode(Integer ele) {
            this(ele, null, null);
        }

        BinaryNode(Integer ele, BinaryNode lChild, BinaryNode rChild) {
            this.ele = ele;
            this.lChild = lChild;
            this.rChild = rChild;
        }

        @Override
        public int compareTo(Integer o) {
            return ele - o;
        }
    }

    private BinaryNode root;

    public MyBinaryTree() {
        root = null;
    }

    public MyBinaryTree(Integer ele) {
        root = new BinaryNode(ele, null, null);
    }

    public void makeEmpty() {
        this.root = null;
    }

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

    public boolean contains(Integer node) {
        return contains(node, root);
    }

    public boolean contains(Integer node, BinaryNode root) {
        if (root == null) {
            return false;
        }
        int result = root.ele.compareTo(node);
        if (result > 0) {
            return contains(node, root.lChild);
        } else if (result < 0) {
            return contains(node, root.rChild);
        } else {
            return true;
        }
    }

    public Integer findMin() {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        return (Integer) findMin(root);
    }

    public Integer findMin(BinaryNode root) {
        if (root == null) {
            return null;
        } else if (root.lChild == null) {
            return root.ele;
        } else {
            return findMin(root.lChild);
        }
    }

    public Integer findMax() {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        return (Integer) findMax(root).ele;
    }

    public BinaryNode findMax(BinaryNode root) {
        if (root == null) {
            return null;
        } else if (root.rChild == null) {
            return root;
        } else {
            return findMax(root.rChild);
        }
    }

    public void insert(Integer x) {
        root = insert(x, root);
    }

    public BinaryNode insert(Integer ele, BinaryNode root) {
        if (root == null) {
            return new BinaryNode(ele);
        }
        int result = root.compareTo(ele);
        if (result < 0) {
            root.rChild = insert(ele, root.rChild);
        } else if (result > 0) {
            root.lChild = insert(ele, root.lChild);
        } else ;
        return root;
    }

    public BinaryNode remove(Integer ele) {
        root = remove(ele, root);
        return root;
    }

    public BinaryNode remove(Integer ele, BinaryNode root) {
        if (root == null) {
            return null;
        }
        int result = root.compareTo(ele);
        if (result > 0) {
            root.lChild = remove(ele, root.lChild);
        } else if (result < 0) {
            root.rChild = remove(ele, root.rChild);
        }
        //这个地方就是递归的结束条件  也就是当我们找到了要删除的节点，这时候要分情况如果两个子节点都不空我们需要把右子树的最小值的替换到当前节点然后删除右子树最小节点
        //当有一个或者0个节点的时候我们只需要把左边或者右边挂上去就行
        else if (root.lChild != null && root.rChild != null) {
            root.ele = findMin(root.rChild);
            root.rChild = remove(root.ele, root.rChild);
        } else {
            root = root.lChild == null ? root.rChild : root.lChild;
        }
        return root;
    }

    public void printTree() {
        preOrder(root);
    }

    public void preOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.ele + " ");
        if (root.lChild != null) {
            preOrder(root.lChild);
        }
        if (root.rChild != null) {
            preOrder(root.rChild);
        }
    }

    public void inOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        if (root.lChild != null) {
            inOrder(root.lChild);
        }
        System.out.print(root.ele + " ");
        if (root.rChild != null) {
            inOrder(root.rChild);
        }
    }

    public void subOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        if (root.lChild != null) {
            inOrder(root.lChild);
        }
        if (root.rChild != null) {
            inOrder(root.rChild);
        }
        System.out.print(root.ele + " ");
    }

    public void preOrder_1(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        // stack.push(root);
        BinaryNode p = root;
        System.out.printf(p.ele + " ");
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                System.out.printf(p.ele + " ");
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.pop();
                p = p.rChild;
            }
        }
    }

    public void inOrder_1(BinaryNode root) {
        BinaryNode p = root;
        Stack<BinaryNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.pop();
                System.out.printf(p.ele + " ");
                p = p.rChild;
            }
        }
    }

    public void subOrder_1(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        BinaryNode q = null;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.peek();
                if (p.rChild == null || p.rChild == q) {
                    q = p;
                    p = stack.pop();
                    System.out.printf(p.ele + " ");
                    p = null;
                } else {
                    p = p.rChild;
                }
            }
        }
    }

    public BinaryNode getRoot() {
        return this.root;
    }


}