树的基础理论

树的定义

树是n（n>=0）个结点的集合。
n==0时为空树。
n!=0时，结点集合符合如下关系：

  • 所有结点的集合中只有一个节点没有前驱结点，称为根结点。
  • 除根结点外，其他结点有且只有一个前驱结点，对于没有后继结点的结点称为叶子结点。
  • 结点集合中有多个终端结点。

树数据结构其实是图数据结构的一种。图的一些算法同样可用于树。

树的属性

结点关系

结点的度

该结点的后继节点的总数

分支结点

度>0的结点称为分支结点或非终端结点。（单分支结点、双分支结点）

叶子结点

度=0的结点称为叶子结点。

孩子结点

一个结点的后继结点为该结点的孩子结点。

双亲结点

一个结点是其后继结点的双亲结点。

子孙结点

一个结点的子树中除该结点外的所有结点成为该结点的子孙结点。

祖先结点

从树的根结点到某结点路径上通过的所有结点称为该结点的祖先结点。

兄弟结点

具有同一双亲的结点互相称为兄弟结点。

结点层次

树的一种层次结构。根结点为第一层，其孩子结点为第二层，依此类推。

树的度

所有结点的度的最大值称之为树的度

树的高度/树的深度

树种结点的最大层次。

树的性质

二叉树基础理论

二叉树的种类

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树

二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉搜索树（AVL）

AVL（Adelson-Velsky and Landis）树
具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式

顺序存储

顺序存储的内存是连续的。使用数组记录。可以通过计算出下一元素的下标进行访问。
假设当前的节点下标为i，则其左子节点下标为i2+1，右子节点下标为i2+2。

链式存储

链式存储的内存是离散的。我们需要定义一个结构体,然后使用指针连接各个不同的存储地址。

1
2
3
4
5
6
7
8
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) {}
};

二叉树的遍历

二叉树的深度优先遍历

前序遍历

遍历顺序：中->左->右
力扣——二叉树的前序遍历

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
void traversal(TreeNode* node,vector<int>& record){
    if(node == nullptr) return;
    //只是语句顺序不同
    record.push_back(node->val);
    traversal(node->left,record);
    traversal(node->right,record);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    traversal(root,res);
    return res;
}
  • 循环迭代法

使用栈模拟递归的行为。（因为递归的运行底层就是出栈入栈的过程）

注：
相关动画可以看这里：
力扣——代码随想录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> record;
    vector<int> res;
    //根结点入栈
    if(!root) return res;
    record.push(root);
    while(!record.empty()){
        //中
        TreeNode* node = record.top();
        record.pop();
        res.push_back(node->val);
        //右 （右侧结点先入栈，是因为出栈顺序应当为左结点、右结点）
        if(node->right) record.push(node->right);
        //左
        if(node->left) record.push(node->left);
    }
    return res;
}

中序遍历

遍历顺序：左->中->右
力扣——二叉树的中序遍历

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
void traversal(TreeNode* node,vector<int>& record){
    if(node == nullptr) return;
    //只是语句顺序不同
    traversal(node->left,record);
    record.push_back(node->val);
    traversal(node->right,record);
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    traversal(root,res);
    return res;
}
  • 循环迭代法
    与前序遍历的迭代法不同。
    首先使用一个指针迭代到树的左侧底部，记录经过的所有结点。
    然后依次出栈，如果出栈结点的右结点不为空还需要遍历右子树的结点。
    如此往复，直到栈空或指针为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> record;
    vector<int> res;
    TreeNode* cur = root;
    while(cur || !record.empty()){
        if(cur){
            record.push(cur);
            cur = cur->left;
        }
        else{
            cur = record.top();
            record.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
    }
    return res;
}

后序遍历

遍历顺序：左->右->中
力扣——二叉树的后序遍历

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
void traversal(TreeNode* node,vector<int>& record){
    if(node == nullptr) return;
    //只是语句顺序不同
    traversal(node->left,record);
    traversal(node->right,record);
    record.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    traversal(root,res);
    return res;
}
  • 循环迭代法
    在前序遍历的基础上做了一点修改。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;
    if(root == nullptr) return res;
    st.push(root);
    while(!st.empty()){
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);
        //需要左结点先入栈
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }
    //将结果反转
    reverse(res.begin(),res.end());
    return res;
}

