【数据结构】二叉树：性质、遍历(DFS、BFS)、斜二叉树、满二叉树、完全二叉树、二叉搜索树(BST)、平衡二叉树(AVL) 干货总结

二叉树

二叉树是应用最为广泛的数据结构之一，它是一个有穷的结点集合。直观表示如图所示：

二叉树有五种基本形式，分别为空树、只有一个结点、只有左子树、只有右子树、左右子树都有。如下图所示：

在二叉树这种数据结构的描述中，有几个常用的概念：

1.度(Degree)：结点子树个数；

2.叶结点：度为0的结点；

3.父结点：有子树的结点是其子树根结点的父结点；

4.子结点：父结点的孩子结点；

5.路径及路径长度：路径为从某结点到另一结点走过的边，路径长度为边的权重和；

6.结点的层次(Level)：树根在第一层，其它依次加1；

7.树的深度(Depth)：结点的最大层次。

性质

(1)第i层的最大结点数：2^(i-1)；

(2)深度为h的二叉树最大结点数：2^k-1；

(3)对任何非空二叉树，叶结点数=度为2的结点数+1.

遍历

深度优化搜索(DFS)

可理解为对于一个父结点，穷尽它的子树，直到叶结点。对于二叉树来说，共有三种DFS方法，分别是前序、中序、后序。如下表所示：

方法	过程
前序遍历	先访问根结点，再访问左、右子树
中序遍历	先访问左子树，再访问根结点，后访问右子树
后序遍历	先访问左子树，再访问右子树，后访问根结点

下面通过代码来说明其原理，以前序为例。

(1)递归法：

typedef struct TreeNode* BinTree;//定义BinTree为结点的指针类型
struct TreeNode{//树的每个结点的形式
    ElemType data;
    BinTree left;
    BinTree right;
};
void PreOrderTravelsal(BinTree bt){
    if(bt){
    cout<<bt->data<<" ";//输出当前结点的值
    PreOrderTravelsal(bt->left);//将bt->left作为根结点递归调用
    PreOrderTravelsal(bt->right);//将bt->right作为根结点递归调用
    }
}

(2)堆栈法：

typedef struct TreeNode* BinTree;//定义BinTree为结点的指针类型
struct TreeNode{//树的每个结点的形式
    ElemType data;
    BinTree left;
    BinTree right;
};
void PreOrderTravelsal(BinTree bt){
    stack<TreeNode>stk;
    while(bt||!stk.empty()){
        while(bt){
            stk.push(bt);//入栈
            cout<<bt->data<<" ";//输出当前结点的值
            bt=bt->left;
        }
        if(!stk.empty()){
            bt=stk.top();//记录出栈元素
            stk.pop();//出栈
            bt=bt->right;//转向右子树
        }
    }
}

大家可以思考一下，如何去写中序和后序遍历呢？
其实三种遍历方法的差异无非就是访问元素的时机不同，只需将cout<<bt->data<<” “;语句调整位置即可实现三种DFS方法。

广度优化搜索(BFS)

与DFS借助堆栈实现不同，广度优化搜索BFS(层序遍历)需要在访问父结点时，同时装入它的两个子结点，因此借助队列来实现。其代码实现为：

typedef struct TreeNode* BinTree;//定义BinTree为结点的指针类型
struct TreeNode{//树的每个结点的形式
    ElemType data;
    BinTree left;
    BinTree right;
};
void PreOrderTravelsal(BinTree bt){
    queue<TreeNode>Q;
    if(!bt)return;
    q.push(bt);
    while(!q.empty()){
        bt=q.front();
        cout<<bt->data<<" ";
        q.pop();
        if(bt->left) q.push(bt->left);
        if(bt->right) q.push(bt->right);    
    }
}    

特殊形式

二叉树有几种特殊的形式：斜二叉树、满二叉树、完全二叉树、二叉搜索树(BST)、平衡二叉树(AVL)

斜二叉树

如图所示，在斜二叉树中，所有结点都倒向同一边，相当于一个链表。

