第6章树和二叉树ppt课件.ppt

《第6章树和二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、,第6章 树和二叉树,一、树的定义和基本术语二、二叉树三、二叉树的遍历四、线索二叉树五、树和森林六、赫夫曼树及其应用,主要内容,一、树的定义和基本术语,1、树的定义（教材P118）,树是n（n0）个结点的有限集合。n=0时称为空树。在任意一颗非空树中：（1）有且仅有一个特定的结点被称为根（Root）的结点；（2）当n1时，其余结点被分成m（m0）个互不相交的有限集T1，T2，.，Tm，其中每一集合本身又是一棵树，并且成为根的子树（SubTree）。,树的定义是一个递归,例如:,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大

2、值,度为零的结点,度大于零的结点,2、基本术语（教材P120）,孩子:结点子树的根双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点,结点的层次:,树的深度：,假设某结点在第L层,则其子树的根就在第L+1层,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点，F 被称为子树森林,森林：是m（m0）棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,有序树、无序树：,如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。,线性结构,树型结构,第一个数据元素 (无前

3、驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素(一个前驱、 一个后继),其它数据元素(一个前驱、 多个后继),A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二、二叉树,1、二叉树的定义（教材P121）,二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分,二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,二叉树的五种基本形态：,N,空树,只含

4、根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,2、特殊二叉树,（1）斜树 所有的结点都只有左子树的二叉树叫左斜树；所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。,（2）满二叉树（教材P124） 在一颗二叉树中，如果所有分支都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树成为满二叉树。,（3）完全二叉树 （教材P124） 树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1),3、二叉树的性质 （重点内容，教材P123-124）,性质 2 ：深度为 k

5、的二叉树上至多含 2k-1 个结点（k1）。,注意：性质1、2的区别例如，高度为4的二叉树，第4层的最大结点数为 ，总结点数最多为 。,8,15,性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,性质 4 ：具有 n 个结点的完全二叉树的深度为 log2n +1 。,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；,(2) 若 2in，则该结点无左孩子

6、，否则，编号为 2i 的结点为其左孩子结点；,(3) 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,（1） 顺序存储结构,4、二叉树的存储结构,用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,A,D,E,B,C,F,root,lchild data rchild,结点结构:,-二叉链表,（2）二叉树的链式存储表示,typedef struct BiTNode / 结点结构 TElemType

7、 data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:（教材P127）,A,D,E,B,C,F,root,-三叉链表,parent lchild data rchild,结点结构:,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *

8、TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,三、二叉树的遍历,所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。,1、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。,按层次遍历该二叉树的序列为：,K,A,B,E,C,F,D,G,H,2、按根、左子树和右子树三个部分进行遍历 二叉树的遍历方式存在六种可能： DLR（根左右）、LDR（左根右）、LRD（左右根） DRL（根右左）、RDL（右根左）、RLD（右左根）,如果限定先

9、左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。,A,B,C,D,E,F,G,D L R,T,D L R,D L R,A,B,E,D L R,D L R,DLR,DLR,C,F,D,G,先序遍历结果:,A,B,C,D,E,F,G,T,（1）DLR先序遍历,A,B,C,D,E,F,G,L D R,T,L D R,L D R,A,B,E,L D R,L D R,LDR,LDR,C,F,D,G,中序遍历结果:,B,D,C,A,G,F,E,T,（2）LDR中序遍历,（3）LRD后序遍历,后序遍历结果:,DCBGFEA,练习：分别写出先序、中序、后序遍

10、历的结果。,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,【问题1】若已知二叉树结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？,任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。,回答是肯定的。,【问题2】若已知二叉树结点的先序序列和后序序列，能否确定这棵二叉树？,回答是不能。,想一想，为什么？,3、由遍历序列恢复二叉树,【例】一棵二叉树的前序序列为：ABDEC，中序序列为：DBEAC。请画出这棵树。,练习：已知二叉树的中序和后序序列分别为：DCBEA和

11、DCEBA；请画出这棵树，并写出先序序列。,ABCDE,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,（1）先序的遍历算法： （教材P129，算法6.1）,4、遍历算法,void PreOrderTraverse (BiTree T） if (T=NULL) return; printf(“%c”,T-data); / 访问根结点 PreOrderTraverse(T-lchild); / 遍历左子树 PreOrderTraverse(T-rchild);/ 遍历右子树,若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（

12、3）中序遍历右子树。,（2）中序的遍历算法：,void InOrderTraverse (BiTree T） if (T=NULL) return; InOrderTraverse(T-lchild); / 遍历左子树 printf(“%c”,T-data); / 访问根结点 InOrderTraverse(T-rchild);/ 遍历右子树,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,（2）后序的遍历算法：,void PostOrderTraverse (BiTree T） if (T=NULL) return; PostOrderTrav

13、erse(T-lchild); / 遍历左子树 PostOrderTraverse(T-rchild);/ 遍历右子树 printf(“%c”,T-data); / 访问根结点 ,（1）输入结点值，构造二叉树（教材P131算法6.4）,算法基本思想: 先序(或中序或后序)遍历二叉树，读入一个字符，若读入字符为空，则二叉树为空,若读入字符非空，则生成一个结点。 将算法中“访问结点”的操作改为：生成一个结点，输入结点的值。,5、遍历算法的应用,void CreateBiTree (BiTree *T) char ch; scanf(“%c”, /构造右子树 ,（2）求二叉树的深度(后序遍历),算法

14、基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。 需先分别求得左、右子树的深度，算法中“访问结点”的操作改为：求得左、右子树深度的最大值，然后加1。,int Depth (BiTree T ) int depthleft,depthright; if (T=NULL ) return 0; else depthleft = Depth( T-lchild ); depthright= Depth( T-rchild ); if(depthleft=depthright) return depthleft+1;

15、 else return depthright+1; ,（3）统计二叉树中叶子结点的个数,算法基本思想: 类似求二叉树深度的算法。二叉树的叶子总数等于它的左、右子树叶子数之和。需先判断结点是否为叶子。,int CountLeaf(BiTree T) int lnum,rnum; if(T=NULL) return 0; else if(T-lchild=NULL) ,四、线索二叉树,1、为什么要建线索二叉树？,-n个结点，一共有2n个指针域，有n-1条分支线，也就是说，其实存在2n-（n-1）=n+1个空指针域。,-在二叉链表中，想知道某个结点的前驱和后继必须遍历一次。线索二叉树可以将遍历时结

16、点的线性关系保留下来,指向遍历顺序中的 “前驱”和“后继” 的指针，称作“线索”,A B C D E F G H K, D ,C , B,E ,2、什么叫线索？,包含 “线索” 的存储结构，称作 “线索链表”；加上“线索”的二叉树，称为“线索二叉树”。,线索化（教材P132）线索化的实质（教材P134）,增加两个标志域， Ltag和Rtag,在二叉链表中，若结点有孩子，则让指针指向它的孩子，否则，指向其前驱（后继）。,3、建立线索二叉树的方法,【问题】如何区分指针的是左右孩子的指针还是前驱、后继的线索？,关于LTag和RTag的具体含义：教材P132,typedef struct BiThrN

17、od TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,二叉树的线索存储类型描述：教材P133,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,CBDAFHGIE,例如：,1、树、森林与二叉树的转换,（1）树转换为二叉树,五、树和森林,（2）森林转换为二叉树,（3）二叉树转树,（4）二叉树转森林,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先

18、访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,3、树和森林的遍历,（1）树的遍历,先根遍历时顶点的访问次序：,A B C E F G D,后根遍历时顶点的访问次序：,B E G F C D A,A,B,C,D,E,F,G,B C DE F G H I J K,1森林中第一棵树的根结点；,2森林中第一棵树的子树森林；,3森林中其它树构成的森林。,森林由三部分构成：,（2）森林的遍历,例如：,先序遍历时顶点的访问次序：,B E F C D G H I J K,后序遍历时顶点的访问次序：,E F B C I J K H G D,先序遍历: 依次从左至右对森林中的每一棵树进行先根遍历。中序遍历: 依次从左至右对森林中的每一棵树进行后根遍历。,