二叉树的由来

在 jdk1.8 之前，HashMap 的数据结构由「数组+链表」组成，数组是 HashMap 的主体，链表是为了解决 Hash 冲突引入的，正常的数据存放是直接存在数组中，但如果发生 Hash 冲突就会以链表的形式进行存储，而在 jdk1.8之后，当链表的长度超过 8 之后，将会转换成红黑树存储。

清楚HashMap八股文的小伙伴应该知道，为何随着版本的迭代会引入不同的数据结构呢？

数组 > 链表 > 树

✧ 数组

优点	缺点
简单易用，随机访问性强	插入和删除效率低
无序数组插入速度很快，效率为O1	数组大小固定，无法动态扩容
有序数组查找速度较快，效率为O(logN)

✧ 链表

优点	缺点
大小不固定，无限扩容	查询效率低，不支持随机查找，必须从第一个开始遍历
插入和删除速度很快	在链表非表头的位置进行插入、删除很慢，效率为O(N)

二叉树：整合了数组和链表的优缺点，使得插入、删除、查找的速度都很快，效率比较高。

什么是二叉树？

二叉树是每个结点最多有两个子树的树结构。即“左子树” 和“右子树”。本身是有序树

例如，图1) 就是一棵二叉树，而图 2) 则不是，其子节点数>2

二叉树类型

1、满二叉树

每一个节点点中都两棵深度相同的子树，且叶子节点都在最底层。

例如图 2)是一颗满二叉树， 图1) 不是，其4节点没有左右子树，而相邻的10节点有左右子树

2、完全二叉树

二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布

如图a) 所示是一棵完全二叉树，图b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。

3、二叉查找树（二叉排序树）

查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集。

☛ 特点

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

3. 左、右子树也分别为二叉排序树。

如上图：二叉查找树中，左子树都比节点小，右子树都比节点大。

根据二叉排序树可知：二叉排序树的中序遍历一定是从小到大的。

比如上图，中序遍历结果是：

1 3 4 6 7 8 10 13 14

☛ 极端现象

二叉查找树可能存在，大部分子节点都比父节点值小，导致所有的数据偏向左侧，进而退化成链表，如下图所示：

4、平衡二叉树（AVL树）

解决二叉树退化成链表而引入了平衡二叉树，特点是尽量保证两边平衡，高度差<=1

☛ 特点

1. 平衡二叉树要么是一棵空树，要么保证左右子树的高度之差不大于 1

2. 子树也必须是一颗平衡二叉树

假设如下图，以8为根节点，左子树为0，右子树为1（10），如果此时再加入节点15，就会导致该二叉树不平衡，因为8的左子树一个都没有，右子树有2个节点，高度差为2，不满足平衡二叉树。

平衡二叉树在添加和删除时需进行旋转保持整个树的平衡，内部做了这么复杂的工作后，在使用它时，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。（上图旋转为平衡树如下：）

二叉树遍历

• 前序遍历：根、左子、右子
• 中序遍历：左子、根、右子
• 后序遍历：左子、右子、根
• 层次遍历：一层一层遍历

准备1：先创建一个TreeNode实体类，如下：

public static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;
        TreeNode(String val) {
            val = val;
        }

        @Override
        public String toString() {
            return val + " ";
        }
 }

 准备2：其次，编写创建二叉树的方法，如下

// 根据数组{ "3", "9", "20", null, null, "15","7"}，转换为二叉树
public static TreeNode createTreeNode(String[] array, int index){
        TreeNode treeNode = null;

        // index为数组的下标，等同遍历数组，拆分数组的元素存储为树型结构
        if (index < array.length) {
            // 一般第一个根节点，初始下标为0，即数组的第一个元素为顶根节点
            treeNode = new TreeNode(array[index]);

            // 对于顺序存储的完全二叉树，如果某个节点的索引为index，
            // 其对应的左子树的索引为2*index+1，右子树为2*index+2
            treeNode.left = createTreeNode(array, 2 * index + 1); // 1、3、5
            treeNode.right= createTreeNode(array, 2 * index + 2); // 2、4、6
        }
        return treeNode;
}

