数据结构3第3章：树.pdfVIP

数据结构与算法第3章树

线性表——元素之间的线性关系

树——元素之间的层次关系

第3章树Tree）

3.1基本术语

3.2二叉树*

3.3堆

3.4选择树

3.5树

3.6森林与二叉树间的转换

3.7树的应用

2015秋Slide.3-1

数据结构与算法第3章树

3.1基本术语

[定义]1、一个结点x组成的集{x}是一株树(Tree)，这个结点x也是

一这株树的根。

2、假设x是一个结点，D，D，…，D是k株互不相交的

12k

树，我们可以构造一株新树：令x为根，并有k条边由

x指向树D，D，…，D。这些边也叫做分支，D，D，

12k12

…，D称作根x的树之子树SubTree）。

k

[定义]树是n0）个结点的有限集。在任意一棵非空树中：

二1、有且仅有特定的称为根Root）的结点；

2、当n＞1时，其余结点可分为k＞0）个互不相交的有限

集D，D，…，D，其中每一个集合本身又是一棵树，

12k

并且称为根的子树SubTree）。

2015秋Slide.3-2

数据结构与算法第3章树

[定义三]

T=D，R）

D：具有相同类型的数据元素的集合。

R：若D为空集，则称为空树；

若D仅含一个数据元素，则R为空集，否则R={H}，H是

如下的二元关系：

1、在D中存在唯一的称为根的数据元素root，它在关系H下

无前驱；

2、若D-{root}≠￠，则存在D-{root}的一个划分D，D，…，

12

Dk＞0），对任意j≠l1≤j，l≤k）有D∩D=￠，

kjl

且对任意的i1≤i≤m），唯一存在数据元素x∈D，

ii

有root,x∈H;

i

3、对应于