第九章二叉搜索树

二叉搜索树（Binary Search Tree）
二叉树的遍历
二叉树前驱节点
二叉树后继节点
">
练习-反转二叉树
练习-计算二叉树的高度
练习-是否是完全二叉树

二叉搜索树（Binary Search Tree）

二叉搜索树是二叉树的一种，英文简称BST，又被称为二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树分别都是一棵二叉搜索树
二叉搜索树大大提高了搜索数据的效率
二叉搜索树存储的元素必须具备可比较性，比如 int、double
自定义的数据类型，需要指定比较方式
二叉搜索树存储的元素不能是null类型

二叉搜索树的接口设计

int size();//元素的数量
boolean isEmpty()；//是否是空的
void clear();//清空所有元素
void add(E element);//添加元素
void remove(E element);//删除元素

boolean contains(E element);//是否包含指定元素

二叉搜索树的成员变量设计

public class BinarySearchTree<E> {
  private Node<E> root;
  private int size;
  private Comparator<E> comparator;
  public BinarySearchTree(Comparator<E> comparator) {
      this.comparator = comparator;
  }
  public BinarySearchTree() {
  }
  /**
   * if(e1>e2) return 1,
   * if(e1<e2) return -1,
   * if(e1==e2) return 0
   *
   * @param e1
   * @param e2
   * @return
   */
  private int compare(E e1, E e2) {
      if (comparator != null) {
          return this.comparator.compare(e1, e2);
      } else {
          return ((Comparable<E>) e1).compareTo(e2);
      }
  }
   private static class Node<E> {
      E element;
      Node<E> parent;
      Node<E> left;
      Node<E> right;
      public Node(E element, Node<E> parent) {
          this.element = element;
          this.parent = parent;
      }
  }
}

元素的比较方案设计

允许外界传入一个Comparator接口，自定义比较方案
如果没有传入Comparator接口，强制元素实现Comparable接口

神奇的网站

添加元素

二叉树的遍历

遍历时数据结构的常见操作，就是把所有元素访问一遍
线性数据结构的遍历比较简单
- 正序遍历
- 逆序遍历
根据访问节点的顺序不同，二叉树的遍历有以下几种：
- 前序遍历（Preorder Traversal）根左右
- 中序遍历（Inorder Traversal）左根右
- 后序遍历（Postorder Traversal）左右根
- 层序遍历（Level Order Traversal）从上到下、从左到右依次访问每个节点

前序遍历

递归方式

 /**
     * 前序遍历，递归方式
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }
    public void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        //先访问这个节点
        System.out.println(node.element);
        //然后访问这个节点的左子树
        preorderTraversal(node.left);
        //再访问这个节点的右子树
        preorderTraversal(node.right);
    }

非递归方式（使用栈）

   /**
     * 前序遍历、非递归方式、（使用栈第一种方式）
     */
    public void preorderTraversal2() {
        Node<E> node = root;
        Stack<Node> stack = new Stack<>();
        if (node == null) {
            return;
        }
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.println(node.element);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
    /**
     * 前序遍历、非递归方式、（使用栈第二种)
     */
    public void preorderTraversal3() {
        Node<E> node = root;
        Stack<Node> stack = new Stack<>();
        while (node != null) {
            System.out.println(node.element);
            if (node.right != null) {
                stack.push(node.right);
            }
            node = node.left;
            if (node == null && !stack.isEmpty()) {
                node = stack.pop();
            }
        }
    }

中序遍历

递归方式

 /**
     * 中序遍历,左 根 右，递归
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    private void inorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        //左
        inorderTraversal(node.left);
        // 根
        System.out.println(node.element);
        //右
        inorderTraversal(node.right);
    }

非递归方式（使用栈）

 /**
     * 中序遍历，左 根 右，非递归，使用栈，先进后出，后进先出 右 中 左
     */
    public void inorderTraversal2() {
        if (root == null) {
            return;
        }
        Node<E> node = root;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                Node pop = stack.pop();
                System.out.println(pop.element);
                node = pop.right;
            }
        }
    }

后序遍历

