数据结构与算法之二叉树、二叉搜索树、平衡二叉树、红黑树、B - 树、哈夫曼树等详细教程（更新中）

第一章、二叉树概述和基本算法

1.1 二叉树遍历算法概述

对于二叉树，其实遍历顺序一共有6种，基于有左子树，右子树，根这三个因素，即排列组合有3 * 2 * 1=6种结合顺序，不过因为算法思想是一样的，就没有必要把左右子树的先后再分开讨论，所以普遍认为左子树优先右子树。

二叉树遍历的应用：

（1）前序遍历：可以用来实现目录结构的显示。

（2）中序遍历：可以用来做表达式树，在编译器底层实现的时候用户可以实现基本的加减乘除，比如 $a\ast b+c$。

（3）后序遍历：可以用来实现计算目录内的文件占用的数据大小，非常有用。

前序遍实现目录结构的显示

对于前序遍历，可以用来实现输出某个文件夹下所有文件名称(可以有子文件夹)，就是目录结构的显示。

输出文件名称的过程如下：

如果是文件夹，先输出文件夹名，然后再依次输出该文件夹下的所有文件(包括子文件夹)，如果有子文件夹，则再进入该子文件夹，输出该子文件夹下的所有文件名。这是一个典型的先序遍历过程。

后序遍历实现计算目录内的文件占用的数据大小

对于后序遍历，可以用来统计某个文件夹的大小（该文件夹下所有文件的大小）

统计文件夹的大小过程如下：

若要知道某文件夹的大小，必须先知道该文件夹下所有文件的大小，如果有子文件夹，若要知道该子文件夹大小，必须先知道子文件夹所有文件的大小。这是一个典型的后序遍历过程。

1.2 二叉树前序遍历

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子书。

前序遍历的规则： （1）访问根节点 （2）前序遍历左子树 （3）前序遍历右子树

特点：① 根 > 左 > 右 ② 根据前序遍历的结果可知第一个访问的必定是 root 结点。

前(先)序遍历图例

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

数据范围：二叉树的节点数量满足 $1\le n\le 100$ ，二叉树节点的值满足 $1\le val\le 100$，树的各节点的值各不相同。

方法一：递归（推荐使用）在这里插入代码片

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

算法思路：

什么是二叉树的前序遍历？简单来说就是“根左右”，展开来说就是对于一颗二叉树优先访问其根节点，然后访问它的左子树，等左子树全部访问完了再访问其右子树，而对于子树也按照之前的访问方式，直到到达叶子节点。

从上述前序遍历的解释中我们不难发现，它存在递归的子问题：每次访问一个节点之后，它的左子树是一个要前序遍历的子问题，它的右子树同样是一个要前序遍历的子问题。那我们可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。
1
2
3

代码展示如下：

void preorder(vector<int> &res, TreeNode* root){
        // return when meet blank node
        if(root == NULL)
            return;
        // first traverse root node
        res.push_back(root->val);
        // then travese left-sub-tree
        preorder(res, root->left);
        // finally travese right-sub-tree
        preorder(res, root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        // recursion preorderTraversal
        preorder(res, root);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n)，其中 n 为二叉树的节点数，遍历二叉树所有节点

空间复杂度：O(n)，辅助栈空间最坏为链表所有节点数

1.3 二叉树中序遍历

思路：遍历左子树，访问根节点，遍历右子树

二叉树递归中序遍历

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

什么是二叉树的中序遍历，简单来说就是“左根右”，展开来说就是对于一棵二叉树，我们优先访问它的左子树，等到左子树全部节点都访问完毕，再访问根节点，最后访问右子树。同时访问子树的时候，顺序也与访问整棵树相同。

从上述对于中序遍历的解释中，我们不难发现它存在递归的子问题，根节点的左右子树访问方式与原本的树相同，可以看成一颗树进行中序遍历，因此可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问左子树的子问题，等到左子树的结果返回后，再访问自己的根节点，然后进入右子树。
1
2
3

具体做法：

• step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
• step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
• step 3：左子树访问完毕再回到根节点访问。
• step 4：最后进入根节点的右子树进行递归。

void BinaryTreePrevOrder(BTNode* root){
	if (root){
		BinaryTreePrevOrder(root->lChild);
		putchar(root->data);
		BinaryTreePrevOrder(root->rChild);
	}
}
1
2
3
4
5
6
7

算法复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，遍历二叉树所有节点
空间复杂度：O(n)，最坏情况下二叉树化为链表，递归栈深度为 n

中序遍历投影特性

直观来看，二叉树的中序遍历就是将节点投影到一条水平的坐标上。

图例展示如下：

非递归中序遍历（辅助栈）

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

与前序遍历类似，我们利用栈来代替递归。如果一棵二叉树，对于每个根节点都优先访问左子树，那结果是什么？从根节点开始不断往左，第一个被访问的肯定是最左边的节点，

while(root != NULL){ //每次找到最左节点
    s.push(root);
    root = root->left;
}
1
2
3
4

然后访问该节点的右子树，最后向上回到父问题。因为每次访问最左的元素不止对一整棵二叉树成立，而是对所有子问题都成立，因此循环的时候自然最开始都是遍历到最左，然后访问，然后再进入右子树，我们可以用栈来实现回归父问题。

具体做法：

• step 1：优先判断树是否为空，空树不遍历。
• step 2：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
• step 3：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
• step 4：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        //当树节点不为空或栈中有节点时
        while(root != NULL || !s.empty()){
            //每次找到最左节点
            while(root != NULL){
                s.push(root);
                root = root->left;
            }
            TreeNode* node = s.top(); //访问该节点
            s.pop();
            res.push_back(node->val);
            root = node->right; //进入右节点
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析：

时间复杂度：O(n)O(n)O(n)，其中nnn为二叉树的节点数，遍历二叉树所有节点
空间复杂度：O(n)O(n)O(n)，辅助栈空间最大为链表所有节点数

1.4 二叉树后序遍历

方法一：递归后序遍历（推荐使用）

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

什么是二叉树的后续遍历，简单来说就是“左右根”，展开来说就是优先访问根节点的左子树的全部节点，然后再访问根节点的右子树的全部节点，最后再访问根节点。对于每棵子树的访问也按照这个逻辑，因此叫做“左右根”的顺序。

从上述后序遍历的解释中我们不难发现，它存在递归的子问题：对每个子树的访问，可以看成对于上一级树的子问题。那我们可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 对于每个子问题，优先进入左子树的子问题，访问完了再进入右子树的子问题，最后回到父问题访问根节点。
1
2
3

具体做法：

• step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
• step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
• step 3：左子树访问完毕再进入根节点的右子树递归访问。
• step 4：最后回到根节点，访问该节点。

class Solution {
public:
    void postorder(vector<int> &res, TreeNode* root){
        //遇到空节点则返回
        if(root == NULL) 
            return;
        //先遍历左子树
        postorder(res, root->left); 
        //再遍历右子树
        postorder(res, root->right); 
        //最后遍历根节点
        res.push_back(root->val); 
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        //递归后序遍历
        postorder(res, root);  
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：非递归后序遍历（扩展思路）知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

既然二叉树的前序遍历和中序遍历都可以使用栈来代替递归，那后序遍历是否也可以呢？答案是可以的，但是会比前二者复杂一点点。

根据后序遍历“左右中”的顺序，那么后序遍历也与中序遍历类似，要先找到每棵子树的最左端节点：

while(root != NULL){
    s.push(root);
    root = root->left; //每次找到最左节点
}
1
2
3
4

然后我们就要访问该节点了嘛？不不不，如果它还有一个右节点呢？根据“左右根”的原则，我还要先访问右子树。我们只能说它是最左端的节点，它左边为空，但是右边不一定，因此这个节点必须被看成是这棵最小的子树的根。要怎么访问根节点呢？

我们都知道从栈中弹出根节点，一定是左节点已经被访问过了，因为左节点是子问题，访问完了才回到父问题，那么我们还必须要确保右边也已经被访问过了。如果右边为空，那肯定不用去了，如果右边不为空，那我们肯定优先进入右边，此时再将根节点加入栈中，等待右边的子树结束。

s.push(node); //该节点再次入栈
root = node->right; //先访问右边
1
2

不过，当右边被访问了，又回到了根，我们的根怎么知道右边被访问了呢？用一个前序指针pre标记一下，每个根节点只对它的右节点需要标记，而每个右节点自己本身就是一个根节点，因此每次访问根节点的时候，我们可以用pre标记为该节点，回到上一个根节点时，检查一下，如果pre确实是它的右子节点，哦那正好，刚刚已经访问过了，我现在可以安心访问这个根了。

//如果该元素的右边没有或是已经访问过
if(node->right == NULL || node->right == pre){
    //访问中间的节点
    res.push_back(node->val);
    //且记录为访问过了
    pre = node;
}
1
2
3
4
5
6
7

具体做法：

step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。
1
2
3
4

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s; 
        TreeNode* pre = NULL; 
        while(root != NULL || !s.empty()){ 
            while(root != NULL){ 
                s.push(root);
                root = root->left; //每次先找到最左边的节点
            }
            
            TreeNode* node = s.top(); //弹出栈顶
            s.pop();
            //如果该元素的右边没有或是已经访问过
            if(node->right == NULL || node->right == pre){ 
                
                res.push_back(node->val); //访问中间的节点
                pre = node; //且记录为访问过了
            }else{
                
                s.push(node); //该节点入栈
                root = node->right;  //先访问右边
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，遍历二叉树所有节点

空间复杂度：O(n)，辅助栈空间最大为链表所有节点数

1.5 二叉树层序遍历

方法一：非递归（推荐使用）知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助：

因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一行节点，并在访问的时候依次把它们的子节点加入队列，那么它们的子节点也是从左到右的次序，且排在本行节点的后面，因此队列中出现的顺序正好也是从左到右，正好符合层次遍历的特点。

具体做法：

• step 1：首先判断二叉树是否为空，空树没有遍历结果。
• step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
• step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
• step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
• step 5：访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if(root == NULL)
            //如果是空，则直接返回空vector
            return res; 
        //队列存储，进行层次遍历
        queue<TreeNode*> q; 
        q.push(root);
        TreeNode* cur;
        while(!q.empty()){
            //记录二叉树的某一行
            vector<int> row;  
            int n = q.size();
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                cur = q.front();
                q.pop();
                row.push_back(cur->val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            //每一层加入输出
            res.push_back(row); 
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

复杂度分析：

时间复杂度：O(n)，其中n为二叉树的节点数，每个节点访问一次
空间复杂度：O(n)，队列的空间为二叉树的一层的节点数，最坏情况二叉树的一层为O(n)级

方法二：层序遍历递归（扩展思路）知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

既然二叉树的前序、中序、后序遍历都可以轻松用递归实现，树型结构本来就是递归喜欢的形式，那我们的层次遍历是不是也可以尝试用递归来试试呢？

按行遍历的关键是每一行的深度对应了它输出在二维数组中的深度，即深度可以与二维数组的下标对应，那我们可以在递归的访问每个节点的时候记录深度：

void traverse(TreeNode root, int depth)
1

进入子节点则深度加 1：

//递归左右时深度记得加1
traverse(root.left, depth + 1);
traverse(root.right, depth + 1);
1
2
3

每个节点值放入二维数组相应行。

res[depth - 1].push_back(root->val);
1

因此可以用递归实现：

终止条件： 遍历到了空节点，就不再继续，返回。
返回值： 将加入的输出数组中的结果往上返回。
本级任务： 处理按照上述思路处理非空节点，并进入该节点的子节点作为子问题。
1
2
3

具体做法：

• step 1：首先判断二叉树是否为空，空树没有遍历结果。
• step 2：使用递归进行层次遍历输出，每次递归记录当前二叉树的深度，每当遍历到一个节点，如果为空直接返回。
• step 3：如果遍历的节点不为空，输出二维数组中一维数组的个数（即代表了输出的行数）小于深度，说明这个节点应该是新的一层，我们在二维数组中增加一个一维数组，然后再加入二叉树元素。
• step 4：如果不是step 3的情况说明这个深度我们已经有了数组，直接根据深度作为下标取出数组，将元素加在最后就可以了。
• step 5：处理完这个节点，再依次递归进入左右节点，同时深度增加。因为我们进入递归的时候是先左后右，那么遍历的时候也是先左后右，正好是层次遍历的顺序。

class Solution {
public:
    void traverse(TreeNode* root, vector<vector<int>>& res, int depth) {
        if(root){
            //新的一层
            if(res.size() < depth)  
                res.push_back(vector<int>{}); 
            //vector从0开始计数因此减1，在节点当前层的vector中插入节点
            res[depth - 1].push_back(root->val);
        }
        else
            return;
        //递归左右时进入下一层
        traverse(root->left, res, depth + 1); 
        traverse(root->right, res, depth + 1);
    }
    
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if(root == NULL)
            //如果是空，则直接返回空vector
            return res; 
        traverse(root, res, 1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

复杂度分析：

时间复杂度：O(n)，其中n为二叉树的节点数，每个节点访问一次
空间复杂度：O(n)，最坏二叉树退化为链表，递归栈的最大深度为n