二叉查找树代码实现

一、定义

1. 查找二叉树又叫二叉排序树，如果同时满足以下性质：
   1. 左右子树都是二叉树；
   2. 如果左子树不为空，那么左子树上面的所有节点的关键字都比根节点的关键字小；
   3. 如果右子树不为空，那么右子树上面的所有节点的关键字都比跟节点的关键字大；
2. 好处：方便查找，可以提高查找效率，查找二叉树越平衡，查找的效率的越稳定，效率越高，这种树就是平衡二叉树；

二、代码实现

public class SearchBinaryTree {

    private TreeNode root;//跟节点

    /**
     * 创建查找二叉树，如果关键字比根节点的关键字大，就往右边插入，
     * 如果关键字比根节点小，就往左边插入
     * @param data 带插入的数据
     * @return
     */
    public TreeNode put(int data) {
        TreeNode node = null;
        TreeNode parent = null;
        //首先判断根节点，如果根节点为空，则新创建的节点为根节点
        if (root == null) {
            node = new TreeNode(0, data);
            root = node;
            return node;
        } else {
            //如果不是根节点，就需要不停地遍历已有的节点，找到满足条件的节点的位置，然后插入节点
            //和根节点进行比较，首先要拿到根节点
            node = root;
            while (node != null) {
                //把当前结点制定为父节点，然后比较左右孩子和当前节点的大小
                parent = node;
                //如果要插入的数据比当前结点要大，就需要往右子树上找
                if (data > node.data) {
                    node = node.rightChild;
                } else if (data < node.data) {
                    node = node.leftChild;
                } else {
                    return node;
                }
            }
            //while循环结束，就表示找到了要插入的地方，
            // 接下来就是创建节点，然后把这个节点挂在指定的位置
            //角标默认是0
            node = new TreeNode(0, data);
            //节点创建完毕，需要判断放在父节点的左边还是右边
            if (data < parent.data) {
                parent.leftChild = node;
            } else {
                parent.rightChild = node;
            }
            //指定这个节点的父节点
            node.parent = parent;
            return node;
        }
    }

    /**
     * 删除二叉查找树中的某个节点，
     * <strong>因为是二叉查找树，所以是删除某个节点后，需要对剩下的节点进行
     * 重新排序，使之依然是二叉查找树
     * </strong>
     * @param data
     */
    public void deleteNode(int data) {
        //要想删除某个节点，必须先找到这个节点
        TreeNode node = searchNode(data);
        //如果node为空，表示没有找到
        if (node == null) {
            throw new NoSuchElementException("没有指定的节点");
        } else {
            delete(node);
        }
    }

    /**
     * 删除节点
     * @param node 要删除的节点
     */
    private void delete(TreeNode node) {
        if (node == null) {
            throw new NoSuchElementException("没有这个节点");
        } else {
            //如果当前节点不为空，就需要判断这个节点的父节点，左右孩子节点是否为空
            TreeNode parent = node.parent;
            //如果 当前节点为叶子节点，直接删除
            if (node.leftChild == null && node.rightChild == null) {
                //需要判断是父亲的左儿子还是右儿子
                if (parent.leftChild == node) {
                    parent.leftChild = null;
                    node.parent = null;
                } else {
                    parent.rightChild = null;
                    node.parent = null;
                }
            } else if (node.leftChild != null && node.rightChild == null) {
                //如果被删除的节点有左孩子没有右孩子
                //这是还需要判断这个节点是在父节点的左子树上，还是在右子树上
                //如果这个节点在左子树上，就需要把这个节点的左孩子放在parent的左子树上
                if (parent.leftChild == node) {
                    parent.leftChild = node.leftChild;
                } else {
                    parent.rightChild = node.leftChild;
                }
            } else if (node.leftChild == null && node.rightChild != null) {
                //如果被删除的节点有右孩子而没有左孩子
                if (parent.leftChild == node) {
                    parent.leftChild = node.rightChild;
                } else {
                    parent.rightChild = node.rightChild;
                }
            } else if (node.leftChild != null && node.rightChild != null) {
                //如果被删除的节点既有左孩子又有右孩子
                //找后继节点
                TreeNode next = getNextNode(node);
                delete(next);
                node.data = next.data;
            }
        }
    }

    /**
     * 找到某个节点的后继节点
     * @param node
     * @return
     */
    private TreeNode getNextNode(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            //如果这个节点的右子树不为空，就在右子树里面找到key最小的节点
            if (node.rightChild != null) {
                return getMinTreeNode(node);
            } else {
                TreeNode parent = node.parent;
                while (parent == null && node == parent.rightChild) {
                    node = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }

    /**
     * 找到这个节点的子树下面key最小的节点,最小的节点一定在该节点的左子树上的最末端
     * @param node
     * @return
     */
    private TreeNode getMinTreeNode(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            while (node.leftChild != null) {
                node = node.leftChild;
            }
        }
        return node;
    }

    private TreeNode searchNode(int data) {
        TreeNode node;
        //先从根节点开始找
        node = root;
        if (node == null) {
            return null;
        } else {
            while (node != null && data != node.data) {
                if (data > node.data) {
                    node = node.rightChild;
                } else if (data < node.data) {
                    node = node.leftChild;
                } else {
                    return node;
                }
            }
            //当while循环结束后，就表示已经遍历完了整个二叉查找树，
            // 有可能找到，有可能找不到，即node有可能为null
            return node;
        }
    }

    /**
     * 中序遍历二叉查找树，如果树构建的正确，中序遍历出来应该是升序的
     * @param node
     */
    public void midOrderTraverse(TreeNode node) {
        midOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        midOrderTraverse(node.rightChild);
    }

    private static final class TreeNode {
        private int key;//二叉查找树的关键字，通过这个关键字对节点进行排序
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;
        private int data;

        public TreeNode(int key, int data) {
            this.key = key;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }
    }
}