递归方式

   /**
     * 后序遍历，左右根 ，递归
     */
    public void postOrderTraversal() {
        postOrderTraversal(root);
    }
    private void postOrderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.println(node.element);
    }

非递归方式（使用栈）

/**
     * 后序遍历，左右根，使用栈
     */
    public void postOrderTraversal1() {
        if (root == null) {
            return;
        }
        Node pre = null;
        Node<E> node = root;
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node cur = stack.peek();
            if (cur.right == null && cur.left == null || (pre != null && (pre == cur.left || pre == cur.right))) {
                stack.pop();
                System.out.println(cur.element);
                pre = cur;
            } else {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

层序遍历（使用队列）

/**
     * 层序遍历，使用队列
     */
    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }
        Node<E> node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

二叉树前驱节点

前驱节点：中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是比它小的前一个节点

  /**
     * 前驱节点
     *
     * @param node
     * @return
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            //这种情况，前驱在左子树的最右子树
            Node<E> pre = node.left;
            while (pre.right != null) {
                pre = pre.right;
            }
            return pre;
        } else if (node.parent != null) {
            while (node != null && node.parent != null) {
                if (node == node.parent.right) {
                    return node.parent;
                }
                node = node.parent;
            }
            return null;
        } else {
            // node.left ==null && node.parent == null
            return null;
        }
    }

二叉树后继节点

/**
     * 后继节点
     *
     * @param node
     * @return
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            //这种情况，后继节点在右子树的最左子树
            Node<E> pre = node.right;
            while (pre.left != null) {
                pre = pre.left;
            }
            return pre;
        } else if (node.parent != null) {
            while (node != null && node.parent != null) {
                if (node == node.parent.left) {
                    return node.parent;
                }
                node = node.parent;
            }
            return null;
        } else {
            // node.right ==null && node.parent == null
            return null;
        }
    }

练习-反转二叉树

/**
 * @description: 反转二叉树
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * @author: huangguoqiang
 * @create: 2021-07-06 17:37
 **/
public class InvertBinaryTree226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode temp = null;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() { }
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

练习-计算二叉树的高度

 /**
     * 计算二叉树的高度，非递归，层序遍历法
     *
     * @return
     */
    public int height1() {

        if (root == null) {
            return 0;
        }
        int height = 0;
        int levelSize = 1;
        Node<E> node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) {
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
     * 计算二叉树的高度，递归
     *
     * @return
     */
    public int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

练习-是否是完全二叉树

  /**
     * 是否是完全二叉树
     *
     * @return
     */
    public boolean isCompleteBinaryTree2() {
        if (root == null) {
            return false;
        }

        boolean isLeaf = false;
        Node<E> node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            if (isLeaf && !(node.left == null && node.right == null)) {
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                // node.left == null && node.right != null ,这种一定不是
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                // (node.left != null && node.right == null) || (node.left == null && node.right == null)
                //这两种情况下，剩下的节点必须是叶子节点 才能是完全二叉树
                isLeaf = true;
            }
        }
        return true;
    }

    /**
     * 是否是完全二叉树
     *
     * @return
     */
    public boolean isCompleteBinaryTree() {
        if (root == null) {
            return false;
        }
        Node<E> node = root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            if (node.left != null && node.right != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else if ((node.left != null && node.right == null)
                    || (node.left == null && node.right == null)) {
                //这两种情况下，剩下的节点必须都是 叶子节点才是 完全二叉树
                if (node.left != null) {
                    queue.offer(node.left);
                }
                while (!queue.isEmpty()) {
                    node = queue.poll();
                    if (node.left != null || node.right != null) {
                        return false;
                    }
                }
                return true;

            }
        }
        return false;
    }

第九章 二叉搜索树

二叉搜索树（Binary Search Tree）

二叉搜索树的接口设计

二叉搜索树的成员变量设计

元素的比较方案设计

神奇的网站

添加元素

二叉树的遍历

前序遍历

递归方式

非递归方式（使用栈）

中序遍历

递归方式

非递归方式（使用栈）

后序遍历

递归方式

非递归方式（使用栈）

层序遍历（使用队列）

二叉树前驱节点

二叉树后继节点

练习-反转二叉树

练习-计算二叉树的高度

练习-是否是完全二叉树