二叉搜索树

2018-03-04 -数据结构 PV:

一、操作：

判断元素是否存在：递归的在左右子树中查找
查找最小元素：在左子树中递归或者循环
查找最大元素：在右子树中递归或循环
插入：递归的插入，大于则插入在节点的右子树，小于则左子树，等于则是重复节点不作处理
删除：递归删除( 或者说递归查找需要删除的元素 )，找到该元素后，如果元素有两个子节点那么久找到这个元素的右子树的最小元素代替要删除的元素，然后再删除那个右子树上的最小元素。如果只有一个子节点直接让要被删除的节点赋值上他的子节点。
二、代码

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;
    }


}

一、操作：

二、代码