数据结构第六章精品文稿.ppt

《数据结构第六章精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章精品文稿.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第六章1第1页，本讲稿共39页主要讨论的问题：树的定义；二叉树的定义与性质主要讨论的问题：树的定义；二叉树的定义与性质,二叉二叉树的遍历树的遍历,线索二叉树线索二叉树,树与森林哈夫曼树及应用树与森林哈夫曼树及应用.6.1树的定义与基本术语树的定义与基本术语.回忆线性结构的特点回忆线性结构的特点.非线性结构的特点非线性结构的特点:至少存在一个数据元素有两个至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数或两个以上的直接前驱（或直接后继）元素的数据结构据结构.人类的族谱、各种社会关系、各类分类编码；人类的族谱、各种社会关系、各类分类编码；操作系统的文件系统、编译程序的语

2、法树；操作系统的文件系统、编译程序的语法树；Internet中的中的DNS（域名系统）（域名系统）-层次结构层次结构第2页，本讲稿共39页.树的定义树的定义(递归定义递归定义)是是n(n0)个结点的有限集合个结点的有限集合T，对于任意一棵，对于任意一棵非空树，它满足：非空树，它满足：(1)有且仅有一个特定的称为根的结点。有且仅有一个特定的称为根的结点。(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互个互不相交的有限集不相交的有限集T1，T2，.，Tm，其中每，其中每个集合本身又是一棵树，称为根的个集合本身又是一棵树，称为根的子树子树。显然：上述树的定义是一个递归定义。显然：上述

3、树的定义是一个递归定义。3第3页，本讲稿共39页.常用术语与基本概念常用术语与基本概念.结点的度、树的度、叶子结点、分支结点结点的度、树的度、叶子结点、分支结点.内部结点、结点的孩子、兄弟、结点的祖先、结点内部结点、结点的孩子、兄弟、结点的祖先、结点的子孙、结点的层次的子孙、结点的层次.树的深度、无序树、有序树、森林树的深度、无序树、有序树、森林.4第4页，本讲稿共39页6.2二叉树二叉树.二叉树的定义二叉树的定义 是由是由n(n=0)个结点的有限集合，它或为空树个结点的有限集合，它或为空树(n=0),或由一个根结点和至多两棵称为根的左子或由一个根结点和至多两棵称为根的左子树和右子树的互不相交

4、的二叉树组成树和右子树的互不相交的二叉树组成.结论结论:二叉树中不存在度大于二叉树中不存在度大于2的结点，并且二的结点，并且二叉树的子树有左子树和右子树之分叉树的子树有左子树和右子树之分.即二叉树是即二叉树是度不大于度不大于2的有序树的有序树.二叉树的五种形态二叉树的五种形态.5第5页，本讲稿共39页.二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结个结(i=1).性质性质2:高度为高度为k的二叉树中至多有的二叉树中至多有2k-1个结点个结点(k=1).性质性质3:在任意一棵二叉树中在任意一棵二叉树中,若其叶子结点数为若其叶子结点数为n0,度为度为

5、2的结点数为的结点数为n2,则有：则有：n0=n2+1.性质4:具有n个结点的完全二叉树的深度为6第6页，本讲稿共39页.满二叉树满二叉树 是指高度为是指高度为k且有且有2k-1个结点的二叉树个结点的二叉树.特点：每一层上都有含有最大结点数特点：每一层上都有含有最大结点数.结点编号结点编号:从上到下从上到下,从左到右按自然数编号从左到右按自然数编号.完全二叉树完全二叉树 高度为高度为k，有，有n个结点的二叉树是一棵完全二叉树，个结点的二叉树是一棵完全二叉树，当且仅当其每个结点都与高度为当且仅当其每个结点都与高度为k的满二叉树中层次编的满二叉树中层次编号号1-n相对应相对应.7第7页，本讲稿共3

6、9页.完全二叉树的特点完全二叉树的特点1)除最后一层外，每一层都取最大结点数，最后一除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层层结点都有集中在该层最左边的若干位置最左边的若干位置.2)叶子结点叶子结点只可能在层次最大的两层出现只可能在层次最大的两层出现.3)对任一结点，若其右分支下的子孙的最大层次为对任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的子孙的最大层次为则其左分支下的子孙的最大层次为k或或k+1.性质4:具有n个结点的完全二叉树的深度为8第8页，本讲稿共39页性质5:对有n个结点的完全二叉树的结点按层序编号(从上到下,自左到右)对任一结点i(1=in)，

7、若若in/2，则，则i无左孩子。无左孩子。(3)若若i(n-1)/2，结点，结点i的或孩子是结点的或孩子是结点2i+1;否则否则(即即2i+1n),结点结点i无右孩。无右孩。9第9页，本讲稿共39页性质5的证明:对i=1,由完全二叉树定义知，其左孩为结2，右孩为结点3；若2n(即2in)，显然结点2不存在，即此时i无左孩；若3n（即2i+1n），则结点3不存在。由此：对于i=1时，上述性质(2),(3)成立。后续证明i1的情形10第10页，本讲稿共39页性质5的证明(续):对i1,将结点i处于某层第一个结点和该层任意一个结点两种情形分别证明:情况一：设结点i为第j层()的第一个结点.j-1 j

8、 j+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1续证i1的情形11第11页，本讲稿共39页性质5的证明（续）：?j-1 j j+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1 由二叉树的性质二可得:第j-1层最后一个结点为2j-1-1;又根据完全二叉树的特点知:第j层的第一个结点应为i=2j-1-1+1=2j-1.又因为i的左孩必为第j+1层的第一个结点，显然其编号应为（2j-1）+1即2j.因为2j=2*2j-1=2i（i为2j-1）续证i1的情形12第12页，本讲稿共39页 j-1 j j+1i=2j-

9、1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1所以当2jn（即2in）时，编号为2j的结点不存在，即：此时i必无左孩(因为最多只有n个结点).同理：结点i如有右孩，则其右孩必为第j+1层上的第二个结点，其编号为2i+1(即2j+1)否则,若2i+1n,则i必无右孩.续证i1的情形二性质5的证明（续）：13第13页，本讲稿共39页 对于第对于第j层的任意第层的任意第k个结点，设上述个结点，设上述(2),(3)的断言成立，即对于任意的的断言成立，即对于任意的i=k,当当2j-1k2j-1时，若结点时，若结点k有左孩，则必为有左孩，则必为2k；若结点；若结点k有右孩，则

10、必为有右孩，则必为2k+1.由此：当由此：当i=k+1(2j-1k2j-1)时，由于时，由于k+1是是k的右兄弟的右兄弟(若堂兄弟若堂兄弟)，若，若k+1有左孩，则有左孩，则应为应为2(k+1)，同理，如，同理，如(k+1)结点有右孩，则应为结点有右孩，则应为2(k+1)+1.而由完全二叉树的特点知，这而由完全二叉树的特点知，这显然是正确的，由此性质五显然是正确的，由此性质五(2),(3)完全成立完全成立.2k 2k+1 2k+2 j-1 j ji=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .k+1 2k+3性质5的证明（续）：14第14页，本讲稿共39页例例1

11、:任意一个有任意一个有n个结点的二叉树，已知它有个结点的二叉树，已知它有m个叶个叶子结点，试证明非叶子结点有子结点，试证明非叶子结点有(m-1)个度为个度为2，其余，其余度为度为1.例例2:已知完全二叉树的第七层有已知完全二叉树的第七层有10个叶子结点，个叶子结点，则整个二叉树的结点数最多是多少则整个二叉树的结点数最多是多少.15第15页，本讲稿共39页.二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构用一组地址连续的存储单元依次自上而下，自用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素左至右存储完全二叉树上的结点元素结论：完全二叉树适合于顺序存储结构结论：完

12、全二叉树适合于顺序存储结构链式存储结构链式存储结构二叉链表表示法二叉链表表示法16第16页，本讲稿共39页例例3.有有n个结点的完全二叉树存放在一维数组个结点的完全二叉树存放在一维数组A1.n中中,试据此建立一棵用二叉链表表示的二叉树试据此建立一棵用二叉链表表示的二叉树,根由根由tree指向指向.分析：分析：1)树的递归定义树的递归定义2)树由几部分组成？树由几部分组成？BiTree Creat(ElemType A,int i)BiTree tree;if(idata=Ai;if (2*in)tree-lchild=null；else tree-lchild=Creat(A,2*i)；if

13、(2*i+1n)tree-rchild=null；else tree-rchild=Creat(A,2*i+1)；return tree；17第17页，本讲稿共39页例例4要求二叉树按要求二叉树按二叉链表二叉链表形式存储，形式存储，(1)写一个建立二叉树的算法写一个建立二叉树的算法.(2)写一个判别给定的二叉树是否是完全二叉树的写一个判别给定的二叉树是否是完全二叉树的算法算法.BiTree Creat()ElemType x；BiTree bt;scanf(“%d”,&x);/本题假定结点数据域为整型本题假定结点数据域为整型if(x=0)bt=null;else if(x0)bt=(BiNod

14、e*)malloc(sizeof(BiNode);bt-data=x;bt-lchild=creat();bt-rchild=creat();else error(“输入错误输入错误”)；return bt;18第18页，本讲稿共39页6.3遍历遍历二叉树和线索二叉树二叉树和线索二叉树.遍历二叉树遍历二叉树按按某条搜索路径某条搜索路径访问二叉树中的每个结点，使访问二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次得每个结点均被访问一次，而且仅被访问一次.先左后右先左后右的搜索路径的搜索路径/先右后左的搜索路径先右后左的搜索路径.先左后右先左后右的搜索路径有三种：先序遍历，中序遍历和

15、的搜索路径有三种：先序遍历，中序遍历和后序遍历后序遍历19第19页，本讲稿共39页.按按先序遍历先序遍历/中序遍历中序遍历/后序遍历把非线性的二叉树后序遍历把非线性的二叉树结构变为了线性结构结构变为了线性结构.那么，变换后的线性结构能否恢复为原来的二叉树？那么，变换后的线性结构能否恢复为原来的二叉树？NO.先序遍历与中序遍历中序遍历和后序遍历能唯一先序遍历与中序遍历中序遍历和后序遍历能唯一确定该二叉树确定该二叉树20第20页，本讲稿共39页例例5.设一棵二叉树的先序遍历序列设一棵二叉树的先序遍历序列:A B D F C E G H,中序遍历序列中序遍历序列:B F D A G E H C，画出

16、这，画出这棵二叉树棵二叉树.二叉树层次遍历二叉树层次遍历(广度优先遍历广度优先遍历).按以上的搜索路径遍历一棵二叉树称之为按以上的搜索路径遍历一棵二叉树称之为二叉树二叉树的深度优先遍历的深度优先遍历搜索路径搜索路径：从二叉树的根开始，自顶向下，同一层：从二叉树的根开始，自顶向下，同一层从左向右从左向右21第21页，本讲稿共39页.二叉树遍历递归算法二叉树遍历递归算法.先序遍历的递归算法先序遍历的递归算法void preorder(BiTree tree)if(tree!=null)visit(tree-data);/访问二叉树的结点访问二叉树的结点 preorder(tree-lchild);

17、preorder(tree-rchild);.同理同理,可写出中序遍历和后序遍历的递归算法可写出中序遍历和后序遍历的递归算法22第22页，本讲稿共39页.二叉树遍历是二叉树应用的基础二叉树遍历是二叉树应用的基础.例例5.二叉树采用链式存储结构二叉树采用链式存储结构,设计递归算法求给设计递归算法求给定二叉树的所有结点数定二叉树的所有结点数.int size(BiTree tree)if(tree=null)return 0;else return size(tree-lchild)+size(tree-rchild)+1;分析分析:二叉树后序遍历的应用二叉树后序遍历的应用.查阅资料查阅资料:求二

18、叉树高度求二叉树高度,度为度为0/1/2结点个数结点个数,判断判断二叉树相等二叉树相等,实现二叉树复制等实现二叉树复制等.(检查检查)23第23页，本讲稿共39页.二叉树遍历非递归算法二叉树遍历非递归算法.先序遍历的非递归算法先序遍历的非递归算法分析：各阶段栈的内容及输出情况分析：各阶段栈的内容及输出情况void preorder(BiTree p)BiTree sMaxsize;int top=0;while(p!=NULL|top)while(p!=NULL)visit(p-data);s+top=p;p=p-lchild;/左孩子进栈左孩子进栈 if(top!=0)p=stop-;p=p

19、-rchild;/右孩子进栈右孩子进栈 24第24页，本讲稿共39页例例6要求二叉树按要求二叉树按二叉链表二叉链表形式存储，形式存储，(1)写一个建立二叉树的算法写一个建立二叉树的算法.(2)写一个判别给定的二叉树是否是完全二叉树的算写一个判别给定的二叉树是否是完全二叉树的算法法.同理同理,模仿上例查阅资料写出中序遍历与后序遍历模仿上例查阅资料写出中序遍历与后序遍历的非递归算法的非递归算法.(检查检查)分析分析:判定是否是完全二叉树，可以使用队列，在遍判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树历中利用完全二叉树“若某结点无左子女就不应有右若某结点无左子女就不应有右子女子女”的原

20、则进行判断。的原则进行判断。25第25页，本讲稿共39页即即:1.当检查当某个接点只有右孩子时当检查当某个接点只有右孩子时,则退出则退出.2.当检查到某个接点只有左孩子或没有孩子结点当检查到某个接点只有左孩子或没有孩子结点,这时这时要保证队列中后面的结点都没有孩子要保证队列中后面的结点都没有孩子,才是完全二叉树才是完全二叉树,所以要设置一个所以要设置一个flag标记标记.一旦发现这种情况，就标记一旦发现这种情况，就标记该结点该结点.根据根据flag判断是否有孩子，如果有，那么就不判断是否有孩子，如果有，那么就不是完全二叉树是完全二叉树;如果队列取空时，没有出现有孩子的结如果队列取空时，没有出现

21、有孩子的结点，那么就是完全二叉树。点，那么就是完全二叉树。26第26页，本讲稿共39页int JudgeComplete(BiTree bt)int tag=0;BiTree p=bt,Q;/根结点不标记根结点不标记 if(p=null)return 1;QueueInit(Q);QueueIn(Q,p);while(!QueueEmpty(Q)p=QueueOut(Q);/出队出队 if(p-lchild&!tag)QueueIn(Q,p-lchild);/左子女入队左子女入队 else if(p-lchild)return 0;/前面有结点无右孩子前面有结点无右孩子 else tag=1;

22、if(p-rchild&!tag)QueueIn(Q,p-rchild);/右子女入队右子女入队 else if(p-rchild)/前面有结点无左孩子前面有结点无左孩子 return 0;else tag=1;return 1;27第27页，本讲稿共39页.线索二叉树线索二叉树.对于任意的二叉树，采用二叉链表表示，有多少对于任意的二叉树，采用二叉链表表示，有多少个空的指针域？个空的指针域？.在遍历二叉树的过程中，利用这些空的指针域将遍历在遍历二叉树的过程中，利用这些空的指针域将遍历产生的线性序列的前驱与后继保留下来产生的线性序列的前驱与后继保留下来.改进二叉链表的结构改进二叉链表的结构28第

23、28页，本讲稿共39页.线索二叉树线索二叉树:加上线索的二叉树加上线索的二叉树.线索：在线索链表中指向结点前驱和后继的指针线索：在线索链表中指向结点前驱和后继的指针.线索化：对二叉树以某种次序遍历使其变为线索二线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叉树的过程.画线索化二叉树画线索化二叉树.二叉树线索化算法二叉树线索化算法29第29页，本讲稿共39页例例6.设有二叉树设有二叉树BT，每个结点包括，每个结点包括ltag，lchild，data，rchild，rtag五个字段，依次为左标志、左儿子，数据，右五个字段，依次为左标志、左儿子，数据，右儿子，右标志给出将二叉树儿子，右标志给

24、出将二叉树BT建成前序（即先序）线索建成前序（即先序）线索二叉树的递归算法二叉树的递归算法.分析：对每个结点线索化时，应知道其前驱和后继的指针值对分析：对每个结点线索化时，应知道其前驱和后继的指针值对于前驱结点的值，可设置一变量于前驱结点的值，可设置一变量pre来记录对于其后继结点的值，来记录对于其后继结点的值，由于是按遍历次序来进行的因此，在线索化该结点时还不知道，由于是按遍历次序来进行的因此，在线索化该结点时还不知道，因而设置了也没有意因而设置了也没有意义义.存在一个问题存在一个问题即：线索化时只能进行前趋线索化，后继线即：线索化时只能进行前趋线索化，后继线索化无法进行索化无法进行.线索化

25、分线索化分2步进行：当步进行：当T为当前结点时，可进行前驱线索化，当为当前结点时，可进行前驱线索化，当的后继为当前结点时再对进行后继线索化的后继为当前结点时再对进行后继线索化30第30页，本讲稿共39页.线索化分2步进行：当T为当前结点时，可进行前驱线索化，当的后继为当前结点时再对进行后继线索化.从另一角度从另一角度:当当T为当前结点时要完成两个操作为当前结点时要完成两个操作:T的前驱线索的前驱线索化化(需要判断条件需要判断条件),T的前驱结点的前驱结点(由由pre指示指示)的后继线索化和的后继线索化和并为并为后继结点的线索化做准备后继结点的线索化做准备.31第31页，本讲稿共39页BiThr

26、Tree pre=null;/设置前驱设置前驱void PreOrderThreat(BiThrTree BT)if(BT!=null)if(BT-lchild=null)BT-ltag=1;BT-lchild=pre;if(pre!=null&pre-rtag=1)pre-rchild=BT;if(BT-rchild=null)BT-rtag=1;pre=BT;/前驱后移前驱后移 if(BT-ltag=0)PreOrderThreat(BT-lchild);PreOrderThreat(BT-rchild)32第32页，本讲稿共39页例例7.设计算法求先序线索二叉树中指针设计算法求先序线索二

27、叉树中指针p所指结点的所指结点的先序后继结点的指针先序后继结点的指针.分析分析:若某一结点若某一结点p有左孩子有左孩子,则该结点的左孩子便是则该结点的左孩子便是p的的后继后继;否则否则,p的的右孩子右孩子便是它的后继便是它的后继.BiTNode*PreNext(BiTNode*p)BiTNode*q;if(p-ltag=0)q=p-lchild;else q=p-rchild;33第33页，本讲稿共39页.树的存储树的存储.双亲表示法双亲表示法(自学自学)，孩子表示法，孩子表示法(自学自学)，孩子兄弟孩子兄弟表示法表示法(二叉树表示法二叉树表示法)6.4树和森林树和森林.孩子兄弟表示法存储示意

28、图孩子兄弟表示法存储示意图.森林与二叉树的转换森林与二叉树的转换.树与二叉树的转换树与二叉树的转换.方法：方法：1)对每个孩子进行自左至右的排序；对每个孩子进行自左至右的排序；2)在兄弟之间加一条虚线；在兄弟之间加一条虚线；3)对每个结点，除了左孩子外，去除其与其余孩子之间的联系；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4)以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转45度度(实线在左，虚线在右实线在左，虚线在右)。34第34页，本讲稿共39页.树由几部分组成？树由几部分组成？.树由根与去除根外的子树森林两部分组成树由根与去除根外的子树森林两部分组成.树的遍历

29、树的遍历.树的遍历：先序遍历与后序遍历树的遍历：先序遍历与后序遍历.森林的遍历森林的遍历.森林由几部分组成？森林由几部分组成？.森林由三部分组成：第一棵树的根，第一树去除根后的森林由三部分组成：第一棵树的根，第一树去除根后的子树森林，其它树组成的森林三部分组成子树森林，其它树组成的森林三部分组成.森林的遍历：先序遍历，中序遍历与后序遍历森林的遍历：先序遍历，中序遍历与后序遍历.二叉树遍历，树遍历，森林的遍历之间的关系二叉树遍历，树遍历，森林的遍历之间的关系35第35页，本讲稿共39页.为什么要建立为什么要建立哈夫曼哈夫曼树？树？.Huffman.Huffman编码编码(前缀编码前缀编码)6.6

30、哈夫曼树及其应用哈夫曼树及其应用.电文：电文：ABACCDA,若若A,B,C,D的编码分别为的编码分别为:00,01,10,11.报文总长度为报文总长度为14,为为00010010101100.接收方接收时二位一分便可译码接收方接收时二位一分便可译码.如何在传送电文时使报文的总长度最小如何在传送电文时使报文的总长度最小?.编码长度应不等长编码长度应不等长.若若A,B,C,D的编码分别为的编码分别为:0,00,1,01.报文总长度报文总长度为为9,为为000011010.接收方接收译码呈现接收方接收译码呈现多样性多样性.一个编码是一个编码是另一个编码另一个编码的前缀的前缀.任一字符的编码任一字符

31、的编码都不是另一编码都不是另一编码的前缀的前缀 36第36页，本讲稿共39页.如何进行如何进行Huffman编码编码?.构造一棵最优二叉树构造一棵最优二叉树(哈夫曼树哈夫曼树).几个名词：路径几个名词：路径,路径长度路径长度,树的路径长度树的路径长度,树的带权树的带权路径长度路径长度.哈夫曼树构造方法哈夫曼树构造方法 (1)给定给定w1,w2,.,wn,构成构成F=T1,T2,.,Tn,每个每个树只有一个根结点树只有一个根结点;(2)选两个根结点最小的树选两个根结点最小的树,作为作为lchild和和rchild,构成构成一新的二叉树一新的二叉树;(3)在在F中删除这两棵树中删除这两棵树,将新二

32、叉树将新二叉树=F (4)重复重复(2)和和(3)37第37页，本讲稿共39页.得到一棵得到一棵Huffman树后树后,约定左支为约定左支为0(1),右支右支为为1(0).编码过程编码过程:从叶子结点出发从叶子结点出发,走一条从叶子到要的走一条从叶子到要的路径路径.译码过程译码过程:需从根出发走一条从根到叶子的路径需从根出发走一条从根到叶子的路径.38第38页，本讲稿共39页例例8.给定集合给定集合15,3,14,2,6,9,16,17(1)用用表示外部结点，用表示外部结点，用表示内部结点，构造表示内部结点，构造相应的相应的huffman树树(2)计算它的带权路径长度计算它的带权路径长度(3)写出它的写出它的huffman编码编码(4)huffman编码常用来译码，请用语言叙述写出其译编码常用来译码，请用语言叙述写出其译码的过程码的过程39第39页，本讲稿共39页