第28章 架构师必备的核心数据结构之二叉树

第 1 集 查找算法之二分查找思想和快速编码实现

简介： 查找算法之二分查找思想和编码实现

• 注意

  • 平时写业务代码的时很少写对应的算法，因为很少会在内存中存储大量数据
  • 在需要比较大量数据的查找时，多会依赖的中间件，而中间件底层就应用了很多不同算法，尤其是树结构的查找存储算法
  • 二分查找算法在树里面有大量应用，所以需要讲下，这个也是上机面试比较高频应用的算法

• 二分查找算法

  • 也称折半查找（Binary Search），它是一种效率较高的查找方法，时间复杂度 O（log2n）

  • 要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

  • 在数据量大的情况，比线性查找性能高；在数据量少的情况和线性查找差不多

• 线性查找和二分查找效果对比

  • 演示动画：https://www.cs.usfca.edu/~galles/visualization/Search.html

• 快速编码实现（可以用循环或者递归）

  public class BinarySearch {
      public static void main(String[] args) {
          // 定义一个有序数组
          int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
          // 要查找的元素
          int target = 7;
          // 调用二分查找算法
          int index = binarySearch(arr, target);
          if (index == -1) {
              System.out.println("查找的元素不存在");
          } else {
              System.out.println("查找的元素下标为：" + index);
          }
      }
  
      /**
       * 二分查找算法
       *
       * @param arr    有序数组
       * @param target 要查找的元素
       * @return 返回元素在数组中的下标，如果没有找到返回-1
       */
      public static int binarySearch(int[] arr, int target) {
          // 记录开始位置
          int start = 0;
          // 记录结束位置
          int end = arr.length - 1;
          // 记录中间位置
          int mid;
          // 循环查找
          while (start <= end) {
              // 计算中间位置
              mid = (start + end) / 2;
              // 比较中间位置的值
              if (arr[mid] == target) {
                  // 找到元素，返回下标
                  return mid;
              } else if (arr[mid] < target) {
                  // 中间元素小于目标元素，则在右边查找
                  start = mid + 1;
              } else {
                  // 中间元素大于目标元素，则在左边查找
                  end = mid - 1;
              }
          }
          // 没有找到元素
          return -1;
      }
  }
  

第 2 集 树基础快速回顾和二叉树的遍历

简介：树基础快速回顾和二叉树的遍历

• 什么是树
  • 是一种非线性的数据结构，它具有层次结构，根节点是树的最高层，叶节点是最低层
  • 树可以分为二叉树、平衡树、红黑树、B 树、B+树等
  • 常见术语
    • 根节点：在非空树中没有前驱结点的结点，被称为根节点（注意，只有一个根节点）
    • 父节点：每个节点除了根节点外，都有一个父节点
    • 子节点：每个节点都可以有 1 个或多个子节点
    • 叶节点：没有子节点的节点称为叶节点
    • 节点的度：结点所拥有子树个数，叶子结点就是度为 0 的结点
    • 树的度：树里的各个节点度的最大值
    • 层数：根节点为第一层，往下一次递增。
    • 高度（深度）：结点的深度指从根节点自顶向下逐层累加至该结点时的深度，树的深度是树中深度最大的结点的深度。
    • 路径：从一个节点到另一个节点的序列称为路径
    • 森林：由一组树组成的集合称为森林

• 什么是二叉树

  • 树有很多种，但是每一个结点最多只有两个子节点的树，被称作为二叉树。

  • 二叉树的子节点又分成左节点与右节点

  • 二叉树遍历过程中，每个结点都被访问了一次，时间复杂度是 O(n)

  • 注意

    • 为啥重点强调二叉树的遍历和编码实现呢？
    • 在树的大家族中，二叉树是特别高频使用的树，利用二叉树特性，变种延伸特别多（选择关键的讲）
      • 完全二叉树
      • 满二叉树
      • 二叉查找树（二叉排序树）
      • 平衡二叉树(AVL 树)
      • B-Tree
      • B+Tree
      • 红黑树（自平衡的二叉查找树，JDK 1.8 后的 HashMap 的存储结构）
      • ...

  • 二叉树的遍历（面试高频）

    • 二叉树分成根节点、左子树和右子树， 根据根节点什么时候被访问，把二叉树遍历分成三种方式
    • 前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树
      • A B D H E I J C F G
    • 中序遍历：首先访问左子树，然后到根节点，最后才到右子树
      • D H B I E J A F C G
    • 后序遍历：首先访问左子树，然后到右子树，最后到根节点
      • H D I J E B F G C A

