数据结构课件 第6章 树和二叉树

Data Structure
2011-6-23
Page 18
树的抽象数据类型的定义 ADT Tree { 数据对象： 是具有相同特性的数据元素的集合。 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 数据关系：
为空集，则称为空树 空树； 若 D 为空集，则称为空树； 中仅含一个数据元素，则关系R为空集； 若 D 中仅含一个数据元素，则关系R为空集； 若 D 中含多于一个数据元素，则 R={H}，H是如下二元关系： 中含多于一个数据元素， R={H}， 是如下二元关系： root，它在关系H下无前驱； (1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱； n>1时 个互不相交的(非空) (2) 当n>1时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树， 集 T1,T2, ,Tm, 其中每一个子集本身又是一棵符合本定义的树， 的子树，每一棵子树的根xi都是根root的后继， xi都是根root的后继 称为根 root 的子树，每一棵子树的根xi都是根root的后继，即 <root,xi>∈H，i=1,2,…,m。 <root,xi>∈ i=1,2, ,m。 ,m
Data Structure 2011-6-23 Page 20
TreeDepth(T); 初始条件： 存在。 初始条件：树T存在。 操作结果：返回T的深度。 操作结果：返回T的深度。 Root(T); 初始条件： 存在。 初始条件：树 T 存在。 操作结果： 的根。 操作结果：返回 T 的根。 Value(T, cur_e); 初始条件： 存在， 中某个结点。 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果： 的值。 操作结果：返回 cur_e 的值。
Data Structure
2011-6-23
Page 5
只有根结 点的树 A
有子树 的树 A B E K L F C G
根
D H M I J
子树
Data Structure
2011-6-23
Page 6
树中各子树互不相交的含义
两点①某结点不能同时属于两个子集，如图(b)所示； ②两个子集的结点之间不能有关系，如图(c)所示.
A B D E F
Data Structure
D C G E G B F A C
2011-6-23
Page 17
结点A的度： 结点A的度：3 结点B的度： 结点B的度：2 结点M的度： 结点M的度：0 树的度： 树的度：3 结点A的孩子： 结点A的孩子：B，C，D 结点B的孩子： 结点B的孩子：E，F A B F L C G H M
Data Structure
2011-6-23
Page 19
基本操作： 基本操作： InitTree(&T); 操作结果： 操作结果：构造空树 T。 CreateTree(&T,definition); 初始条件： 给出树T的定义。 初始条件：definition 给出树T的定义。 操作结果： 操作结果：按 definition 构造树 T。 DestroyTree(&T); 初始条件： 存在。 初始条件：树 T 存在。 操作结果： 操作结果：销毁树 T。 TreeEmpty(T); 初始条件： 存在。 初始条件：树 T 存在。 操作结果： 为空树， TRUE， FALSE。 操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。
G D E F
数据结构中讨论的一般都是有序树
Data Structure 2011-6-23 Page 15
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
森林： 棵互不相交的树的集合。 森林：m (m≥0)棵互不相交的树的集合。 棵互不相交的树的集合 A B E K L F C H D J
Data Structure
1层 D H M
2011-6-23
C F G
2层 层 J 3层 层 4层
Page 13
高度＝ 高度＝4
I
L
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
层序编号：将树中结点按照从上层到下层、 层序编号：将树中结点按照从上层到下层、同层从左 到右的次序依次给他们编以从1开始的连续自然数。 到右的次序依次给他们编以从1开始的连续自然数。 A B
是n(n≥0)个结点的有限集T； n(n≥0)个结点的有限集T 个结点的有限集 在任意一棵非空树中， 在任意一棵非空树中， 有且仅有一个特定的结点，称为树的根(root)； 有且仅有一个特定的结点，称为树的根(root)； 当n>1时，其余结点可分为m(m>0)个互不相交的有限集 n>1时 其余结点可分为m(m>0)个互不相交的有限集 m(m>0) T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子 Tm， T1,T2, Tm 其中每一个集合本身又是一棵树，称为根的子 subtree)。 树(subtree)。 特点： 特点： 非空树中至少有一个结点——根； 根 非空树中至少有一个结点 树中各子树是互不相交的集合。 树中各子树是互不相交的集合。
Data Structure
2011-6-23
Page 16
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
同构： 对两棵树， 若通过对结点适当地重命名， 同构 ： 对两棵树 ， 若通过对结点适当地重命名 ， 就可以使这两棵树完全相等（ 结点对应相等， 就可以使这两棵树完全相等 （ 结点对应相等 ， 结 点对应关系也相等） 则称这两棵树同构。 点对应关系也相等），则称这两棵树同构。
叶子结点：度为 的结点 也称为终端结点。 的结点， 叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 分支结点：度不为 的结点，也称为非终端结点。 的结点 A B E K L F C G H M D I J
Data Structure
2011-6-23
Page 9
10
100
第六章 树和二叉树
865
Data Structure
2011-6-23
Page 1
学习目标
领会树和二叉树的类型定义，理解树和二叉树的结构差别。 领会树和二叉树的类型定义，理解树和二叉树的结构差别。 熟记二叉树的主要特性，并掌握它们的证明方法。 熟记二叉树的主要特性，并掌握它们的证明方法。 二叉树的主要特性 熟练掌握二叉树的各种遍历算法， 熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二 二叉树的各种遍历算法 叉树的其它操作。 叉树的其它操作。 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前 二叉树的线索化过程 驱和后继的方法。 驱和后继的方法。 熟练掌握二叉树和树的各种存储结构及其建立的算法。 熟练掌握二叉树和树的各种存储结构及其建立的算法。 存储结构及其建立的算法 学会编写实现树的各种操作的算法。 学会编写实现树的各种操作的算法。 树的各种操作的算法 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。 最优树和赫夫曼编码的方法
Data Structure
2011-6-23
Page 12
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
结点所在层数：根结点的层数为1 对其余任何结点， 结点所在层数：根结点的层数为1；对其余任何结点， 若某结点在第k 则其孩子结点在第k+1 k+1层 若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度 高度。 树的深度：树中所有结点的最大层数，也称高度பைடு நூலகம் C B E K
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
孩子、双亲： 孩子、双亲：树中某结点子树的根结点称为这个结点 孩子结点，这个结点称为它孩子结点的双亲结点 双亲结点； 的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 兄弟：具有同一个双亲的孩子结点互称为兄弟。 A B E K L F C G H M
2011-6-23 Page 10
D I J
Data Structure
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
路径：如果树的结点序列 有如下关系： 路径：如果树的结点序列n1, n2, …, nk有如下关系： 结点n 的双亲（ ），则把 结点 i是ni+1的双亲（1<=i<k），则把 1, n2, …, nk称 ），则把n 为一条由n 的路径； 为一条由 1至nk的路径；路径上经过的边的个数称为 路径长度。 路径长度。 A B E K
A B D E F H I C G D B
A C F G B D
A E F C G
(a) 一棵树结构
Data Structure
(b)一个非树结构 一个非树结构
2011-6-23
(c)一个非树结构 一个非树结构
Page 7
6.1 树的定义和基本术语——树的基本术语 树的定义和基本术语——树的基本术语
叶子： 叶子：K，L，F，G，M，I，J 结点I的双亲： 结点I的双亲：D 结点L的双亲： 结点L的双亲：E 结点B 结点B，C，D为兄弟 结点K 结点K，L为兄弟 J 结点A是结点F 结点A是结点F，G的祖先 结点F 结点F，G为堂兄弟 树的深度： 树的深度：4
D I
E K 结点A的层次： 结点A的层次：1 结点M的层次： 结点M的层次：4