算法与数据结构-C语言描述课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法与数据结构-C语言描述课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 语言 描述 课件
- 资源描述:
-
1、谢谢您的观赏15.1树与树林5.2树和树林的存储表示 5.3二 叉 树 5.4二叉树的存储表示5.5哈夫曼算法及其应用2019-8-29谢谢您的观赏2线性结构和非线性结构。树形结构是以分支关系定义的层次结构,在现实世界中广泛存在,在计算机领域中也有广泛应用。本章重点讨论二叉树的存储结构及其各种操作,并研究树和森林与二叉树之间的转换关系。2019-8-29谢谢您的观赏3 5.1.1 5.1.1 树的定义树的定义 5.1.2 5.1.2 基本术语基本术语 5.1.3 5.1.3 树林树林 5.1.4 5.1.4 树的基本运算树的基本运算 5.1.5 5.1.5 树的周游树的周游 5.1.6 5.1
2、.6 树林的周游树林的周游2019-8-29谢谢您的观赏4树树(Tree)的例子:一个家族。A有子女B,C;B和 C分别有子女D,E,F和G,H;E有 子女I,J。T=(N,R),其中 N=A,B,C,D,E,F,G,H,I,J R=A,B,A,C,B,D,B,E,B,F,C,G,C,H,E,I,E,J 2019-8-29谢谢您的观赏5(c)凹入表(a)树形表示ABCDEFIJGH2019-8-29谢谢您的观赏6(A(B(D)(E(I)(J)(C(G)(H)(d)嵌套括号表示法CDEIJFGHAB(b)文氏图2019-8-29谢谢您的观赏7 树树(Tree):是包括n(n=0)个结点结点的有限
3、集T。当T非空时,满足:(1)有且仅有一个特别标出的称为根根的 结点;(2)除除根结点根结点外,其余结点可分为m(m=0)个互不相交非空的有限集T1,T2,Tm,其中 每一个集合本身又是一棵树,称为根的子树子树 (Subtree)。树的递归定义:树的递归定义:空树空树:不包括任何结点的树。2019-8-29谢谢您的观赏8树结构的特点:树结构的特点:(1)树的根的结点没前驱结点,除了根结点之外 的所有结点都有且只有一个前驱结点;(2)树的结点可以有零个或多个后继结点。树结构描述的是层次关系。2019-8-29谢谢您的观赏9 (a)树t (b)树t 图5.2 树t和树t 2019-8-29谢谢您的
4、观赏10 父结点父结点,子结点,子结点,边边 若结点y是结点x的一棵子树的根,则x称作y的父结父结点点(或父母);y称作x的子结点子结点(或子女);有序对称作从x到y的边边。例如树t中,C是E的父结点,E是C的子结点,是从C到E的边(它对应着图中的有向线段CE)。兄弟结点兄弟结点具有同一父母的结点彼此称作兄弟兄弟。树t中B,C,D互为兄弟,F,G互为兄弟,等等。注意,E和F并不是兄弟。2019-8-29谢谢您的观赏11 祖先祖先,子孙子孙若结点y在以结点x为根的一个子树(或树)中,且yx,则称x是y的祖先祖先,y是x的子孙子孙。例如树t中,A是其它各结点的祖先;C是E,H,I,J的祖先。路径路
5、径,路径长度路径长度如果x是y的一个祖先,又有xx0,x1,xny,满足xi(i0,1,n-1)为xi+1的父结点,则称x0,x1,xn为从x到y的一条路径路径。n称为这条路径的长度路径的长度。路径中相邻的两个结点可以表示成一条边。例如树t中A,C,E,I,J是从A到J的一条路径,其长度为4。2019-8-29谢谢您的观赏12 结点的层数结点的层数规定根的层数根的层数为0,其余结点的层数结点的层数等于其父母结点的层数加1。例如t中,0层的结点是A,1层的结点有B,C,D,4层的结点是J。树的深度或高度树的深度或高度树中结点的最大层数称为树的深度树的深度或树的高度树的高度。例如树t中,树的深度为
6、4。2019-8-29谢谢您的观赏13 结点的度数结点的度数、树的度数树的度数结点的子女个数叫作结点的度数度数。树中度数最大的结点的度数叫作树的度数树的度数。例如t中A,C,E,J的度数分别为3,1,2,0;t的度数为3 树叶树叶、分支结点分支结点度数为0的结点称作树叶树叶或终端结点终端结点;度数大于0的结点称作分支结点分支结点或非终端结点非终端结点。例如树t中B,F,G,H,J都是树叶,其余结点都是分支结点。2019-8-29谢谢您的观赏14 无序树无序树、有序树有序树对子树的次序不加区别的树叫作无序树无序树。对子树之间的次序加以区别的树叫作有序树有序树。例如在图5.2中,按无序树的概念t和
7、t是同一棵树,按有序树的概念则是不同的树,本章讨论的树一般是有序树。结点的次序结点的次序 在有序树中可以从左到右地规定结点的次序次序。按从左到右的顺序,我们可以把一个结点的最左边的子结点简称为最左子结点最左子结点,或直接称为长子长子,而把长子右边的结点称为次子次子。例如在t中结点B是结点A的长子,结点C是结点A的次子,是结点B的兄弟。2019-8-29谢谢您的观赏15树林树林:是m(m=0)棵互不相交的树所组成的集合。就逻辑结构而言,任何一棵树是一个二元组二元组Tree=(root,F),其中root称为树的根结点,F是m(m0)棵子树构成的树林,F=(T1,T2,Tm),其中Ti=(ri,F
8、i)称作根root的第i棵子树;当m0时,在树根和其子树林之间存在下列关系:RF=|i=1,2,m,m02019-8-29谢谢您的观赏16创建一棵空树Tree createTree(Node p,Tree t1,Tree t2,Tree ti)i=1,2,3,判断某棵树是否为空int isNull(Tree t)求树中的根结点,若为空树,则返回一特殊值Node root(Tree t)求某个指定结点的父结点,当指定结点为根时,返回一特殊值Node parent(Node p)2019-8-29谢谢您的观赏17 求树中某个指定结点的最左子结点,当指定结点为树叶时,返回一特殊值Node leftC
9、hild(Node p)求树中某个指定结点的右兄弟结点,当指定结点没有右兄弟时,返回一特殊值Node rightSibling(Node p)树的周游:即按某种方式访问树中的所有结点,并使每个结点恰好被访问一次。2019-8-29谢谢您的观赏185.1.5 5.1.5 树的周游树的周游1.周游的定义:按某一规律系统的访问树中的所有 结点,并使每个结点恰好被访问一次。2.周游的方法:按深度方向和按宽度方向周游。(I)按深度方向(以右图为例)a.先根次序b.中根次序c.后根次序2019-8-29谢谢您的观赏19a.先根次序(1,2,3,5,8,9,6,10,4,7)(1)访问根结点;(2)从左到右
10、按先根次序周游根结点的每棵子树。b.中根次序(2,1,8,5,9,3,10,6,7,4)(1)按中根次序周游根结点的最左子树;(2)访问根结点;(3)从左到右按中根次序周游根结点的其它各子树。c.后根次序(2,8,9,5,10,6,3,7,4,1)(1)从左到右按后根次序周游根结点的每棵子树;(2)访问根结点。2019-8-29谢谢您的观赏20(II)按宽度方向周游 先访问层数为0的结点,然后从左到右逐个访 问层数为1的结点,依此类推,直到访问完树中 的全部结点。层次序列(1,2,3,4,5,6,7,8,9,10)2019-8-29谢谢您的观赏211.先根(A,B,C,K,D,E,H,F,J,
11、G)2.后根 (B,K,C,A,H,E,J,F,G,D)5.1.6 5.1.6 树林的周游树林的周游2019-8-29谢谢您的观赏22 5.2.1 5.2.1 树的存储表示树的存储表示 5.2.2 5.2.2 树林的存储表示树林的存储表示 5.2.3 5.2.3 树和树林的其它表示法树和树林的其它表示法*2019-8-29谢谢您的观赏235.2.1 5.2.1 树的存储表示树的存储表示 树的父指针表示法 树的子表表示法 树的长子-兄弟表示法2019-8-29谢谢您的观赏24struct ParTreeNode/*树中结点结构*/DataTypeinfo;/*结点中的元素*/intparent;
12、/*结点的父结点位置*/;struct ParTree struct ParTreeNode nodelistMAXNUM;/*存放树中的结点*/int n;/*树中结点的个数*/;typedef struct ParTree *PParTree;树的父指针表示法用一组连续空间存储树的结点,并附设一个指示器指示其双亲结点的位置。结构类型如下:2019-8-29谢谢您的观赏25 优点:a)容易找到父结点及其所有的祖先;b)能找到结点的子女和兄弟;缺点:a)没有表示出结点之间的左右次序;b)找结点的子女和兄弟比较费事。改进方法:按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列
13、,如下图:2019-8-29谢谢您的观赏26(a)(b)图5.5 一棵树的父指针表示 2019-8-29谢谢您的观赏27树的子表表示法 结点表中的每一元素又包含一个子表,存放该结点的所有子结点。结点表顺序存放,子表用链接表示。struct EdgeNode /*子表中节点的结构*/intnodeposition;struct EdgeNode*link;struct ChiTreeNode /*结点表中节点的结构*/DataTypeinfo;struct EdgeNode*children;2019-8-29谢谢您的观赏28子表表示的树结构定义如下:struct ChiTree /*树结构*/
14、struct ChiTreeNode nodelistMAXNUM;introot;/*根结点的位置*/intn;/*结点的个数*/typedef struct ChiTree *PChiTree;求某个结点的最左子女运算很容易实现,找到结点的全部子女也很容易,但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是:合并若干个子树构成一个新树时(createTree_chitree操作)也要考虑多个结点表的合并问题,由于这些结点表通常用顺序方式表示,所以合并起来比较麻烦。2019-8-29谢谢您的观赏29 info parent 0 a 1 b 2 d 3 e 4 h 5 i 6 j 7 c
15、 8 f 9 g 1 7 2 3 4 6 8 9 5 图5.6 树的子表表示法2019-8-29谢谢您的观赏30 在树的每个结点中,除信息域外,增加指向其最左子女和右兄弟的指针。struct CSNode;/*树中结点结构*/typedef struct CSNode*PCSNode;/*结点的指针类型*/struct CSNode /*结点结构定义*/DataType info;/*结点中的元素*/PCSNode lchild;/*结点的最左子女的指针*/PCSNode rsibling;/*结点的右兄弟的指针*/;typedef struct CSNode *CSTree;/*树类型定义*
16、/树的长子-兄弟表示法2019-8-29谢谢您的观赏31 t a b d c e h i j f g 图5.7 树的长子兄弟表法2019-8-29谢谢您的观赏325.2.2 5.2.2 树林的存储表示树林的存储表示 父指针表示法 子表表示法 长子-兄弟表示法2019-8-29谢谢您的观赏33树林的父结点表示方法 2019-8-29谢谢您的观赏34 info parent 0 A 1 B 2 C 3 K 4 D 5 E 6 H 7 F 8 J 9 G 1 2 3 5 9 8 6 7 树林的子表表示法2019-8-29谢谢您的观赏35 t A B D C E H J K F G 树林的长子兄弟表示
17、法2019-8-29谢谢您的观赏36 5.3.1 5.3.1 二叉树的基本概念二叉树的基本概念 5.3.2 5.3.2 二叉树的性质二叉树的性质 5.3.3 5.3.3 二叉树的基本运算二叉树的基本运算 5.3.4 5.3.4 二叉树的周游二叉树的周游 5.3.5 5.3.5 树、树林与二叉树的转换树、树林与二叉树的转换2019-8-29谢谢您的观赏37二叉树:它是结点的有限集合,这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树”和“右子树”的二叉树组成。它的每一个结点至多有两棵子树,并且子树有左右之分,不能随意颠倒。5.3.1 5.3.1 二叉树的基本概念二叉树的基本概念
18、2019-8-29谢谢您的观赏38二叉树的基本形态:左子树右子树右子树左子树(1)空二叉树(2)只有一个根结点(3)有根结点 和左子树(4)有根结点 和右子树(5)有根结点 和左,右子树2019-8-29谢谢您的观赏39 二叉树不是树的特殊情形,它们是两个概念。树和二叉树之间最主要的差别是:二叉树中结点的子树要区分为左子树和右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。(3)和(4)是两棵不同的二叉树,但作为树,它们是相同的。在二叉树中可定义类似树中的概念。2019-8-29谢谢您的观赏40 满二叉树满二叉树:如果一棵二叉树的任何结点或者是树叶,或者有两棵非空子树
展开阅读全文