《计算机软件基础》多媒体教程
第十三讲
第四章 数据结构
4.4 树
4.4.1 树的基本概念
⊙ 定义
设 B=(K,R)是数据结构，K 中有 n 个结点，R 中只有一种关系 r。定义 B 是一棵树，必
须满足两个条件：
(1) K 中有且仅有一个始结点，称为根结点。
(2) K 中除了根结点以外的所有结点，可分成 m 个互不相交的集合{T
1
, T
2
, …, T
m
}，每
个集合 T
i
中的结点又都是一棵树，即以 T
i
为根结点的子树。
例： T = k
1
+{T
1
+ T
2
+ T
3
} T
1
= k
5
+{k
3
, k
10
}
T
2
= k
6
+{k
8
, k
9
, k
4
} T
3
= k
2
⊙ 树的图形表示
前件在上，后件在下，省略箭头。
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
⊙ 树的特性及命名
※ 除了根以外，其他结点有且仅有一个前件。
※ 前件称为父结点，父结点及其以上的所有结点称为父辈结点。
※ 后件称为子结点，子结点及其以下的所有结点称为子辈结点。
※ 没有子树(后件)的结点为叶结点，即终结点。
※ 非根非叶的结点称为内结点。
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
8
的
父结点
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
4
k
1
k
6
k
8
k
2
k
10
k
5
k
3
k
9
k
8
的
父辈结点
根结点
叶结点
内结点
※ n次树
若某树中结点的最大后件数为 n，则称该树为 n 次树。
例如：T1 为四次树。
※ n次完全树
若某树中所有结点的后件数要么等于 0，要么等于 n，称为 n 次完全树(根和内结点的后
件数为 n，叶的后件数为 0)。
例如：T2 为二次完全树。
※ 有序树
剩余10页未读，继续阅读
资源评论
