1. 二叉树基础

    学习树这种数据结构之前，需要熟悉数组、链表、栈、队列，如果都已经熟悉了，那么学习树就容易多了。

    首先来看几棵树，让大家对树有个大致的认识

关于树的几个概念

    父结点、子结点、兄弟结点、 根结点、叶子结点

    A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫做根节点，也就是图中的节点 E。我们把没有子节点的节点叫做叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。

    高度、深度、层次

    结点的高度： 结点到叶子结点的最长路径

    结点的深度：根结点到这个结点的路径长度

    结点的层次： 结点的深度 加 1

    树的高度： 根结点的高度

二叉树、完全二叉树、满二叉树

    树结构多种多样，不过最常用还是二叉树。二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。但是不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。以下三棵树都是二叉树：

    叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树（上图中的第二棵树）

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树（上图中的第三棵树）以下两棵树不是完全二叉树

二叉树的存储方式

    想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

    链式存储法。从图中你应该可以很清楚地看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

    基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

    节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。

    堆其实就是一种完全二叉树，最常用的存储方式就是数组。

二叉树的遍历

    经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历的先后顺序。

    前序遍历是指，对于树中的任意节点来说，先遍历这个节点，然后再遍历它的左子树，最后遍历它的右子树。

    中序遍历是指，对于树中的任意节点来说，先遍历它的左子树，然后再遍历它本身，最后遍历它的右子树。

    后序遍历是指，对于树中的任意节点来说，先遍历它的左子树，然后再遍历它的右子树，最后遍历这个节点本身。

    二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先遍历根节点，然后再递归地遍历左子树，最后递归地遍历右子树。

    二叉树的遍历代码模板

    # Python

    def recursion(level, param1, param2, ...): 

        # recursion terminator 

        if level > MAX_LEVEL: 

       process_result 

       return 

        # process logic in current level 

        process(level, data...) 

        # drill down 

        self.recursion(level + 1, p1, ...) 

        # reverse the current level status if needed

    // Java

    public void recur(int level, int param) { 

      // terminator 

      if (level > MAX_LEVEL) { 

        // process result 

        return; 

      }

      // process current logic 

      process(level, param); 

      // drill down 

      recur( level: level + 1, newParam); 

      // restore current status 

    }

    // C/C++

    void recursion(int level, int param) { 

      // recursion terminator  递归终止条件

      if (level > MAX_LEVEL) { 

        // process result 

        return ; 

      }

      // process current logic   处理当前递归层的逻辑

      process(level, param);

      // drill down   处理子问题

      recursion(level + 1, param);

      // reverse the current level status if needed   处理当前递归层的状态

    }

二叉搜索树（Binary Search Tree）

    二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

    1. 二叉查找树的查找操作

    先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

2. 二叉查找树的插入操作

    如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

3. 二叉查找树的删除操作

    需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

支持重复数据的二叉查找树

    第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

    第二种方法比较不好理解，不过更加优雅。

    每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

    当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

二叉查找树的时间复杂度分析

    二叉查找树的形态各式各样，比如这个图中，对于同一组数据，我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。二叉查找树是一棵完全二叉树（或满二叉树）。这个时候，插入、删除、查找的时间复杂度O(height)，对于完全二叉树的height是小于等于 log2n，平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。