满二叉树

满二叉树，又称完美二叉树。完美一词，已足以概括这种二叉树的特点，即每个父结点对应的两个子结点都不为空，直至叶结点为止。

完美二叉树的深度h与结点数n有如下数学关系式：
h = l o g 2 ( n + 1 ) . h = log_2 (n+1). h=log2​(n+1).

完全二叉树

完全二叉树相比完美二叉树来说，虽不如其“完美”，但是完全二叉树除叶结点所在层的部分都是与完美二叉树无异的，而叶结点所在层的靠左部分也与完美二叉树无异。

这么说还有些抽象，举个很简单的例子。比如一棵深度为3的完美二叉树各结点值为{1,2,3,4,5,6,7}，其中第一层为{1}，第二层为{2,3}，第三层为{4,5,6,7}。那么完全二叉树的组成则为，第一层、第二层与完美二叉树完全一致，第三层可能的四种情况为{4}，{4,5}，{4,5,6}，{4,5,6,7}。

小结：
关于完美二叉树与完全二叉树的异同，如图所示

1.完美二叉树和完全二叉树用顺序存储的方式不会造成任何的空间浪费。
Q：完全二叉树不也有可能会有空元素吗？
A：完全二叉树在叶结点所在层只存储不为空的元素即可。

2.完美二叉树和完全二叉树从上到下，从左到右各结点编号后【对应的编号】完全一致。

3.完美二叉树和完全二叉树的一些数学性质（i表示当前结点编号，n表示结点个数）：

(1)非根结点的父结点序号为i/2。
e.2号结点的序号为2，则其父结点序号为2/2=1；7号结点的序号为7，则其父结点基于int类型的序号为7/2=3.

(2)结点的左孩子序号为2i，右孩子的序号为2i+1.
针对完全二叉树来说，若2i≤n，则该父结点没有左孩子（当然更没有右孩子）；若2i+1小于等于n，则该父结点没有右孩子。

二叉搜索树 BST

1.引入：

在查找问题中，我们知道查找可以分为静态查找和动态查找。

静态查找包括顺序查找、二分查找等方法，其中顺序查找的时间复杂度一般为O(n)，空间复杂度一般为O(n)；二分查找法的时间复杂度一般为O(log n)，空间复杂度为一般为O(n)。若在有数据频繁插入或删除的情况下，显然静态查找并不适合，会显著提高时间复杂度。因此引入动态查找。

动态查找也有诸多方法，如二叉搜索树、哈希表等。那么二叉搜索树到底是如何组织数据的呢？

2.性质：
二叉搜索树(BST)，又叫二叉排序树、二叉查找树，其性质概括为以下三点：
(1)左子树所有结点值均小于根结点值；
(2)右子树所有结点值均大于根结点值；
(3)左、右子树均为二叉搜索树。

3.二叉搜索树中的中序遍历是一个升序序列，这个结论在力扣783——二叉搜索树结点最小距离中会用到。关于这道题的解法，我的博客中有写，小伙伴们如果没有思路的话可以去看一下。

4.二叉搜索树的查找效率取决于高度，因为根据性质可知每层只需查找1次，所以O(log n)。

平衡二叉树 AVL

二叉搜索树也有自己没有解决的问题，比如形成了斜二叉树的形态，此时既使得时间复杂度达到了没有必要的O(log n)，又浪费了大量的空间。因此有了平衡二叉树(AVL)。

平衡二叉树在二叉搜索树的要求之外，增加了一条左右子树的高度差严格≤1，这使得整棵二叉树显得特别平衡。

关于AVL插入后的调整，遵循的原则是：
(1)首先把麻烦结点（插入导致平衡破坏的结点）的父结点提为根结点；
(2)根据BST所要求的结点关系调整结点位置。

由此，产生了四种调整方式，分别为RR、LL、LR、RL旋转。目前我做的题目中，涉及AVL的调整的题目较少，因此此处不展开讨论，感兴趣的小伙伴欢迎私信交流。