二叉树

基本概念

定义

二叉树是一种特殊的树形结构，每个结点至多只有两颗子树（所有结点度不大于2）

二叉树的子树有左右之分，次序不能颠倒（因此为有序树）

由于二叉树的孩子也是二叉树，故二叉树也是递归定义的结构
二叉树的特殊分类
- 满二叉树
  - 概念
    
    在一颗二叉树中，所有非叶子结点都存在左右孩子，所有叶子都在同一层
  - 性质
    
    如果将满二叉树，按照层序遍历的过程编号，那么
    
    结点 \(i\) 的左孩子编号：为 \(2i\)
    
    结点 \(i\) 的右孩子编号：为 \(2i + 1\)
    
    结点 \(i\) 的双亲编号：\(i/2\)
    
    注：若以 0 开始编号，则
    
    结点 \(i\) 的左孩子编号：为 \(2(i + 1) - 1=2i+1\)
    
    结点 \(i\) 的右孩子编号：为 \(2(i + 1) + 1 - 1 = 2i + 2\)
    
    结点 \(i\) 的双亲编号：\((i + 1)/2-1\)
    
    利用这个性质，可以用来帮我们存储满二叉树
- 完全二叉树
  - 概念
    
    就是在满叉树的基础之上，从右往前依次删掉一些结点

顺序存储实现

概念

在《树》的章节中，学过了树的vector数组实现、链式前向星实现。这里同样可以以这些存储方法来实现二叉树

由于二叉树的结构特性，除了以vector数组、链式前向星这两个实现方法（标记左孩子、右孩子），还能用符合二叉树特性的存储方式：顺序存储、链式存储
顺序存储

对于满二叉树，根据满二叉树的性质，计算父子结点的编号

若不是满二叉树、完全二叉树，要把缺失的部分空着，然后再去编号（缺点是空间利用率不高）

这种存储方式相对简单清晰，在后续堆、线段树的课程中，我们再继续讨论

链式存储实现

链式存储

这里依旧只讲解静态实现，也就是用数组模拟（动态实现这里不做要求，在企业中才需要动态存储）

竞赛中给定的树结构一般都是有编号的，二叉树也是如此。因此，我们可以创建两个数组l[N]、r[N]，分别存储i号结点的左右孩子的编号，这样就可以通过数组下标实现链式访问

代码实现

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int child_left[N], child_right[N];

void addChild(const int& root, const int& left_child, const int& right_child) {
    child_left[root] = left_child;
    child_right[root] = right_child;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int l = 0, f = 0;
        cin >> l >> f;
        addChild(i, l, f);
    }

    return 0;
}

DFS

概念

与树不同的是，二叉树的DFS遍历可以分为：中序、前序、后序
- 前序：根、左、右
- 中序：左、根、右
- 后序：左、右、根

代码实现

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int child_left[N], child_right[N];

void addChild(const int& root, const int& left_child, const int& right_child) {
    child_left[root] = left_child;
    child_right[root] = right_child;
}

// 前序遍历
void dfs_1(const int& root) {
    cout << root << " ";
    if (child_left[root]) {
        dfs_1(child_left[root]);
    }
    if (child_right[root]) {
        dfs_1(child_right[root]);
    }
}

// 中序遍历
void dfs_2(const int& root) {
    if (child_left[root]) {
        dfs_2(child_left[root]);
    }
    cout << root << " ";
    if (child_right[root]) {
        dfs_2(child_right[root]);
    }
}

// 后序遍历
void dfs_3(const int& root) {
    if (child_left[root]) {
        dfs_3(child_left[root]);
    }
    if (child_right[root]) {
        dfs_3(child_right[root]);
    }
    cout << root << " ";
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int l = 0, f = 0;
        cin >> l >> f;
        addChild(i, l, f);
    }

    dfs_1(1); // 先序遍历
    cout << endl;
    dfs_2(1); // 中序遍历
    cout << endl;
    dfs_3(1); // 后序遍历
    cout << endl;

    return 0;
}

测试用例：

BFS

代码实现

#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int child_left[N], child_right[N];

void addChild(const int& root, const int& left_child, const int& right_child) {
    child_left[root] = left_child;
    child_right[root] = right_child;
}

void bfs(const int& root) {
    queue<int> q;

    // 进入循环
    q.push(root);
    while (!q.empty()) {
        cout << q.front() << " ";
        if (child_left[q.front()]) {
            q.push(child_left[q.front()]);
        }
        if (child_right[q.front()]) {
            q.push(child_right[q.front()]);
        }
        q.pop();
    }
    cout << endl;
}

int main() {
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int l = 0, f = 0;
        cin >> l >> f;
        addChild(i, l, f);
    }

    bfs(1);

    return 0;
}