二叉树的统一迭代遍历（深度优先搜索）

深度优先搜索使用栈（stack）记录临时节点。
要点：在中节点（两个子节点的双亲节点）入栈后再次插入一个nullptr（空节点）作为标记。
力扣——二叉树的统一迭代遍历
这里以中序遍历为例：

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
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    if(root != nullptr){
        st.push(root);
    }

    while(!st.empty()){
        TreeNode* node = st.top();
        if(node){
            st.pop(); //取出栈顶节点
            if(node->right) st.push(node->right); //右子节点先入栈（因为是栈，需要考虑到出栈顺序）
            st.push(node); //中节点入栈
            st.push(nullptr); //中节点入栈后，插入空节点作为标记
            if(node->left) st.push(node->left); //左子节点入栈
        }
        else{
            //如果栈顶节点为空...
            st.pop(); //去掉空节点
            node = st.top(); //拿到空节点后的中间节点
            st.pop();
            res.push_back(node->val); //将数据插入结果列表
        }
    } 
    return res;
}

二叉树的层序遍历（广度优先搜索）

广度优先搜索使用队列（queue）记录临时节点。
力扣——二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int>> res;
    if(root) que.push(root);
    while(!que.empty()){
        int size = que.size();
        vector<int> temp;
        for(int i=0;i<size;i++){
            TreeNode* node = que.front();
            que.pop();
            temp.push_back(node->val);
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
        res.push_back(temp);
    }
    return res;
}

解题技巧

关于二叉树（树）算法题目的基本解题思路

通常解决一道树相关的题目不妨从下面几个角度考虑

  • 树的遍历顺序
    使用递归法还是迭代法？如果使用递归法又应当使用先、中、后哪种顺序递归？
  • 如果使用递归法则需要考虑“递归三部曲”
    即递归函数的参数、递归终止条件、单层处理逻辑。
  • 如果使用迭代法则需要考虑使用队列还是栈存储临时节点

关于二叉树的增删查改

删除

以删除一个二叉搜索树中的节点为例：
可能有下面几种情况

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
    找到删除的节点
  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

AVL树的删除

AVL树需要在删除后树的中序遍历顺序不变。因此在上述删除的过程后还可能进行一系列调整，使得树维持平衡，即树的旋转。

AVL树的平衡因子

AVL树（左子树高度-右子树高度）的绝对值<=1，**（左子树高度-右子树高度）**为平衡因子。
当平衡因子<-1或>1时则为失衡。

AVL树的旋转

  • 左旋 向左旋转，冲突左孩变右孩
  • 右旋 向右旋转，冲突右孩变左孩

AVL树的失衡类型，分别有LL、RR、LR、RL四种类型。

  • LL: 失衡节点的平衡因子=2，失衡节点的左孩子的平衡因子=1
  • RR: 失衡节点的平衡因子=-2，失衡节点的左孩子的平衡因子=-1
  • LR: 失衡节点的平衡因子=2，失衡节点的左孩子的平衡因子=-1
  • RL: 失衡节点的平衡因子=-2，失衡节点的左孩子的平衡因子=1

不同类型的旋转方式分别为：

  • LL 右旋
  • RR 左旋
  • LR 先左旋左孩子，再右旋
  • RL 先右旋右孩子，再左旋

其他注意的地方

  • 终止条件涉及父节点
    如果终止条件涉及到父节点，比如返回树中所有的左叶子节点，那么就需要借助父节点才能找到左叶子节点。因此终止条件不再是遇到叶子节点后返回。
  • 重复使用的不变变量可以声明为类内变量
  • 注意递归中的回溯
    递归一定伴随着回溯，只是在大多数二叉树相关题目中的隐藏了。
    这是个使用了回溯的二叉树问题：力扣——二叉树的所有路径
    简而言之，回溯就是“在危险边缘来回试探”，当触碰到终止条件则回退一步，否则一直走下去。