二叉树的定义

• 二叉树具有唯一根节点
• 二叉树每个节点最多有两个孩子
• 二叉树每个节点最多有一个父亲
• 二叉树具有天然的递归结构
  • 每个节点的左子树也是二叉树
  • 每个节点的右子树也是二叉树
  • 二叉树不一定是“满”的（意思是可能只有左孩子或右孩子,因为null也可能是二叉树）

二分搜索树

• 二分搜索树首先是二叉树
• 二分搜索树的每个节点的值：
  • 大于其左子树的所有节点的值
  • 小于其右子树的所有节点的值
  • 因此存储的元素必须具有可比较性

• 目前二分搜索树不包含重复的元素，如果想包含重复元素，只需要定义
  • 左子树小于等于节点
  • 或者右子树大于等于节点

二叉搜索树的代码

    private class Node {
        public E e;
        public Node left, right;
        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }
    private Node root;
    private int size;
    public BST() {
        root = null;
        size = 0;
    }
    public int size() {
        return size;
    }
    public boolean inEmpty() {
        return size == 0;
    }

添加子节点递归代码

    //往二叉树中插入一个元素
    public void add(E e) {
        root = add(root, e);
    }
    //递归插入一个元素
    //返回插入新节点后二分搜索树的跟
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        //递归
        if (node.e.compareTo(e) > 0) {
            node.left = add(node.left, e);
        } else if (node.e.compareTo(e) < 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

添加子节点非递归代码

//非递归写法插入一个元素
    public void addNR(E e){
        if (root == null){
            root = new Node(e);
            size++;
            return;
        }
        Node p = root;
        while (p!=null){
            //如果插入的值小于当前值则插到左边
            if (e.compareTo(p.e) < 0){
                //如果左子树为空就放在左子树
                if (p.left == null){
                    p.left = new Node(e);
                    size++;
                    return;
                }else{
                    p = p.left;
                }
            }else if (e.compareTo(p.e) > 0){
                if (p.right == null){
                    p.right = new Node(e);
                    size++;
                    return;
                }else{
                    p = p.right;
                }
            }else {
                return;
            }
        }
}

前序遍历

• 前序遍历过程

• 前序遍历代码
• 图示(递归)

前序遍历的非递归形式

    /**
     * 前序遍历的非递归写法
     */
    public void preOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left  != null){
                stack.push(cur.left);
            }
        }
    }

• 图示

中序遍历

• 中序遍历图示

• 中序遍历代码

    /**
     * 中序遍历
     * 中序遍历的结果是顺序的
     */
    public void inOrder() {
        inOrder(root);
    }
    private void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

  
  

  后序遍历

• 应用

  • 为二分搜索树释放内存
• 后续遍历图示

• 后序遍历代码

    /**
     * 后续遍历
     * @return
     */
    public void postOrder() {
        postOrder(root);
    }
    private void postOrder(Node node) {
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

  二分搜索树的层序遍历

• 层序遍历图示

• 广度优先遍历的意义
  • 常用于算法设计中-最短路径

• 广度优先算法代码

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> sublist = new ArrayList<>();
            int queueLength = queue.size();
            for (int i = 0; i < queueLength; i++) {
                TreeNode node = queue.remove();
                sublist.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            res.add(sublist);
        }
        return res;
    }

删除二分搜索树的最小值和最大值

• 很明显，最小值是从根节点开始最左边，最大值是从根节点开始最右边的点

删除节点

    /**
     * 二分搜索树删除节点
     * @return
     */
    //删除以node为根的二分搜索树中值为e的节点，递归算法
    //返回删除节点后新的的二分搜索树的根
    public Node remove(Node node , E e){
        if (node == null)
            return null;
        if (e.compareTo(node.e) < 0 ){
            node.left = remove(node.left,e);
            return node;
        }else if(e.compareTo(node.e) > 0){
            node.right = remove(node.right,e);
            return node;
        }else{  // e == node.e
            //待删除的节点的左子树为空
            if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //待删除的节点的右子树为空的情况
            if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //待删除的节点左右子树均不为空的情况
            //找到比要删除节点大的最小子节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }