数据结构第六章树和二叉树.ppt

《数据结构第六章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章树和二叉树.ppt（69页珍藏版）》请在三一文库上搜索。

1、,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A 线性结构,B 非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,第六章 树和二叉树,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.6.2 赫夫曼编码,树形结构

2、是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。,树形结构 结点间具有分层次的连接关系,6.1 树的定义和基本术语,树(Tree)是n(n0)个结点的有限集合T，它满足如下条件： 有且仅有一个称为根(Root)的结点。 其余结点可划分为m(m=0)个互不相交的有限集合T1 ,T2,Tm,其中每个集合又是一棵树，并称其为根的子树(SubTree)。 这是一个递归定义。有时n=0也称为空树。,树的表示方法,1）树形图法 2）嵌套集合法 3）广义表形式 4）凹入表示法,( A(B, C(E,F), D(G) ) ),线性结构 （一对一关系） 树结构（

3、一对多关系） 第一个数据元素(无前驱) 根结点(无前驱) 最后一个数据元素(无后继) 多个终端结点(无后继) 其它数据元素 树中其它结点 (一个前驱、一个后继) (一个前驱、多个后继),树形结构和线性结构的比较,树结构的基本术语,结点(node)表示树中的元素，包括数据元素及若干指向其子树的分支。 结点的度(degree)结点拥有的子树数。 叶子(leaf)或终端结点度为0的结点。 分支结点度大于零的结点。 树的度树中所有结点的度的最大值。 孩子(child)结点的子树的根。 双亲(parents)孩子结点的上层结点。 兄弟(sibling)同一双亲的孩子。 堂兄弟其双亲在同一层的结点互为堂兄

4、弟。 结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层。 深度(depth)树中结点的最大层次数。 森林(forest)m(m0)棵互不相交的树的集合。,树的抽象数据类型定义：,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），唯一存在数据元素

5、xiDi，有 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。 C

6、learTree(&T ) ； 初始条件：树T存在。 操作结果：将树T清为空树。,树的抽象数据类型定义-基本操作（之二）,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存在，cur_e是T

7、中某个结点。 操作结果：结点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有右兄弟，则返回它的右兄弟，否则函数值为 “空”。,树的抽象数据类型定义-基本操作（之

8、四）,InsertChild(&T，&p，i，c)； 初始条件：树T存在，p指向T中某个结点，1ip所指结点的度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,6.2 二叉树

9、,二叉树的定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 二叉树的特点： 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒,二叉树的五种基本形态：,空二叉树,只有一个根结点 的二叉树,右子树为空 的二叉树,左子树为空 的二叉树,左、右子树均 非空的二叉树,注意：二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树,这不是二叉树,这是二叉树,6.2.2 二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 性质2：深度为k的二叉树至多

10、有2k-1个结点 (k1)。 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,几种特殊形态的二叉树,满二叉树 定义：深度为k且有2k-1个结点的二叉树 特点：每一层上的结点数都是最大结点数 完全二叉树 定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。 特点： 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1 说明：满二叉树是完全二叉树,反之不成立; 对于完全二叉树,若某结点无左孩子,则必无右孩子

11、, 该结点为叶结点。,性质4：具有n个结点的完全二叉树的深度为log2n +1 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是i/2 (2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,6.2.3 二叉树的存储结构,顺序存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。,下

12、标 0 1 2 3 4 5 6 7 8 9 10 11,对完全二叉树而言，顺序存储结构既简单又节省存储空间。 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。 (最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间),链式存储结构,typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTNode,*BiTree;,链式存储结构示例,注意： 一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的

13、指针为空。 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。,基本操作的函数原型说明(一),Status CreateBiTree(BiTree /采用二叉链表存储结构,Visit是对结点操作的应用函数 /先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。 /一旦Visit( ) 失败，则操作失败。,基本操作的函数原型说明(二),Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /中序遍历

14、二叉树T，一旦Visit( ) 失败，则操作失败。 Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /后序遍历二叉树T，一旦Visit( ) 失败，则操作失败。 Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /层序遍历二叉树T，一旦Visit( ) 失败，则操作失败。,6.3 遍历二叉树,按某条搜索路径巡访二叉树中

15、每个结点，使得每个结点均被访问一次，而且仅被访问一次。,假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。,先序遍历二叉树的操作定义,若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 A B C D F E G,中序遍历二叉树的操作定义,若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 C B D

16、 F A G E,后序遍历二叉树的操作定义,若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 C F D B G E A,例：已知结点的先序序列和中序序列，求整棵二叉树,先序序列：A B C D E F G 中序序列：C B E D A F G,先序遍历二叉树的递归算法,Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTra

17、verse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraverse,作业,分别写出中序遍历二叉树和后序遍历二叉树的递归算法 已知一棵二叉树的中序和后序序列如下，画出此二叉树并写出该二叉树的先序遍历序列。 中序序列：A,B,C,D,J,E,F,H,G,I 后序序列：B,C,J,D,A,H,I,G,F,E,中序遍历二叉树的非递归算法,基本思想 中序遍历一棵非空树t时 ，首先应该进入t的左子树访问，此时由于t的根结点及右子树尚未访问，因此必须将t保存起来，放入栈中，以便访问完其左子树后，从栈中取出t，进行其

18、根结点及右子树的访问；对t的左子树和右子树的遍历也是如此。 主要步棸 先将根结点入栈； 将栈顶元素的所有左孩子依次入栈； 出栈一个结点，访问之； 若该结点的右孩子不空，入栈，重复2)，3)步； 如果栈不空，重复3)，4)步，否则结束。,Status InOrderTraverse(BiTree T, Status(* Visit) (TElemType e) /采用二叉链表存储结构，中序遍历二叉树的非递归算法。 InitStack(S); Push(S,T); /根指针进栈 while(!StackEmpty(S) while(GetTop(S,p) /InOrderTraverse,算法6.

19、2,算法6.3,Status InOrderTraverse( BiTree T, Status(* Visit)(TElemType e) InitStack(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-lchild; /根指针进栈，遍历左子树 else /根指针退栈，访问根结点，遍历右子树 Pop(S,p); if(!Visit(p-data) return ERROR; p=p-rchild; /else /while return OK; /InOrderTraverse,6.3.2 线索二叉树,n个结点的二叉链表中含有n+

20、1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为“线索”） 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,线索二叉树结点的结构:,其中，ltag和rtag是增加的两个标志域，用来区分结点的左、右 指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。 0 lchild域指示其左孩子 ltag = 1 lchild域指示其前驱 0 rchild域指示其右孩子 rtag = 1 rchild域指示其后继,中序线

21、索二叉树的表示,注意： 图中的实线表示指针，虚线表示线索。 结点C的左线索为空，表示C是中序序列的开始结点，无前趋； 结点E的右线索为空，表示E是中序序列的终端结点，无后继。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。,6.4 树和森林,树的存储结构 双亲表示法（静态链表存储）：以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在(静态)链表中的位置,双亲表示法举例,#define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; /双亲位置域 PTNode; typ

22、edef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数 PTree;,* 便于涉及双亲的操作； * 求结点的孩子时需要遍历整棵树。,孩子链表存储表示举例,6.4.1 树的存储结构,孩子表示法（链式存储） typedef struct CTNode /孩子结点结构 int child; struct CTNode *next; *ChildPtr; typedef struct /双亲结点结构 TElemType data; ChildPtr firstchild; /孩子链表头指针 CTBox; typedef struct /树结构 CTBox

23、nodesMAX_TREE_SIZE; int n, r; /结点数和根的位置 CTree;,* 便于涉及孩子的操作； * 求结点的双亲时不方便。,6.4.1 树的存储结构,孩子兄弟表示法： 又称二叉树表示法，或二叉链表表示法。记以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。 typedef struct CSNode ELemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,孩子兄弟表示法示例：,*

24、 易于实现找结点孩子的操作；,6.4.2 森林与二叉树的转换,将树转换成二叉树的步骤： 将所有兄弟结点用边连接起来 对每个结点，除了保留与其长子的边外，去掉该结点与其它孩子的边,说明：根结点没有右孩子,6.4.2 森林与二叉树的转换,将森林转换成二叉树的步骤 将森林中的每棵树转换成二叉树 将每个二叉树的根结点看成兄弟用边连起来,6.4.2 森林与二叉树的转换,将二叉树转换成树(森林)的步骤 如果根有右子树，将根的右子树分开，得到几棵二叉树 根据得到的二叉树往回转换。(若结点X是双亲y的左孩子，则把X的右孩子，右孩子的右孩子,都与y用连线连起来，最后去掉所有X到右孩子的连线。),6.4.3 树和

25、森林的遍历,树的两种遍历方法： 先根遍历： 访问树的根结点； 依次先根遍历每棵子树。 R A D E B C F G H K 后根遍历： 依次后根遍历每棵子树； 访问树的根结点。 D E A B G H K F C R,6.4.3 树和森林的遍历,森林的两种遍历方法： 先序遍历森林：若森林非空，则 访问森林中第一棵树的根结点； 先序遍历第一棵树的根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的的森林。 中序遍历森林：若森林非空，则 中序遍历第一棵树的根结点的子树森林； 访问森林中第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的的森林。,先序遍历：ABCDEFGHIJ 中序遍

26、历：BCDAFEHJIG,先序遍历：ABCDEFGHIJ 中序遍历：BCDAFEHJIG,说明,先序遍历森林等同于先序遍历该森林对应的二叉树 中序遍历森林等同于中序遍历该森林对应的二叉树 当用二叉链表作树和森林的存储结构时，树和森林的先序遍历和后序遍历，可用二叉树的先序遍历和中序遍历算法来实现。,6.6 赫夫曼树及其应用,路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。 树的路径长度 ：从树根到每一结点的路径长度之和。 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和

27、。通常记作： n WPL= kk k=1,6.6.1 最优二叉树（赫夫曼树）,定义： 假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i, 则其中：带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。,例：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4,(a) WPL=72+52+22+42 = 36 (b) WPL=73+53+21+42 = 46 (c) WPL=71+52+22+42 = 35,赫夫曼算法的基本思想,根据给定的n个权值1, 2, , n构成n棵二叉树的集合F=T1,T2, ,Tn其中每棵二叉树Ti中只有一个带权为

28、i的根结点,其左右子树均空。 在F中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复上述两个步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。,构造赫夫曼树举例,6.2.2 赫夫曼编码,在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则： 发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样 发送的二进制编码尽可能地短,编码方式,等长编码：将给定字符集C中每个字符的码长相同 【例】设待压缩的数据

29、文件共有100000个字符，这些字符均取自字符集C=a，b，c，d，e，f，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300000位。,编码方式,不等长编码：将频度高的字符编码设置短，将频度低的字符编码设置较长。 根据计算公式： (45*1+13*3+12*3+16*3+9*4+584)*1000=224000，整个文件被编码为224000位，比定长编码方式节约了约25的存储空间。,编码方式,注意： 变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。 【例】设E、T、W分别编码为00、01、0001，则解码时无

30、法确定信息串0001是ET还是W。,编码方式,前缀编码：对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。 可以利用二叉树来设计二进制的前缀编码。 设每种字符在电文中出现的次数为i，其编码长度为li,，电文中只有n个字符，则电文总长为： n WPL= kk。 k=1,前缀编码,如何得到电文总长最短的二进制的前缀编码？ (1)利用字符集中每个字符的使用频率作为权值构造一个赫夫曼树； (2)从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。,假设有一个电文字符集中有8个字符，每个字符的使用频率分

31、别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，现以此为例设计哈夫曼编码。 哈夫曼编码设计过程为： （1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5,29,7,8,14,23,3,11； （2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，,本章小结,掌握树的定义和基本术语，灵活运用二叉树的性质，熟练掌握二叉树的存储结构。 能够快速写出二叉树的先序、中序和后序序列，并熟练掌握与理解二叉树遍历的递归非递归算法。 熟练掌握树的各种存储结构，并能够对森林和二叉树进行相互转换。 会构造赫夫曼树并给出相应的赫夫曼编码。,作业,假设用于通讯的电文仅由8个字符组成（字母表中ah），字母在电文中出现的频率为7，15，3，6，10，27，12，20，画出字母频率作权值的赫夫曼树，并写出赫夫曼编码，并求带权路径长度WPL。,