第六章树和二叉树 6.1树的定义和基本术语 6.2二叉树 6.2.1二叉树的定义 6.2.2二叉树的性质 6.2.3二叉树的存储结构 6.3遍历二叉树和线索二叉树 6.3.1遍历二叉树 6.3.2线索二叉树 6.4树和森林 6.4.1树的存储结构 6.4.2森林与二叉树的转换 6.6赫夫曼树及其应用 6.6.1最优二叉树(赫夫曼树)
第 六 章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 赫夫曼树及其应用 6.6.1 最优二叉树(赫夫曼树)
第六章树和二叉树 6.1树的定义和基本术 非线性数据结构 树的递归定义: 树(tree)是n(>=0)个结点的有限集 当n>0时, (1)有且仅有一个特定的称为根(root)的结点 (2)当n>1时,其余结点可分为mm>0)个互不相 交的有限集T1,T2,,Tm,其中每个集合本身又是 棵树。称为子树( subtree)
第六章 树和二叉树 6.1 树的定义和基本术语 非线性数据结构。 树的递归定义： 树(tree)是n(n>=0)个结点的有限集。 当n>0时, (1)有且仅有一个特定的称为根(root)的结点; (2)当n>1时,其余结点可分为m(m>0)个互不相 交的有限集T1 ,T2 ,...,Tm,其中每个集合本身又是一 棵树。称为子树(subtree)
树的示例 层次 A A 空树只有根结点 D 0的树n=1 B E F( H K 般的树
树的示例 空树 n=0 层次 1 2 3 4 一般的树 A B C D E F G H I J K L 只有根结点 的树 n=1 A
树的抽象数据类型定义: ADT Tree 数据对象D:D是具有相同特性的数据元素的集 数据关系R:若D为空集,则称为空树 若D仅含一个数据元素,则R为空集,否则R={H H是如下二元关系: 1)在D中存在唯一的称为根的数据元素root,它在 关系H下无前驱; 2)若D-{root}≠φ,则存在D-{root}的一个 划分D1,D D(m>0 对任意j≠k(1 有DnD=3,直对任意的(1≤m),唯一存在数据 素x1D,有<ootx>H (3)对应于D-{root}的划分,H-{< rootx1>, <root 有唯一的一个划分H1,H >0 m 对任意≠k(1≤jk≤m)有再∩H=中,且对任意的i m),H1:是D.上的二元关系 {H1})是 棵符合本定义的树,称为根root的子树
树的抽象数据类型定义： ADT Tree｛ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树; 若D仅含一个数据元素，则R为空集，否则R＝｛H｝， H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在 关系H下无前驱； （2）若D－｛root｝≠φ，则存在D－｛root｝的一个 划分D1 , D2 , ..., Dm （m＞0），对任意j≠k（1≤j,k≤m） 有Dj∩Dk=φ ，且对任意的i（1≤i≤m），唯一存在数据 元素xiξDi，有<root,xi>ξH; （3）对应于D－｛root｝的划分，H－｛<root,x1>，....， <root,xm >｝有唯一的一个划分H1 , H2 ,..., Hm （m＞0）， 对任意j≠k（1≤j,k≤m）有Hj∩Hk=φ ，且对任意的i （1≤i≤m），Hi 是Di上的二元关系，（Di ,{Hi}）是一 棵符合本定义的树，称为根root的子树
树的抽象数据类型定义: 基本操作(之一) iniTTREE (&T) 操作结果:构造空树T DESTRoYTREE(&t) 初始条件:树T存在。 操作结果:销毁树T。 createtreE (&T, DEFINITION 初始条件: DEFINITION给出树T的定义 操作结果:按 DEFINITION构造树T cleartree(&T) 初始条件:树T存在 操作结果:将树T清为空树
树的抽象数据类型定义： 基本操作（之一） INITTREE（＆T）； • 操作结果：构造空树T。 DESTROYTREE（＆T）； • 初始条件：树T存在。 • 操作结果：销毁树T。 CREATETREE（＆T，DEFINITION）； • 初始条件：DEFINITION给出树T的定义。 • 操作结果：按DEFINITION构造树T。 CLEARTREE（＆T）； • 初始条件：树T存在。 • 操作结果：将树T清为空树