✧ 说明：第一个node为arr[0]，即3，3的左子树为：2*index+1，也就是数组中下标为1的元素9，右子树同理。那么已知下标0为顶根节点，故所有左子树取奇数下标，所有右子树取取奇数下标，然后递归执行创建其子节点。

准备3：main方法调用创建二叉树，如下

/* 假设需要创建的二叉树结构如下
        3
       / \
      9   20
         /  \
        15   7
*/
public static void main(String[] args) {
        String[] array = { "3", "9", "20", null, null, "15","7"};
        // 创建二叉树
        TreeNode node = createTreeNode(array,0);
}

1、前序遍历

根结点 → 左子树 → 右子树

 代码如下：

// 递归 前序遍历（根、左、右）
public static void before(TreeNode node) {
      if (node != null) {
           System.out.print(node); // 打印根
           before(node.left);      // 打印左
           before(node.right);     // 打印右
      }
}

执行结果：因为树型结构已经完整了，按照打印顺序执行输出打印即可

前序遍历二：非递归 方式一

// 非递归二叉树前序遍历
public static void before2(TreeNode node) {
     Stack<TreeNode> stack = new Stack<>();
     if (node != null) {
         // a.顶根节点入栈   ①
         stack.push(node);

         // b.栈不为空
         while (!stack.empty()) {

             // c.将栈中存入的节点元素进行出栈   
             node = stack.pop();          // ②
             System.out.print(node);

             // d.判断该节点是否有右树，有则把右子节点进行入栈
             if (node.right != null) {
                 stack.push(node.right);   // ③
             }

             // e.是否有左树，有则把左子节点进行入栈
             if (node.left != null) {
                stack.push(node.left);   // ④
             }
          }
    }
}

☛ 流程详解

第一次：把根节点3压入栈中，栈不为空故再把3出栈，并判断3是否有子节点，把其子节点入栈

栈底部序号，参考上述代码中的执行序号

第二次循环：根绝栈中元素，栈顶的元素9出栈，并判断节点9是否有子节点，把其子节点入栈

第三次循环：栈顶元素为null (此null 非空，是数组中存在的元素)，继续出栈，由于null的子节点为空，故不会进入压栈操作，即 ③④

第四次循环：同步骤三

第五次循环：将目前栈中最后一个元素进行出栈，并将其子节点压入栈

第六次循环：由于15无子树，故不会进入压栈操作，即 ③④

第七次循环：同步骤6

 

☁ 思考：为何代码③的位置，要先把右子树压入栈

前序遍历：根→左子树→右子树

答：因为栈的特性，先入栈的元素，会放入栈底，而出栈，会先把栈顶的元素先出，故先把右子树压入栈，就能保证左子树先出

前序遍历三：非递归 方式二

/*    3
     / \
    9   20
       /  \
      15   7
*/
public static void before3(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        // 初始：当前node = 根节点3
        TreeNode node = root;
        while (node != null || !stack.empty()) {

            // 当前node不为空，则打印node,并压入栈，赋值：当前node=当前node的左子树
            // ①
            if (node != null) {        
                System.out.print(node.val + " "); 
                stack.push(node);
                node = node.left;

            // 当前node为空，但stack栈不为空，则出栈该元素，赋值：node=当前node的右子树
            // ②
            } else {
                TreeNode tem = stack.pop();   
                node = tem.right;
            }
        }
}

☛ 流程详解

第一次：当前node=3，进入if 语句，将其3压入栈，并设置node=node.left（即3的左子树9)，由于9的左子树(null) 也不为空，故依次压入栈中。

栈底部序号，参考上述代码中的执行序号

第二次：由于步骤1中设置了 node=node.left，即最后元素为null旗下无子节点，故进入else，将其栈中元素进行出栈

第三次：如下图

第四次：由于步骤3中，9存在右子节点，即“null”，满足进入if 条件，将9的右子节点null压入栈，并赋值当前node=node.left（null无子节点，所以当前node为空）

 第五次：由于node为空，故进入else，将栈中元素出栈

 

