二叉树的种类

从结构上来说，二叉树主要分为完全二叉树和非完全二叉树，其中以完全二叉树的应用最为广泛。

满二叉树

满二叉树是指除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。若满二叉树的高度（深度）为K，则它的结点总数一定是$2^{k}-1$，这个原理也可以用于证明一棵二叉树是否是满二叉树。国际上的定义为：若一棵二叉树的结点要么是叶子结点，要么有两个子结点，那么这样的树就是满二叉树。如下图所示可看出国内对满二叉树的定义和国际版本的不同，在国际版本的定义中，霍夫曼树仍然是一个满二叉树，但是这却不符合国内的定义。

graph TD
    %% 第一个子图：国内定义的满二叉树
    subgraph 国内定义的满二叉树
        A((1))
        A --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
        C --> F((6))
        C --> G((7))
    end
    %% 第二个子图：国际标准的满二叉树
    subgraph 国际标准的满二叉树
        A1((1))
        A1 --> B1((2))
        A1 --> C1((3))
        C1 --> F1((4))
        C1 --> G1((5))
        G1 --> H1((6))
        G1 --> I1((7))
    end

完全二叉树

完全二叉树（Complete Binary Tree）是指深度为k、有n个结点的二叉树，其结点编号与相同深度的满二叉树对应位置一致，是效率极高的一种数据结构。满二叉树每一层的结点数达到最大值时即为完全二叉树的特殊形态。完全二叉树的叶子结点仅出现在最下层和次下层，且最下层叶子结点连续出现在最下层左部。具有n个结点的完全二叉树的深度为${\lfloor\log_{2}n\rfloor+1}$（其中$\lfloor\rfloor$表示向下取整）

graph TD
    A((1))
    A --> B((2))
    A --> C((3))
    
    B --> D((4))
    B --> E((5))
    C --> F((6))
    C --> G((7))
    
    D --> H((8))
    D --> I((9))

搜索二叉树

搜索二叉树是一种在递归结构上满足结点值从小到大的二叉树。即对于搜索二叉树的任意一个子树，其节点值均满足左子树的所有结点小于当前结点，而右子树的所有节点大于当前结点。搜索二叉树的平均搜索时间复杂度和平均插入删除时间复杂度都是O(logn)。但是搜索二叉树容易在构造过程中出现右子树过长的情况变成链表，此时搜索和插入删除的时间复杂度就会达到O(n)，因此需要重新调整搜索二叉树的结构，使其左右子树高度"平衡"。

graph TD
    subgraph 平衡的搜索二叉树
        A((4))
        A --> B((6))
        A --> C((2))
        B --> D((7))
        B --> E((5))
        C --> F((3))
        C --> G((1))
    end

    subgraph 不平衡的搜索二叉树
        A1((1))
        A1 --> B1((2))
        B1 --> C1((3))
        C1 --> D1((4))
        D1 --> F1((5))
    end

平衡搜索二叉树

平衡二叉搜索树又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是⼀棵空树或它的左右两 个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。在C++中，map、set、multiset、multimap的底层数据结构是红黑树（一种特殊的自平衡二叉树<并非严格平衡>）、而unordered系列的容器底层数据结构是哈希表。基于红黑树构造的STL容器是有序的且操作效率稳定，而基于哈希表构造的STL容器是无序的，并且使用拉链法解决哈希冲突，其访问效率更高。

二叉树的存储方式

二叉树的存储方式分为链式存储和顺序存储两种，链式存储方式通过递归或迭代地访问当前结点的left和right指针对二叉树进行遍历。而顺序存储往往无法对二叉树的结构进行直观的判断，在操作时需要提前知道二叉树的结点关系，常用于存储完全二叉树（其实也不太常用）。目前最常用的二叉树存储方式还是链式存储，这种方式虽然不能做到对结点的随机存取，但是可以直观地显示当前结点的左右子树，并且方便结点的添加和删除。

二叉树的遍历

对于使用顺序存储方式存储的二叉树，若父结点的下标是i，那么其左孩子的下标就是2i+1，右孩子的下标就是2i+2。对于链式存储的二叉树，其遍历方式主要分为深度优先遍历（DFS）和广度优先遍历（BFS）两种。其中，深度优先遍历又可分为前序遍历（根左右）、中序遍历（左根右）和后序遍历（左右根），这三种遍历方式常使用递归或迭代的方式结合栈来实现。而广度优先遍历又称层序遍历，常使用迭代的方式结合队列实现。

二叉树定义

一般情况下不会使用顺序存储方式定义二叉树，此处只给出C++版本的链式存储方式的二叉树定义：

1
2
3
4
5
6
7

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0), left(nullptr), right(nullptr);
    TreeNode(int num):val(num), left(nullptr), right(nullptr);
};