数据结构与算法春浙江课件9树

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(n=0)个结点的有限集。 当n0时, (1)有且仅有一个特定的称为根(root)的结点; (2)当n1时,其余结点可分为m(m0)个互不相交的有限集T

2、1,T2,.,Tm,其中每个集合本身又是一棵树。称为子树(subtree)。树的示例空树 n=0层次1234一般的树ABCDEFGHIJKL只有根结点的树 n=1A树的抽象数据类型定义：ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树; 若D仅含一个数据元素，则R为空集，否则RH，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若Droot，则存在Droot的一个划分D1, D2, ., Dm （m0），对任意jk（1j,km）有DjDk= ，且对任意的i（1im），唯一存在数据元素xiDi，有

3、H;（3）对应于Droot的划分，H，.，有唯一的一个划分H1 , H2 ,., Hm （m0），对任意jk（1j,km）有HjHk= ，且对任意的i（1im），Hi 是Di上的二元关系，（Di ,Hi）是一棵符合本定义的树，称为根root的子树。树的抽象数据类型定义：基本操作（之一） INITTREE（T）； 操作结果：构造空树T。 DESTROYTREE（T）； 初始条件：树T存在。 操作结果：销毁树T。 CREATETREE（T，DEFINITION）； 初始条件：DEFINITION给出树T的定义。 操作结果：按DEFINITION构造树T。 CLEARTREE（T）； 初始条件：树T

4、存在。 操作结果：将树T清为空树。树的抽象数据类型定义：基本操作（之二） TREEEMPTY（T） 初始条件：树T存在。 操作结果：若T为空树，则返回TURE，否则FALSE。 TREEDEPTH（T） 初始条件：树T存在。 操作结果：返回T的深度。 ROOT（T） 初始条件：树T存在。 操作结果：返回T的根。 VALUE（T, CUR_E）； 初始条件：树T存在，CURE是T中某个结点。 操作结果：返回CURE的值。树的抽象数据类型定义：基本操作（之三） ASSIGN（T，CUR_E，VALUE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：结点CUR_E赋值 为VALUE。 P

5、ARENT（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE是T的非根结点，则返回它的双亲，否则函数值为“空”。 LEFTCHILD（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 RIGHTSIBLING（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE有右兄弟，则返回它的右兄弟，否则函数值为“空”。树的抽象数据类型定义：基本操作（之四） INSERTCHILD（T，P，I，C）； 初始条件：树T存在，P指向T中某个结点，1IP所指结点

6、的度1，非空树C与T不相交。 操作结果：插入C为T中P指结点的第I棵子树。 DELETECHILD（T，P，I）； 初始条件：树T存在，P指向T中某个结点，1IP指结点的度。 操作结果：删除T中P所指结点的第I棵子树。 TRAVERSETREE（T，VISIT（）； 初始条件：树t存在，VISIT是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数VISIT（）一次且至多一次。一旦VISIT（）失败，则操作失败。ADT TREE树的基本术语（之一）子树(subtree)结点结点的度(degree)叶子(leaf)(终端结点)分支结点(非终端结点)树的度ABCDFGHIL树的基本

7、术语（之二） 孩子(child) 双亲(parent) 兄弟(sibling) 堂兄弟 祖先 子孙ABCDFGHIL树的基本术语（之三）子树(subtree) 层次(level) 深度(depth) 有序树 无序树 森林: m(m=0)棵互不相交的树的集合.ABCDFGHIL6.2 二叉树6.2.1 二叉树的定义二叉树(binary tree): 度不超过2的有序树。二叉树的五种基本形态(a) 空二叉树; (b)仅有根结点的二叉树；(c)右子树为空的二叉树；(d)左、右子树均为非空的二叉树； (e)左子树为空的二叉树。(a)A(b)A(c)A(d)A(e)6.2.2 二叉树的性质性质1：在二叉

8、树的第i层上至多有2(i-1)个结点(i=1).性质2：深度为k的二叉树至多有2k-1个结点(k=1). k Nk = 2i-1 = 2k-1 i = 1性质3:对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为n2, 则 n0 = n2 + 1.一般的二叉树ABDEFHIJKL层次1234满二叉树的定义:一棵深度为k且有 2k-1个结点的二叉树称为满二叉树。k = 3k = 4123456789141011151213完全二叉树的定义: 深度为k的，有n个结点的二叉树， 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时， 称之为完全二叉树。123456完全

9、二叉树和非完全二叉树举例:123456789101112完全二叉树123456非完全二叉树完全二叉树性质4：具有n个结点的完全二叉树的深度为log2n*+1。性质5： 如果对一棵有n个结点的完全二叉树（其深度为log2n*+1）的结点按层序编号（从第1层到第log2n*+1层，每层从左到右），则对任一结点i（1in），有（1）如果i1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT（i）是结点 i/2*。（2）如果2in，则结点i无左孩子（结点i为叶子结点），否则其左孩子LCHILD（i）是结点2i。（3）如果2i1n，则结点i无右孩子； 否则其右孩子RCHILD（i）是结点2i

10、+1.6.2.3 二叉树的存储结构一、顺序存储结构/-二叉树的顺序存储表示- # define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;上一节完全二叉树的十二个结点的顺序存储为：上一节非完全二叉树的六个结点的顺序存储（需7个存储空间）为：1 23 45 67 89 10 11 121 23 40 5 6最坏情况：深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。二、链式存储结构typedef struct BiTNode TElemType data; struct BiTNode

11、 *lchild,*rchild; /左右孩子指针BiTNode,*BiTree;rchilddatalchilddataparentlchildrchilddatalchildrchildparent链式存储结构示例树的二叉链表示。三叉链表示略ABCDGEFABCDEFG/BDA/E/F/G/C/0123456123456基本操作的函数原型说明(一)Status CreateBiTree(BiTree &T);/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。Status PreOrderTraverse(BiTree T, Status(*Vis

12、it)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数/先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。/一旦Visit( ) 失败，则操作失败。基本操作的函数原型说明(二) Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/中序遍历二叉树T，一旦Visit( ) 失败，则操作失败。Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e);/采用二叉链表存储结