第六次：继续将栈中元素出栈，并判断栈中最后元素3，有右子节点20，故将其node=20

 第七次：当前node=20，满足进入if条件，并依次判断当前node是否有左子节点，并将其压入栈

 第八次：15无左子节点，故当前node为空，进入else，将15出栈，并赋值node=15的右子树(空)

第九次：此时栈中还剩20，继续出栈，并判断其20是否有右子节点，赋值node=20的右子节点7

 第十次：由于node=7(是20的右子节点)，故进入if语句，将7压入栈中

第十一次：将最后元素7出栈，由于7无子节点，故循环结束

2、中序遍历

左子树 → 根结点 → 右子树

// 递归 中序遍历（左、根、右），方法同前序遍历，只是根的打印位置不同
public static void before(TreeNode node) {
      if (node != null) {
           before(node.left);      // 打印左
           System.out.print(node); // 打印根  ---调换前序遍历中，根的打印位置即可！
           before(node.right);     // 打印右
      }
}

执行结果：

中序遍历二：非递归

就是将前序 非递归方式二 中的打印位置，放到else语句中，如下

3、后序遍历

左子树 → 根结点 → 右子树

// 递归 中序遍历（左、根、右），方法同前序遍历，只是根的打印位置不同
public static void before(TreeNode node) {
      if (node != null) {
           before(node.left);      // 打印左
           before(node.right);     // 打印右
           System.out.print(node); // 打印根  ---调换前序遍历中，根的打印位置即可！
      }
}

执行结果：

4、层次遍历

先遍历第一层，再遍历第二层，以此类推

// 层次遍历，根据队列的有序特性，按照顺序依次放入队列，再出队
public static void level(TreeNode treeNode){
        Queue<TreeNode> queue = new LinkedList<>();
        if(treeNode==null){
            return;
        }
        // 1.顶根节点放入队列
        queue.add(treeNode);
        
        // 2.如果队列不为空
        while (!queue.isEmpty()){

            // 3.将队列元素出队
            TreeNode node = queue.poll();
            System.out.print(node); // 打印

            // 4.如果当前出队的元素，有左子节点，则放入队列
            if(node.left!=null){
                queue.add(node.left);
            }

            // 5.如果当前出队的元素，有右子节点，则放入队列
            if(node.right!=null){
                queue.add(node.right);
            }
        }
}

执行结果：

思考：为什么MySQL不选择二叉树作为索引数据结构

无论是二叉查找树、AVL 树、红黑树，都是二叉树，特点：每个结点最多只有两个子结点

• 树太高，操作数据时会发生多次磁盘 IO，性能太差。
• 二叉树单边过长（极端的二叉查找树），易退化成链表。

MySQL 应用程序读取数据时，需要将数据从磁盘先加载到内存后才能继续操作，这中间会发生磁盘 IO，如果树太高，每遍历一层结点时，就需要从磁盘读取一次数据，即发生一次 IO

➳ 结论

磁盘读取是按照磁盘块来读取的，并不是一条一条的读。如用树作为索引的数据结构，每查找一次数据就需从磁盘中读取一个节点，即磁盘块。而二叉树每个节点只存储一个键值和数据的。。。即如果数据在树高为 20 的地方，查找一次数据就得发生 20 次 IO，耗时太长了。

☛ 举例说明：

因数据库索引是存储在磁盘上，如果数据量大，意味着索引的大小可能有几个G甚至更多，不可能将整个索引全部加载到内存，只能逐一加载每一个磁盘页，即索引树的节点

假设如下二叉树，其高度是4，查找的元素是22

第一次磁盘IO：先从根节点出发，顺着路径查找

第二次磁盘IO：因二叉树的特性，左子树<根节点<右子树，22>12，故需查找12的右子树节点

第三次磁盘IO：由于22比24小，故查找24的左子树节点 

第四次磁盘IO：由于22比20大，故查找22的右子树节点 

完整的查找链如下： 

磁盘IO的次数，等同于该节点到根节点的树高，如果一个元素存放在h高的节点，那么查找该节点就要 h 次磁盘IO