【C++】二叉树

二叉树的概念

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。二叉树可以为空树，通常子树被称为”左子树“和”右子树“
比如下图就是一棵二叉树

二叉树的每个节点最多有两棵子树（不存在度大于2的节点），二叉树的子树有左右之分，次序不能颠倒
二叉树的第i层，最多有 2 i − 1 2^{i-1} 2i−1个结点
深度为k的二叉树，最多有 2 k − 1 2^k-1 2k−1个结点
对于任何一颗二叉树，如果其叶结点数为 n 0 n0 n0，度为2的节点数为 n 2 n2 n2，则 n 0 = n 2 + 1 n0=n2+1 n0=n2+1
对于最后一个结论可以这么理解，当我们给某个节点新增一个子节点时，如果原节点度数为0则原节点为叶节点，添加后原节点度数为1，新节点为叶节点，所以 n 0 n0 n0和 n 2 n2 n2都不变
如果原节点度数为1，添加后原节点度数为2， n 2 n2 n2会增加1，新增的节点为叶节点，所以 n 0 n0 n0也会增加1，该等式仍然成立

特殊的二叉树满二叉树

一棵深度为k，且有 2 k − 1 2^k-1 2k−1个结点的二叉树，成为满二叉树。满二叉树每一层的结点都是满的
如下图

完全二叉树

在一棵二叉树中，除了最后一层外，其余层都是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度是 l o g ( n + 1 ) log(n+1) log(n+1)。深度为k的完全二叉树，至少有 2 k − 1 2^{k-1} 2k−1个结点，最多有 2 k − 1 2^k-1 2k−1个结点
如下图

满二叉树也是完全二叉树的一种

排序二叉树

排序二叉树(Binary Search Tree,BST)，又称二叉排序树，二叉查找树，具有下列的特质

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

排序二叉树也可以是空树
一般情况下排序二叉树所有结点的值不同，如果需要考虑重复的值，可以另加一个数组 c n t cnt cnt记录BST每个结点的值的个数

二叉树的存储

和一般的树不同，二叉树的子结点分为左儿子和右儿子，左儿子和右儿子均可能为空
我们用一个数组son来存储一棵二叉树，son[u][0]表示u结点的左儿子，son[u][1]表示u结点的右儿子，值为0表示空

如上图，存储的代码为

root = 7;
son[7][0] = 1;
son[7][1] = 6;
son[1][1] = 4;
son[4][0] = 3;
son[4][1] = 2;
son[6][0] = 5;

二叉树的遍历

在二叉树中，因为左右孩子不同，所以很少进行深度优先搜索和广度优先搜索，一般进行几种特殊的遍历：先序遍历、中序遍历、后序遍历和层次遍历

先序遍历

在对二叉树遍历时，先访问当前子树的根节点，再依次访问左子树和右子树。
如上图先序遍历为7 1 4 3 2 6 5

中序遍历

在对二叉树进行遍历时，先访问当前子树的左子树，再访问子树的个节点，最后访问当前子树的右子树
如上图中序遍历为1 3 4 2 7 5 6

后序遍历

在对二叉树进行遍历时，先依次访问当前子树的左右子树，最后访问当前子树的根结点
如上图后序遍历为3 2 4 1 5 6 7

层次遍历

在对二叉树进行遍历时，按从左到右依次遍历从上到下每一层的结点。层次遍历类似于广度优先搜索，但是对于同一层的结点，顺序必须为从左到右，可以借助队列实现
如上图的层次遍历为7 1 6 4 5 3 2

特殊地，对于排序二叉树，它的中序遍历结果为这些数的排序结果

二叉树的四种遍历的代码

#include 
#include 
#include 
using namespace std;
const int N = 1005;
vector v1, v2, v3, v4;
int son[N][2],root;
void build() {
    root = 7;
    son[7][0] = 1;
    son[7][1] = 6;
    son[1][1] = 4;
    son[4][0] = 3;
    son[4][1] = 2;
    son[6][0] = 5;
}
void print() {
    cout << "preorder:";
    for (int i = 0; i < v1.size(); i++) {
        cout << v1[i] << " ";
    }
    cout << endl;
    cout << "inorder:";
    for (int i = 0; i < v2.size(); i++) {
        cout << v2[i] << " ";
    }
    cout << endl;
    cout << "postorder:";
    for (int i = 0; i < v3.size(); i++) {
        cout << v3[i] << " ";
    }
    cout << endl;
    cout << "levelorder:";
    for (int i = 0; i < v4.size(); i++) {
        cout << v4[i] << " ";
    }
    cout << endl;
}
void preorder(int u){
    if(u==0)
        return;
    v1.push_back(u);
    preorder(son[u][0]);
    preorder(son[u][1]);
}
void inorder(int u){
    if(u==0)
        return;
    inorder(son[u][0]);
    v2.push_back(u);
    inorder(son[u][1]);
}
void postorder(int u){
    if(u==0)
        return;
    postorder(son[u][0]);
    postorder(son[u][1]);
    v3.push_back(u);
}
void levelorder(){
    queue q;
    if(root!=0)
        q.push(root);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        v4.push_back(u);
        if(son[u][0]!=0)
            q.push(son[u][0]);
        if(son[u][1]!=0)
            q.push(son[u][1]);
    }
}
int main() {
    build();
    preorder(root);
    inorder(root);
    postorder(root);
    levelorder();
    print();
    return 0;
}

【C++】二叉树

C/C++/C#相关栏目本月热门文章