Skip to content

2021-03-17

定义

树有多种等价的定义方式:

  • 连通且无环的无向图;
  • n 个节点和 n1 条边的无向图;
  • 任意两个顶点间只有一条路径的无向图。

图论中的树看起来更像现实中倒悬的树:

树的节点存在「父子关系」:

  • 有连边的两个节点中,上节点为下节点的父节点。节点 2 是节点 5 的父节点;
  • 有连边的两个节点中,下节点为上节点的子节点,节点 5 是节点 2 的子节点;
  • 没有父节点的节点为根节点,如节点 1
  • 没有子节点的节点为叶节点,如节点 5,6,3,8,9

有根树和无根树

有根树必须明确根节点,而无根树的任意节点都可以是根节点。下面的左图和右图是同一棵无根树:

子树

将节点 i 和其父节点断开,分裂出的以 i 为根的新树,称作节点 i 的子树。如下图,红色部分为节点 3 的子树。

层和深度

定义根节点在第 1 层,子节点层数 = 父节点层数 + 1

树的深度 = 总层数。上图中树的深度为 4。树中各个节点的深度为节点所在的层数。

二叉树

任意节点的子节点数量 2 的树是二叉树:

满二叉树

深度为 k 的二叉树最多有 2k1 个节点。节点最多的那棵树是满二叉树:

满二叉树除最后一层外,其它层任意节点都有 2 个子节点。

完全二叉树

将满二叉树最后一层右边连续的若干节点删除,得到完全二叉树:

满二叉树是一类特殊的二叉树。

森林

多棵树组成的图为森林:

二叉树的遍历

对于二叉树,可以使用 深度优先搜索 DFS 遍历所有节点。二叉树定义了 3 种遍历方式,遍历顺序各不同。

  1. 访问根节点 u
  2. 递归遍历 u 的左子树;
  3. 递归遍历 u 的右子树。

上图的前序遍历顺序为 12453

cpp
void dfs(int u) { // 遍历以 u 为根的树
    if (!u) return;
    cout << u << ' ';
    dfs(l[u]); // l[u]: u 的左子节点
    dfs(r[u]); // r[u]: u 的右子节点
}

二叉树的恢复

给定一棵二叉树的前序和中序遍历序列,求后序遍历序列。

  • 前序遍历:DBACEGF
  • 中序遍历:ABCDEFG
  • 后序遍历:ACBFGED

阅读程序,得到各个遍历方式的规律:

  • 前序遍历:第一个元素是根节点;      DBArootCEGF      
  • 中序遍历:根节点左边的都在左子树,右边的都在右子树。ABCleftDEFGrightroot
  • 后序遍历:最后一个元素是根节点。      ACBFGED      root

根据前序遍历,可以确定 D 是根节点。于是在中序遍历序列中找到 D

ABCDEFG

处于 D 左边的 ABCD 的左子树上;D 右边的 EFG 在右子树上。

比较整棵树的前序、中序遍历序列,还可以得出左右子树的前序、中序遍历序列:

  • 前序遍历:DBACEGF

  • 中序遍历:ABCDEFG

  • 左子树:

    • 前序遍历:BAC
    • 中序遍历:ABC
  • 右子树:

    • 前序遍历:EGF
    • 中序遍历:EFG

对左右子树进行相同的操作,就能得出整棵树的结构。

最后再后序遍历,输出序列。

cpp
#include <bits/stdc++.h>
using namespace std;

char l[255], r[255];

// pre: 前序序列    mid: 中序序列
void build(string pre, string mid) {
    if (!pre.size())
        return;
    
    char root = pre[0]; // 前序遍历序列的第一个是根节点 
    
    int p = 0;
    while (mid[p] != root) p ++; // 在中序遍历中找到根节点位置
    
    string l_pre = pre.substr(1, p);  // 左子树 - 前序
    string l_mid = mid.substr(0, p);  // 左子树 - 中序
    string r_pre = pre.substr(p + 1); // 右子树 - 前序
    string r_mid = mid.substr(p + 1); // 右子树 - 中序
    
    if (l_pre.size()) // 存在左子树
        l[root] = l_pre[0];
    if (r_pre.size()) // 存在右子树
        r[root] = r_pre[0];
    
    build(l_pre, l_mid); // 递归构建左子树
    build(r_pre, r_mid); // 递归构建右子树
}

// 后序遍历
void dfs(char u) {
    if (!u) return;
    dfs(l[u]);
    dfs(r[u]);
    cout << u << ' ';
}

int main() {
    build("DBACEGF", "ABCDEFG");
    dfs('D'); // D 是根节点 
    return 0;
}