二叉树入门指南

发表于 2022-03-09 更新于 2024-04-26 分类于 C++ ，算法笔记，二叉树

二叉树的种类

满二叉树

满二叉树的定义是：如果一颗二叉树只有度为0的节点和度为2的节点，且度为0的节点在同一层上，则该二叉树是满二叉树，如下图：

满二叉树的深度为k，则节点共有 $ 2^{k} - 1 $个（这里使用等比数列相加即可得出）。

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

优先级队列其实是一个堆，堆就是一个完全二叉树，而且保证了父子节点的顺序关系。

二叉搜索树

二叉搜索树是节点带有数值的一棵树，并且要满足以下关系：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
它的左、右子树也分别为二叉排序树。

平衡二叉搜索树

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

最后一棵树不是平衡二叉搜索树，因为根节点的左右子树的高度差的绝对值超过了1（此时左边为6，右边无子树为0）。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，这两者的底层实现是哈希表。

二叉树的定义

在面试的时候，因为大部分情况是没有IDE和代码提示的，需要自己定义二叉树，下面是常用的定义二叉树的方法：

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(NULL), right(NULL) {}
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
}

二叉树的遍历方式

说到二叉树，那么常见的考察方式就是其遍历方式，大体上可以概括为两种：
1. 深度优先遍历
$\qquad\bullet$前序遍历（递归，迭代）
$\qquad\bullet$中序遍历（递归，迭代）
$\qquad\bullet$后序遍历（递归，迭代）
2. 广度优先遍历
$\qquad\bullet$层次遍历（迭代）

在深度优先遍历中，前、中、后指的是根节点所在的位置。

深度优先遍历（迭代法）

下面介绍一下使用递归方法进行深度优先遍历，这里假设我们使用vector来保存遍历过程中的节点值。这里提供的是递归方法的思路，之后只需要按照这个思路稍微修改代码满足需要即可。

1. 前序遍历

//中-左-右
class Solution{
public:
    void traversal(TreeNode* cur， vector<int>& vec){
        if(cur == NULL)return;
        vec.push_back(cr->val); //中
        traversal(cur->left); //左
        traversal(cur->right); //右
    }

    vector<int> preorderTraversal(TreeNode* root){
        vector<int> result;
        if(root == NULL)return result;
        traversal(root, result);
        return result;
    }
}

同理，中序遍历和后序遍历只需要修改递归代码中的顺序即可，思路都是一样的。

2. 中序遍历

//左-中-右
class Solution{
public:
    void traversal(TreeNode* cur， vector<int>& vec){
        if(cur == NULL)return;
        traversal(cur->left); //左
        vec.push_back(cr->val); //中
        traversal(cur->right); //右
    }

    vector<int> preorderTraversal(TreeNode* root){
        vector<int> result;
        if(root == NULL)return result;
        traversal(root, result);
        return result;
    }
}

3. 后序遍历

//左-右-中
class Solution{
public:
    void traversal(TreeNode* cur， vector<int>& vec){
        if(cur == NULL)return;
        traversal(cur->left); //左
        traversal(cur->right); //右
        vec.push_back(cr->val); //中
    }

    vector<int> preorderTraversal(TreeNode* root){
        vector<int> result;
        if(root == NULL)return result;
        traversal(root, result);
        return result;
    }
}

下一篇博客将总结使用迭代方法实现深度优先遍历和广度优先遍历（即层次遍历）。