二叉树

作者：张帅

概念

二叉树是一种非线性数据结构，由结点组成，每个结点最多有两个子结点（称为左子结点和右子结点）。

    根结点 
    /      \
左子树     右子树

关于二叉树的术语：

术语	说明
根结点	树的顶层结点，没有父结点。
叶子结点	没有子结点的结点（左右子结点均为空）。
度	一个结点的子结点数量（二叉树中结点的度 ≤ 2）。
深度/高度	深度：根结点到当前结点的层数；高度：当前结点到叶子结点的最长路径。
子树	以某个结点为根的子树（左子树/右子树）。

二叉树的类型

1. 普通二叉树

每个结点最多有两个子结点，无其他约束。

2. 满二叉树

所有非叶子结点都有两个子结点，且所有叶子结点在同一层。

性质：若高度为 h，则结点总数 = 2^h - 1。

          A

        /   \

       B     C

      / \   / \

     D   E F   G

3. 完全二叉树

除最后一层外，其他层都是满的，且最后一层结点靠左对齐。

          A

        /   \

       B     C

      / \   /

     D   E F

深度优先搜索和广度优先搜索

在了解二叉树的概念以后，我们来了解一下两种基于二叉树的常见搜索方式：dfs和bfs。

深度优先搜索（dfs）

概念

从根节点出发，尽可能深地探索一条路径，直到无法继续后再回溯。

举例

     A

    /   \

   B     C

  / \   / \

 D   E F   G

深度优先搜索的顺序:A-B-D-B-E-B-A-C-F-C-G

如果跳过搜索过的编号，顺序:A-B-D-E-C-F-G

代码实现

vector<int> edge[N]; 
int visited[N];//每个节点只访问一次，因此visited记录节点是否被访问
void dfs(int x)
{
    visited[x] = 1; //dfs中只需要开头写一个v[x]=1 后面for循环遍历路径不用v[x]=1
    for (int i = 0; i < edge[x].size(); i ++)
    {
        int next_node = edge[x][i];
        if (visted[next_node]) continue;
        dfs(next_node);
}

广度优先搜索（bfs）

概念

从根节点出发，按层级逐层访问所有邻居节点。

举例

     A

    /   \

   B     C

  / \   / \

 D   E F   G

广度优先搜索的顺序是A-B-C-D-E-F-G

代码实现

void bfs()
{
    queue<int> q; // 定义队列
    q.push(1);  // 加入起点
    visited[1] = 1;   // 标记起点
    while (q.size() > 0)
    {
        int x = q.front(); q.pop();
        // for (int i = 0; i < edge[x].size(); i ++) next_node = edge[x][i];
        for (auto next_node: edge[x])
        {
            if (visited[next_node]) continue; // 是否被访问过
            visited[next_node] = 1;
            q.push(next_node); // 将没访问的节点加入队列
        }
    }
}