第六章树和二叉树 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,有H (3)对应于D-{root}的划分,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，有ξH; （3）对应于D－｛root｝的划分，H－｛，....， ｝有唯一的一个划分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清为空树
树的抽象数据类型定义: 基本操作(之二) TREEEMPTY (T) 初始条件:树T存在 操作结果:若T为空树,则返回TURE,否则 FALSE。 TREEDEPTH (T) 初始条件:树T存在 操作结果:返回T的深度。 ROOT(T) 初始条件:树T存在 操作结果:返回T的根。 VALUE (T CUR E); 初始条件:树T存在,CURE是T中某个结点 操作结果:返回CURE的值
树的抽象数据类型定义： 基本操作（之二） TREEEMPTY（T） • 初始条件：树T存在。 • 操作结果：若T为空树，则返回TURE，否则FALSE。 TREEDEPTH（T） • 初始条件：树T存在。 • 操作结果：返回T的深度。 ROOT（T） • 初始条件：树T存在。 • 操作结果：返回T的根。 VALUE（T, CUR_E）； • 初始条件：树T存在，CUR＿E是T中某个结点。 • 操作结果：返回CUR＿E的值
树的抽象数据类型定义: 基本操作(之三) ASSiGN(T, CUR E, VALUE 初始条件:树T存在,CURE是T中某个结点 操作结果:结点CURE赋值为 VALUE。 PARENT(T, CUR E) 初始条件:树T存在,CURE是T中某个结点。 操作结果:若CURE是T的非根结点,则返回它的双亲,否则 函数值为 LEFTCHILD(T, CUR E) 初始条件:树T存在,CURE是T中某个结点。 操作结果:若CURE是T的非叶子结点,则返回它的最左孩子 否则返回“空”。 RIGHTSIBLING (T, CUR E) 初始条件:树T存在,CURE是T中某个结点。 操作结果:若CURE有右兄弟,则返回它的右兄弟,否则函数 值为“空
树的抽象数据类型定义： 基本操作（之三） ASSIGN（T，CUR_E，VALUE） • 初始条件：树T存在，CUR＿E是T中某个结点。 • 操作结果：结点CUR_E赋值为VALUE。 PARENT（T，CUR＿E） • 初始条件：树T存在，CUR＿E是T中某个结点。 • 操作结果：若CUR＿E是T的非根结点，则返回它的双亲，否则 函数值为“空”。 • LEFTCHILD（T，CUR＿E） • 初始条件：树T存在，CUR＿E是T中某个结点。 • 操作结果：若CUR＿E是T的非叶子结点，则返回它的最左孩子， 否则返回“空”。 RIGHTSIBLING（T，CUR＿E） • 初始条件：树T存在，CUR＿E是T中某个结点。 • 操作结果：若CUR＿E有右兄弟，则返回它的右兄弟，否则函数 值为“空
树的抽象数据类型定义: 基本操作(之四) inserTChiLD(&T, &P, I, C) 初始条件:树T存在,P指向T中某个结点,1<<P所指结 点的度+1,非空树C与T不相交。 操作结果:插入C为T中P指结点的第I棵子树。 DELETECHILD(&t, &P, D 初始条件:树存在,P指向T中某个结点,1≤P指结点 的度。 操作结果:删除T中P所指结点的第I棵子树。 TRAVERSETREE (T, VISIT ()) 初始条件:树t存在,ⅥSIT是对结点操作的应用函数。 操作结果:按某种次序对T的每个结点调用函数VSIT 次且至多一次。一旦VSIT()失败,则操作失败 3 ADT TREE
树 的 抽 象 数 据 类 型 定 义 ： 基本操作（之四） INSERTCHILD（＆T，＆P，I，C）； • 初始条件：树T存在，P指向T中某个结点，1≤I≤P所指结 点的度＋1，非空树C与T不相交。 • 操作结果：插入C为T中P指结点的第I棵子树。 DELETECHILD（＆T，＆P，I）； • 初始条件：树T存在，P指向T中某个结点，1≤I≤P指结点 的度。 • 操作结果：删除T中P所指结点的第I棵子树。 TRAVERSETREE（T，VISIT（））； • 初始条件：树t存在，VISIT是对结点操作的应用函数。 • 操作结果：按某种次序对T的每个结点调用函数VISIT（） 一次且至多一次。一旦VISIT（）失败，则操作失败。 ｝ADT TREE
树的基本术语(之一) 子树( subtree) 结点 结点的度( degree) 叶子(eaf)(终端结点) 分支结点(非终端结点)(F(G(H)(D 树的度
树的基本术语（之一） 子树(subtree) 结点 结点的度(degree) 叶子(leaf)(终端结点) 分支结点(非终端结点) 树的度 A B C D F G H I L
树的基本术语(之二) 孩子( child) A 双亲( parent 兄弟( sibling) B D 堂兄弟 祖先 F H 子孙
树的基本术语（之二） 孩子(child) 双亲(parent) 兄弟(sibling) 堂兄弟 祖先 子孙 A B C D F G H I L