• 二叉树拓展

  • 满二叉树

    • 每个节点都有 0 个或者 2 个子节点的二叉树，叶节点都在最底层的二叉树，节点的总数=2^n-1（n 为层数）
    • 外观看上去是完整的一个三角形
    • 下图例子：节点总数=2^4-1=15

    

  • 完全二叉树

    • 只有最下面两层节点的度可以小于 2，并且最下层的叶节点集中在靠左连续的边界
    • 只允许最后一层有空缺结点且空缺在右边
    • 完全二叉树需保证最后一个节点之前的节点都齐全；
    • 对任一结点，如果其右子树的深度为 j，则其左子树的深度必为 j 或 j+1
    • 如果把 G 节点删除的话，它就不属于完全二叉树了，因为它的叶子结点已经是不连续了

    

  • 区别

    • 满二叉树的叶节点都在最底层；完全二叉树只有最下面两层节点的度可以小于 2，且最下层的叶节点集中在靠左的边界

第 3 集 核心数据结构之二叉树遍历编码实战《上》

简介： 核心数据结构之二叉树遍历编码实战《上》

• 树的遍历分为

  • 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，且每个节点只访问一次，访问完一颗子树再去访问后面的子树

    • 前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树
    • 中序遍历：首先访问左子树，然后到根节点，最后才到右子树
    • 后序遍历：首先访问左子树，然后到右子树，最后到根节点

  • 广度优先遍历：从根节点到叶子节点的层次关系，一层层横向遍历各个节点，访问树结构的第 n+1 层前必须先访问完第 n 层

  

• 上机编码

  • 深度优先遍历 实现二叉树的插入、前序、中序、后序查找
  • 树的定义本身是递归定义，因此采用递归的方法去实现树的三种遍历，容易理解而且代码很简洁

  public class BinaryTree {
  
      // 根节点
      TreeNode root;
  
      public void insertNode(int data) {
          root = insert(root, data);
      }
  
      private TreeNode insert(TreeNode treeNode, int data) {
          //如果是空则插入第一个节点
          if (treeNode == null) {
              return new TreeNode(data);
          }
          //插左边
          if (data < treeNode.data) {
              treeNode.leftChild = insert(treeNode.leftChild, data);
          }
          //插右边
          else if (data > treeNode.data) {
              treeNode.rightChild = insert(treeNode.rightChild, data);
          } else {
              treeNode.data = data;
          }
          return treeNode;
      }
  
  
      // 前序遍历
      public void preOrder(TreeNode root) {
          if (root == null) {
              return;
          }
          System.out.print(root.data + " ");
          preOrder(root.leftChild);
          preOrder(root.rightChild);
      }
  
      // 中序遍历
      public void inOrder(TreeNode root) {
          if (root == null) {
              return;
          }
          inOrder(root.leftChild);
          System.out.print(root.data + " ");
          inOrder(root.rightChild);
      }
  
      // 后序遍历
      public void postOrder(TreeNode root) {
          if (root == null) {
              return;
          }
          postOrder(root.leftChild);
          postOrder(root.rightChild);
          System.out.print(root.data + " ");
      }
  }
  
  class TreeNode {
      int data;
      //左节点
      TreeNode leftChild;
      //右节点
      TreeNode rightChild;
  
      TreeNode(int data) {
          this.data = data;
      }
  }
  

第 4 集 核心数据结构之二叉树遍历编码实战《下》

简介： 核心数据结构之二叉树遍历编码实战《下》

• 构建测试数据

   public static void testBinaryTree(){
          BinaryTree btt=new BinaryTree();
          btt.insertNode(93);
          btt.insertNode(33);
          btt.insertNode(51);
          btt.insertNode(21);
          btt.insertNode(102);
          btt.insertNode(42);
          btt.preOrder(btt.root);
          System.out.println();
          btt.inOrder(btt.root);
          System.out.println();
          btt.postOrder(btt.root);
      }
  
  

• 输出结果

  前序：93 33 21 51 42 102
  
  中序：21 33 42 51 93 102
  
  后序：21 42 51 33 102 93