数据结构第六章树课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构第六章树课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第六 课件
- 资源描述:
-
1、6.1 树的类型定义树的类型定义6.2 二叉树二叉树6.3 遍历和线索二叉树遍历和线索二叉树6.4 树和森林树和森林6.5 树与等价问题树与等价问题6.6 哈夫曼树及其应用哈夫曼树及其应用6.1 树的类型定义树的类型定义数据对象数据对象 D:D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集,则称为空树;为空集,则称为空树;否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root,(2)当当n1时,其余结点可分为时,其余结点可分为m(m0)个互个互 不相交的有限集不相交的有限集T1,T2,Tm,其中每一其中每一 棵子集本身又是一棵符合本
2、定义的树,棵子集本身又是一棵符合本定义的树,称为根称为根root的子树。的子树。数据关系数据关系 R:ABCDEFGHIJMKLA()T1T3T2树根例如例如:B(E,F(K,L),C(G),D(H,I,J(M)树具有下面两个特点:树具有下面两个特点:(1 1)树的根结点没有前驱结点,)树的根结点没有前驱结点,除根结点之外的所有结点有且除根结点之外的所有结点有且只有一个前驱结点。只有一个前驱结点。(2 2)树中所有结点可以有零个)树中所有结点可以有零个或多个后继结点。或多个后继结点。()有确定的根;()树根和子树根之间为有向关系。有向树:有向树:有序树:有序树:子树之间存在确定的次序关系。无序
3、树:无序树:子树之间不存在确定的次序关系。基基 本本 术术 语语(从根到结点的)路径路径:结点的层次结点的层次:树的深度:树的深度:由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组 Tree=(root,F)其中:其中:root 被称为根结点,F 被称为子树森林森林:森林:是 m(m0)棵互不相交的树的集合ArootBEFKLCGDHIJMF对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无
4、前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)6.2 二叉树的类型定义二叉树的类型定义 二叉树或为空树空树;或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树的五种基本形态:二叉树的五种基本形态:N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树
5、左右子左右子树均不树均不为空树为空树二叉树二叉树的重要特性的重要特性 性质性质 1:在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法用归纳法证明证明:归纳基归纳基:归纳假设:归纳假设:归纳证明:归纳证明:i=1 层时,只有一个根结点,2i-1=20=1;假设对所有的 j,1 j i,命题成立;二叉树上每个结点至多有两棵子树,则第 i 层的结点数=2i-2 2=2i-1。性质性质 2:深度为 k 的二叉树上至多含 2k-1 个结点(k1)证明:证明:基于上一条性质,深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1 性质性质 3:对任何一棵二叉树,若它含有n0 个
6、叶子结点、n2 个度为 2 的结点,则必存在关系式:n0=n2+1证明:证明:设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2而 b=n-1=n0+n1+n2-1由此,由此,n0=n2+1两类两类特殊特殊的二叉树:的二叉树:满二叉树满二叉树:指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树:树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij 性质性质 4:具有 n 个结点的完全二叉树的深度深度为 log2n +1证明:证明:设设 完全二
7、叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n,则该结点无左孩子,否则,编号为 2i 的结点为其左孩子左孩子结点;(3)若 2i+1n,则该结点无右孩子结点,否则,编号为2i+1 的结点为其右孩子右孩子结点。6.2.4 二叉树的存储二叉树的存储二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序 存储表示存储表示一、一、二叉树的顺序存储表示二叉树的顺序存储表示二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。例如例如:A B D C E F 0 1 2 3 4 5
8、 6 7 8 9 10 11 12 13ABCDEF1401326#define MAXNODE 30/*二叉树的最大结点数*/typedef ELEMTYPE SqBiTreeMAXNODE;/*0号单元存放根结点 */SqBiTree bt;即将bt定义为含有MAXNODE个elemtype类型元素的一维数组。完全二叉树和满二叉树适合顺序存储完全二叉树和满二叉树适合顺序存储二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二叉链表type
9、def struct BiTNode /结点结构结点结构 ElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:rootADEBCF 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:typedef struct TriTNode /结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 struct TriT
10、Node *parent;/双亲指针 TriTNode,*TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:结点结构结点结构:3 3双亲链表双亲链表 data parentABDCEF0B41D42C03E14A-15F36LRTagLRRRL根根 typedef struct BPTNode /结点结构结点结构 TElemType data;int *parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode typedef struct BPTree/树结构树结构 BPTNode no
11、desMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree6.3.1二叉树的遍历二叉树的遍历一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例 顺着某一条搜索路径巡访巡访二叉树中的结点,使得每个结点均被访问一均被访问一次次,而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广,如:输出结点的信息等。“遍历遍历”是任何类型均有的操作,对线性结构而言,只
12、有一条搜索路径(因为每个结点均只有一个后继),故不需要另加讨论。而二叉树是非线性结构,每个结点有两个后继每个结点有两个后继,则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径进行进行遍历的问题。对对“二叉树二叉树”而言,可以有而言,可以有三条搜索路径:三条搜索路径:1先上后下先上后下的按层次遍历;2先左先左(子树)后右后右(子树)的遍历;3先右先右(子树)后左后左(子树)的遍历。abcdefghij二、先左后右的遍历算法二、先左后右的遍历算法先先(根)序的遍历算法中中(根)序的遍历算法后后(根)序的遍历算法根根左子树右子树根根根根根根根根根根 若二叉树为空树,则空操作;否则,(1)访问根结
13、点;(2)先序遍历左子树;(3)先序遍历右子树。先(根)序的遍历算法:先(根)序的遍历算法:ADBCD L RAD L RD L RBDCD L R先序遍历序列:A B D C先序遍历:若二叉树为空树,则空操作;否则,(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。中(根)序的遍历算法:中(根)序的遍历算法:ADBCL D RBL D RL D RADCL D R中序遍历序列:B D A C中序遍历:若二叉树为空树,则空操作;否则,(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。后(根)序的遍历算法:后(根)序的遍历算法:ADBC L R DL R DL R DAD
14、CL R D后序遍历序列:D B C A后序遍历:B-+/a*b-efcd先序遍历:中序遍历:后序遍历:层次遍历:-+a*b-c d/e f-+a*b-cd/ef-+a*b-cd/ef-+a*b-c d/e fABCDEFGHK例如:例如:先序序列:先序序列:中序序列:中序序列:后序序列:后序序列:A B C D E F G H KB D C A E H G K FD C B H K G F E A三、算法的递归描述三、算法的递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点
15、 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 void preorder(JD*bt)if(bt!=NULL)printf(%dt,bt-data);preorder(bt-lchild);preorder(bt-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T
16、 R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列:A B D C中序遍历 void inorder(JD*bt)if(bt!=NULL)inorder(bt-lchild);printf(%dt,bt-data);inorder(bt-rchild);后序遍历 void postorder(JD*bt)if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(%dt,bt-data);中序遍历算法的非递归描述中序遍历算法的非递归描述有两种分析(描述)方法:一、“任务书”分析方法二、“路径”分析方法
17、在写算法之前首先需定义栈的元素类型。typedeftypedef enum Travel,Visit TaskType;/Travel=1:遍历,/Visit=0:访问 typedef structtypedef struct BiTree ptr;/指向根结点的指针 TaskType task;/任务性质 ElemType;“遍历二叉树遍历二叉树”包括三项子任务:“遍历左子树”“遍历右子树”“访问根结点”voidvoid InOrder_iter(BiTree BT)/利用栈实现中序遍历二叉树,T为指向二叉树的根结点的头指针 InitStack(S);e.ptr=BT;e.task=Trav
18、el;ifif(T)Push(S,e);/布置初始任务 whilewhile(!StackEmpty(S)Pop(S,e);if if(e.task=Visit)visit(e.ptr);else else ./while/InOrder_iterifif(!e.ptr)/处理非空树的遍历任务 p=e.ptr;e.ptr=p-rchild;Push(S,e);/最不迫切任务进栈 e.ptr=p;e.task=Visit;Push(S,e);e.ptr=p-lchild;e.task=Travel;Push(S,e);/if void Inorder_I(BiTree T,void(*visit
19、)(TelemType&e)Stack*S;t=GoFarLeft(T,S);/找到最左下的结点 while(t)visit(t-data);if(t-rchild)else if(!StackEmpty(S)t=Pop(S);/退栈 else t=NULL;/栈空表明遍历结束 /while/Inorder_I t=GoFarLeft(t-rchild,S);BiTNode*GoFarLeft(BiTree T,Stack*S)if(!T)return NULL;while(T-lchild)Push(S,T);T=T-lchild;return T;中序的非递归算法:void inorder
20、(JD*bt)int i=0;JD*p,*sM;p=bt;do while(p!=NULL)si+=p;p=p-lchild;if(i0)p=s-i;printf(%dt,p-data);p=p-rchild;while(i0|p!=NULL);非递归算法非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问:访问:C(4)pABCDEFGiP-A访问:访问:C B(5)ABCDEFGiP-AP-D访问:访问:C Bp(6)ABCDEFGiP-AP-DP-E访问:访问:C Bp(7)AB
21、CDEFGiP-AP-D访问:访问:C B Ep(8)ABCDEFGiP-AP-DP-G访问:访问:C B EP=NULL(9)ABCDEFGiP-A访问:访问:C B E G Dp(11)ABCDEFGiP-AP-F访问:访问:C B E G Dp(12)ABCDEFGiP-AP-D访问:访问:C B E Gp(10)ABCDEFGiP-A访问:访问:C B E G D Fp=NULL(13)ABCDEFGi访问:访问:C B E G D F Ap(14)ABCDEFGi访问:访问:C B E G D F Ap=NULL(15)层次遍历 二叉树的层次遍历,是指从二叉树的第二叉树的层次遍历,是
22、指从二叉树的第一层(根结点)开始,从上至下逐层遍一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序历,在同一层中,则按从左到右的顺序对结点逐个访问。对结点逐个访问。按层次遍历所得到的结果序列为:A B C D E F Gabcdefg在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作:(1)访问该元素所指结点;)访问该元素所指结点;(2)若该元素所指结点的左、右孩子)若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队
23、。孩子指针和右孩子指针顺序入队。void LevelOrder(BiTree bt/层次遍历二叉树层次遍历二叉树btBiTree queueMAXNODE;int front,rear;if(bt=NULL)return;Front=-1;rear=0;queuerear=bt;while(front!=rear)front+;Visite(queuefront-data);/*访访问队首结点的数据域问队首结点的数据域*/if(queuefront-rchild!=NULL)/*将队首结点的右孩结点入队将队首结点的右孩结点入队 */rear+;queuerear=queuefront-rchi
24、ld;if(queuefront-lchild!=NULL)/*将队首结点的左孩结点入队将队首结点的左孩结点入队 */rear+;queuerear=queuefront-lchild;四四、遍历算法的应用举例遍历算法的应用举例2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数3、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)4、复制二叉树、复制二叉树(后序遍历后序遍历)5 5、建立二叉树的存储结构、建立二叉树的存储结构1、查询二叉树中某个结点、查询二叉树中某个结点1.在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回 TRUE;2.否则在左子树中进行查找,若找到,则
25、返回 TRUE;3.否则继续在右子树中进行查找,若找到,则返回 TRUE,否则返回 FALSE;Status Preorder(BiTree T,ElemType x,BiTree&p)/若二叉树中存在和若二叉树中存在和 x 相同的元素,则相同的元素,则 p p 指向该结点并返回指向该结点并返回 OK,/否则返回否则返回 FALSE if(T)if(T-data=x)p=T;return OK,/if else return FALSE;else if(Preorder(T-lchild,x,p)return OK;else return(Preorder(T-rchild,x,p);/els
展开阅读全文