二叉树 | 胡椒粉的秋天

概念

关于“树”，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

节点的高度=节点到叶子节点的最长路径（边数）

节点的深度=根节点到这个节点所经历的边的个数

节点的层数=节点的深度+1

树的高度=根节点的高度

二叉树的高度深度层数

其中有两种特殊的二叉树：

二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。

二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

存储结构

为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树？这就要从二叉树存储方面说起了。

想要存储一棵二叉树，我们有两种方法，

一种是基于指针或者引用的二叉链式存储法。
一种是基于数组的顺序存储法。

链式存储

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

二叉树的链式存储

顺序存储

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

完全二叉树的顺序存储

我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

不过，我刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。

非完全二叉树的顺序存储

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

当我们讲到堆和堆排序的时候，你会发现，堆其实就是一种完全二叉树，最常用的存储方式就是数组。

二叉树的遍历

如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。

前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

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

深度优先遍历（递归）

Leetcode: 144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
void traversal(TreeNode *cur, vector<int> &res) //1、递归需要的参数和返回值
{
    if(NULL == cur) //2、递归终止条件，当前节点等于空，直接返回
    {
        return;
    }
    //3、递归中的逻辑，前序遍历（中左右）
    res.push_back(cur->val);
    traversal(cur->left, res);
    traversal(cur->right, res);
}

func traversal(root *TreeNode, res *[]int) {
    if root == nil{
        return
    }
    *res = append(*res, root.Val)
    traversal(root.Left, res)
    traversal(root.Right, res)
}

广度优先遍历（层序遍历）

Leetcode：107.二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

给定二叉树 [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

返回其自底向上的层序遍历为：

[

[15,7],

[9,20],

[3]

]

vector<vector<int>> levelOrderBottom(TreeNode* root) 
{
    //层序遍历方式就是图论中的广度优先遍历
    //用辅助队列实现，先进先出，符合一层一层遍历的逻辑
    queue<TreeNode*> que;
    if(NULL != root)
    {
        que.push(root);
    }
    vector<vector<int> > res;
    while(!que.empty())   //循环一次，处理树的一层
    {
        //开始对处理队列里的值，先取出当前队列中节点的val，然后队列弹出该值，然后再获取节点的左右节点，存入队列中
        int iSize = que.size();   //循环一次，处理一个节点
        vector<int> vec;
        for(int i = 0; i < iSize; ++i)// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
        {
            TreeNode *cur = que.front();
            vec.push_back(cur->val);
            que.pop();  //弹出在front位置的值
            if(cur->left != NULL)   que.push(cur->left);
            if(cur->right != NULL)   que.push(cur->right);
        }
        res.push_back(vec);
    }
    reverse(res.begin(), res.end());    //最后进行翻转
    return res;
}

func levelOrderBottom(root *TreeNode) [][]int {
    res := make([][]int, 0, 10)

    queue := make([]*TreeNode, 0, 10)
    if root == nil{
        return res
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)

        level := make([]int, 0, 10)
        for i:=0; i < size; i++ {
            node := queue[0]    //  永远都是取第0个
            queue = queue[1:]  // 截断，取后面值
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level)
    }

    for i := 0; i < len(res) / 2; i++ {
        res[i], res[len(res) - 1 - i] = res[len(res) - 1 - i], res[i]
    }
    return res
}

二叉查找树（Binary Search Tree）

二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树

查找操作

Leetcode：700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

/ \

2 7

/ \

1 3

和值: 2

你应该返回如下子树:

/ \

1 3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

思路分析：因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

这里可能会疑惑，在递归遍历的时候，什么时候直接return 递归函数的返回值，什么时候不用加这个 return呢。如果要搜索一条边，递归函数就要加返回值，这里也是一样的道理。

因为搜索到目标节点了，就要立即return了，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。

TreeNode* searchBST(TreeNode* root, int val) 
{
    if(root == NULL)    return root;
    if(root->val > val) return searchBST(root->left, val);
    else if(root->val < val)    return searchBST(root->right, val);
    else if(root->val == val)   return root;

    return NULL;
}

其他操作

二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。

有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

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

实际上，二叉查找树的形态各式各样。比如这个图中，对于同一组数据，我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。

各式各样的二叉查找树

图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。

显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是一种特殊的二叉查找树，平衡二叉查找树。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

二叉查找树与哈希表区别

相对散列表，二叉查找树好像并没有什么优势，那我们为什么还要用二叉查找树呢？我认为有下面几个原因：

第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

平衡二叉查找树（Balanced BST）

基于BST存在的问题，平衡二叉查找树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡树分别为AVL树和红黑树。

AVL树

1.它的左子树和右子树都是平衡二叉树；
2.且它的左子树和右子树的深度之差的绝对值（平衡因子）不超过1；

简单的说，就是为了保证平衡，当前节点的左子树、右子树的高度差不超过1！当树的左、右子树高度超过差超过1时，核心就是通过左旋转、右旋转实现树再次高度平衡。

红黑树Red-Black Tree（RBTree）

1.任何一个节点都有颜色，红色或黑色
2.根节点是黑色的
3.如果一个节点是红色的，则它的两个子节点都是黑色的
4.从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点（即，黑色节点的高度相等）
5.所有叶子节点（NIL节点，空节点）都是黑色

红黑树

它的数据结构如下：

class Node<T>
{
    public T value;
    public Node<T> parent;
    public boolean isRed;
    public Node<T> left;
    public Node<T> right;
}

因为以上规则的限制，保证了红黑树的自平衡。红黑树从根到叶子节点的最长路径不会超过最短路径的2倍。

作为二叉查找树中面众多的实现之一，红黑树通过引入颜色的概念，通过颜色约束的使用，包括变色和旋转，来保持树的高度平衡。即使在最坏的情况下，操作的时间复杂度也为O(LogN)，原因是整个红黑树的高度保持是LogN(因为旋转修复)，N 为树中的顶点数目。

红黑树RBT与平衡二叉树AVL比较

AVL 树比红黑树更加平衡，但AVL树在插入和删除的时候也会存在大量的旋转操作。所以当你的应用涉及到频繁的插入和删除操作，切记放弃AVL树，选择性能更好的红黑树；当然，如果你的应用中涉及的插入和删除操作并不频繁，而是查找操作相对更频繁，那么就优先选择 AVL 树进行实现。

B-树

B-树是一种多路自平衡的搜索树（B树是一颗多路平衡查找树），它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。

规则：

（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；

（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；

（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);

（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等，这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了，它们由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。因为当数据量非常大时，内存不够用，这时使用B-树作为索引，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。

B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。

B-树结构图

B树的查询流程：

如上图我要从上图中找到E字母，查找流程如下

（1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

（2）拿到关键字D和G，由于D<E<G ，所以直接找到D和G中间的节点；

（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

B+树

规则：

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

（4）非叶子节点的子节点数=关键字数;

B树和B+树，本质上都是一样的，只是B+树所有的跟节点和枝节点上只保存关键字索引和其子节点指针，所有的数据信息都被保存到了叶子节点，这样每个枝节点可以存储更多的数据，从而降低树的层级高度，并且所有的叶子节像是一个链表一样，指向右边的叶子节点，从而可以有效加快检索效率，如果需要遍历所有的数据，只需要遍历叶子节点链式结构即可，方便且高效。

带顺序访问的B+树

B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据。