Appearance
定义
树有多种等价的定义方式:
- 连通且无环的无向图;
- 有
个节点和 条边的无向图; - 任意两个顶点间只有一条路径的无向图。
图论中的树看起来更像现实中倒悬的树:
树的节点存在「父子关系」:
- 有连边的两个节点中,上节点为下节点的父节点。节点
是节点 的父节点; - 有连边的两个节点中,下节点为上节点的子节点,节点
是节点 的子节点; - 没有父节点的节点为根节点,如节点
; - 没有子节点的节点为叶节点,如节点
。
有根树和无根树
有根树必须明确根节点,而无根树的任意节点都可以是根节点。下面的左图和右图是同一棵无根树:
子树
将节点
层和深度
定义根节点在第
树的深度
二叉树
任意节点的子节点数量
满二叉树
深度为
满二叉树除最后一层外,其它层任意节点都有
完全二叉树
将满二叉树最后一层右边连续的若干节点删除,得到完全二叉树:
满二叉树是一类特殊的二叉树。
森林
多棵树组成的图为森林:
二叉树的遍历
对于二叉树,可以使用 深度优先搜索 DFS 遍历所有节点。二叉树定义了
- 访问根节点
; - 递归遍历
的左子树; - 递归遍历
的右子树。
上图的前序遍历顺序为
cpp
void dfs(int u) { // 遍历以 u 为根的树
if (!u) return;
cout << u << ' ';
dfs(l[u]); // l[u]: u 的左子节点
dfs(r[u]); // r[u]: u 的右子节点
}
二叉树的恢复
给定一棵二叉树的前序和中序遍历序列,求后序遍历序列。
- 前序遍历:
; - 中序遍历:
; - 后序遍历:
。
阅读程序,得到各个遍历方式的规律:
- 前序遍历:第一个元素是根节点;
- 中序遍历:根节点左边的都在左子树,右边的都在右子树。
- 后序遍历:最后一个元素是根节点。
根据前序遍历,可以确定
处于
比较整棵树的前序、中序遍历序列,还可以得出左右子树的前序、中序遍历序列:
前序遍历:
; 中序遍历:
。 左子树:
- 前序遍历:
; - 中序遍历:
。
- 前序遍历:
右子树:
- 前序遍历:
; - 中序遍历:
。
- 前序遍历:
对左右子树进行相同的操作,就能得出整棵树的结构。
最后再后序遍历,输出序列。
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;
}