数据结构与算法 --2. 树

發表於 更新於 分類於

一、基本概念

1. 树的定义：递归定义

2. 基本术语

父节点，子节点，兄弟节点
根节点，叶节点
层 (深度)，高度 (树的高度 = 根节点的高度)
有序树 (兄弟节点之间是有顺序的)，无序树

路径 (树的边是单向的)，路径长度 (一条路径边的个数)，带权路径
节点的度 (子节点的数量)，树的度 (最大的度)

3. 树的性质

(1) $n=e+1$ 树中的节点数等于所有结点的度数加 1

边数 $d$，度数 $e$，$d=e$
可以用归纳法证明

(2) 度为 $m$ 的树中，第 $i$ 层上至多有 $m^{i-1}$ 个节点 ($i \geq 1$)
(3) 高度为 $h$ 的 $m$ 叉树中至多有 $\displaystyle {(m^h-1) \over (m-1)}$ 个节点

由性质（2）可得：$n \leq 1+m+m^2+…+m^{h-1}$
$\displaystyle n \leq {(m^h-1) \over (m-1)}$

(4) 具有 $n$ 个节点的 $m$ 叉树的最小高度为 $\lceil \log_m {(n (m-1)+1)} \rceil$

由性质（3）可得：$h \geq \log_m {n (m-1)+1}$

(5) 叶节点个数

$n=k_0+k_1+…+k_m -(1)$
$n=\sum_{i=0}^n d_i +1 \quad (d_i = 节点 n_i 的度数)$
$\quad =\sum_{i=0}^m i \cdot k_i \quad (k_i = 度为 i 的节点的数量)$
$\quad =k_1+2k_2+…+mk_m+1 -(2)$
$ 由式 (1) 和式 (2) 可得 $
$k_0=k_2+k_3+…+(m-1) k_m+1$

二、二叉树

1. 与 {度为 2 的有序树} 不同

只有一个根节点不属于 {度为 2 的有序树}

2. 特殊二叉树种类

满二叉树，完全二叉树

3. 性质

$n=k_0+k_1+k_2$
$k_0=k_2+1$
$ 两式相减得：k_0-n=1-k_0-k_1$
$2k_0=n+1-k_1$
$\displaystyle 当 k_1=0，n 为奇数，k_0={(n+1) \over 2}$
$\displaystyle 当 k_1=0，n 为偶数，k_0={n \over 2}$
$\displaystyle 结论：在完成二叉树或满二叉树中，k_0=\lceil {n \over 2} \rceil$

4. 存储结构

(1) 顺序存储

按照完全二叉树的顺序，父节点和子节点之间有简单的关系
但是可能会造成空间浪费

(2) 链式存储
C++
1
2
3
4
5
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *ichild, *rchild;
} BiTNode, *BiTree;

5. 二叉树的遍历

(1) 遍历有先序 (NLR)、中序 (LNR)、后序 (LRN) 三种遍历算法，其中 “序” 指的是根节点在何时被访问
C++
1
2
3
4
5
6
7
8
9
10
// 先序遍历
void PreOrder (BiTree T)
{
	if (T!=NULL)
	{
		visit (T);            // 访问根节点
		PreOrder (T->ichild); // 递归遍历左子树
		PreOrder (T->echild); // 递归遍历右子树
	}
}
(2) 非递归算法
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 中序遍历的非递归算法
void InOrder2 (BiTree T)
{
	InitStack (S); BiTree p = T;
	while (p || !IsEmpty (S))
	{
		if (p)
		{
			Push (S,p);
			p = p->lchild;
		}

		else
		{
			Pop (S,p); visit (p);
			p = p->rchild;
		}
	}
}
// 入栈序列：先序
// 出栈序列：中序
(3) 层次遍历

利用队列：
将根节点入队
若队列不为空：队头元素出队，访问队头元素若有子节点，子节点入队

(4) 由遍历序列构造二叉树
(a) 先序 + 中序

中序遍历最左端元素第一个访问，排序树的插入会用到这个性质
先序序列第一个元素是根节点

(b) 后序 + 中序
(c) 层次 + 中序

数据结构与算法系列

数据结构与算法 —1. 线性表
数据结构与算法 —2. 树
数据结构与算法 —3. 图
数据结构与算法 —4. 查找
数据结构与算法 —5. 排序