第五章树和二叉树ppt课件.ppt
《第五章树和二叉树ppt课件.ppt》由会员分享,可在线阅读,更多相关《第五章树和二叉树ppt课件.ppt(83页珍藏版)》请在三一文库上搜索。
1、张乃孝 算法与数据结构C语言描述,1,第五章 树和二叉树,5.1 树与树林 5.2 树和树林的存储表示 5.3 二 叉 树 5.4 二叉树的存储表示 5.5 哈夫曼算法及其应用,张乃孝 算法与数据结构C语言描述,2,线性结构和非线性结构。 树形结构是以分支关系定义的层次结构,在现实世界中广泛存在,在计算机领域中也有广泛应用。 本章重点讨论二叉树的存储结构及其各种操作,并研究树和森林与二叉树之间的转换关系。,张乃孝 算法与数据结构C语言描述,3,5.1 树与树林,5.1.1 树的定义 5.1.2 基本术语 5.1.3 树林 5.1.4 树的基本运算 5.1.5 树的周游 5.1.6 树林的周游,
2、张乃孝 算法与数据结构C语言描述,4,5.1.1 树的定义,树(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 ,张乃孝 算法与数据结构C语言描述,5,树的表示方法:,(c ) 凹入表,(a)树形表示,A,B,C,D,E,F,I,J,G,H,张乃孝 算法与数据结构C语言描述,6,(A(B(D)(E(I)(J)(C(G)(H) (d) 嵌
3、套括号表示法,C,D,E,I,J,F,G,H,A,B,(b) 文氏图,张乃孝 算法与数据结构C语言描述,7,树(Tree):是包括n(n=0)个结点的有限集T。当T非空时,满足: (1)有且仅有一个特别标出的称为根的 结点; (2)除根结点外,其余结点可分为m(m=0) 个互不相交非空的有限集T1, T2, , Tm, 其中 每一个集合本身又是一棵树,称为根的子树 (Subtree)。,树的递归定义:,空树:不包括任何结点的树。,张乃孝 算法与数据结构C语言描述,8,树结构的特点: (1)树的根的结点没前驱结点,除了根结点之外 的所有结点都有且只有一个前驱结点; (2)树的结点可以有零个或多个
4、后继结点。 树结构描述的是层次关系。,张乃孝 算法与数据结构C语言描述,9,5.1.2 基本术语,(a) 树t (b) 树t 图5.2 树t和树t ,张乃孝 算法与数据结构C语言描述,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并不是兄弟。,张乃孝 算法与数据结构C语言描述,11,祖先,子孙 若结点y在以
5、结点x为根的一个子树(或树)中,且yx,则称x是y的祖先,y是x的子孙。 例如树t中,A是其它各结点的祖先;C是E,H,I,J的祖先。,路径,路径长度 如果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。,张乃孝 算法与数据结构C语言描述,12,结点的层数 规定根的层数为0,其余结点的层数等于其父母结点的层数加1。 例如t中,0层的结点是A,1层的结点有B,C,D,4层的结点是J。,树的
6、深度或高度 树中结点的最大层数称为树的深度或树的高度。 例如树t中,树的深度为4。,张乃孝 算法与数据结构C语言描述,13,结点的度数、树的度数 结点的子女个数叫作结点的度数。树中度数最大的结点的度数叫作树的度数。 例如t中A,C,E,J的度数分别为3,1,2,0;t的度数为3,树叶、分支结点 度数为0的结点称作树叶或终端结点;度数大于0的结点称作分支结点或非终端结点。 例如树t中B,F,G,H,J都是树叶,其余结点都是分支结点。,张乃孝 算法与数据结构C语言描述,14,无序树、有序树 对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。 例如在图5.2中,按无序树的概
7、念t和t是同一棵树,按有序树的概念则是不同的树,本章讨论的树一般是有序树。,结点的次序 在有序树中可以从左到右地规定结点的次序。按从左到右的顺序,我们可以把一个结点的最左边的子结点简称为最左子结点,或直接称为长子,而把长子右边的结点称为次子。 例如在t中结点B是结点A的长子,结点C是结点A的次子,是结点B的兄弟。,张乃孝 算法与数据结构C语言描述,15,树林:是m(m=0)棵互不相交的树所组成的集合。 就逻辑结构而言,任何一棵树是一个二元组Tree=(root,F) , 其中root称为树的根结点,F是m(m0)棵子树构成的树林,F=(T1, T2,Tm), 其中Ti=(ri,Fi)称作根ro
8、ot的第i棵子树;当m0时,在树根和其子树林之间存在下列关系: RF= | i=1,2,m, m0,5.1.3 树林,张乃孝 算法与数据结构C语言描述,16,5.1.4 树的基本运算,创建一棵空树 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 ),张乃孝 算法与数据结
9、构C语言描述,17,求树中某个指定结点的最左子结点,当指定结点为树叶时,返回一特殊值 Node leftChild ( Node p ) 求树中某个指定结点的右兄弟结点,当指定结点没有右兄弟时,返回一特殊值 Node rightSibling ( Node p ) 树的周游:即按某种方式访问树中的所有结点,并使每个结点恰好被访问一次。,张乃孝 算法与数据结构C语言描述,18,5.1.5 树的周游,1. 周游的定义:按某一规律系统的访问树中的所有 结点,并使每个结点恰好被访问一次。 2. 周游的方法:按深度方向和按宽度方向周游。 (I)按深度方向(以右图为例) a. 先根次序 b. 中根次序 c
10、. 后根次序,张乃孝 算法与数据结构C语言描述,19,a. 先根次序 (1,2,3,5,8,9,6,10,4,7) (1) 访问根结点; (2)从左到右按先根次序周游根结点的每棵子树。 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)访问根结点。,张乃孝 算法与数据结构C语言描述,20,(II)按宽度方向周游 先访问层数为0的结点,然后从左到右逐个访 问层数
11、为1的结点,依此类推,直到访问完树中 的全部结点。 层次序列(1,2,3,4,5,6,7,8,9,10),张乃孝 算法与数据结构C语言描述,21,1. 先根(A, B, C, K, D, E, H, F, J, G ) 2. 后根 ( B, K, C, A, H, E, J, F, G, D ),5.1.6 树林的周游,张乃孝 算法与数据结构C语言描述,22,5.2 树和树林的存储表示,5.2.1 树的存储表示 5.2.2 树林的存储表示 5.2.3 树和树林的其它表示法*,张乃孝 算法与数据结构C语言描述,23,5.2.1 树的存储表示,树的父指针表示法 树的子表表示法 树的长子-兄弟表示法
12、,张乃孝 算法与数据结构C语言描述,24,struct ParTreeNode /* 树中结点结构 */ DataType info; /* 结点中的元素 */ int parent; /* 结点的父结点位置 */ ; struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放树中的结点 */ int n; /* 树中结点的个数 */ ; typedef struct ParTree *PParTree;,树的父指针表示法,用一组连续空间存储树的结点,并附设一个指示器指示其双亲结点的位置。结构类型如下:,张乃孝 算法与数据结构C语言描述,25
13、,优点:a)容易找到父结点及其所有的祖先; b)能找到结点的子女和兄弟; 缺点:a)没有表示出结点之间的左右次序; b)找结点的子女和兄弟比较费事。,改进方法: 按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列,如下图:,张乃孝 算法与数据结构C语言描述,26,(a) (b) 图5.5 一棵树的父指针表示,张乃孝 算法与数据结构C语言描述,27,树的子表表示法,结点表中的每一元素又包含一个子表,存放该结点的所有子结点。结点表顺序存放,子表用链接表示。 struct EdgeNode /* 子表中节点的结构 */ int nodeposition; struct EdgeN
14、ode *link; ; struct ChiTreeNode /* 结点表中节点的结构 */ DataType info; struct EdgeNode *children; ;,张乃孝 算法与数据结构C语言描述,28,子表表示的树结构定义如下: struct ChiTree /* 树结构 */ struct ChiTreeNode nodelistMAXNUM; int root; /* 根结点的位置 */ int n; /* 结点的个数 */ typedef struct ChiTree * PChiTree;,求某个结点的最左子女运算很容易实现,找到结点的全部子女也很容易,但求某个结
15、点的父母和右兄弟实现起来比较费事。另一个缺点是:合并若干个子树构成一个新树时(createTree_chitree操作)也要考虑多个结点表的合并问题,由于这些结点表通常用顺序方式表示,所以合并起来比较麻烦。,张乃孝 算法与数据结构C语言描述,29,1,7 ,2,3 ,4,6 ,8,9 ,5,图5.6 树的子表表示法,张乃孝 算法与数据结构C语言描述,30,在树的每个结点中,除信息域外,增加指向其最左子女和右兄弟的指针。 struct CSNode; /* 树中结点结构 */ typedef struct CSNode *PCSNode;/* 结点的指针类型 */ struct CSNode /
16、* 结点结构定义 */ DataType info; /* 结点中的元素 */ PCSNode lchild; /* 结点的最左子女的指针 */ PCSNode rsibling; /* 结点的右兄弟的指针 */ ; typedef struct CSNode *CSTree; /* 树类型定义 */,树的长子-兄弟表示法,张乃孝 算法与数据结构C语言描述,31,t,a ,b, d,c ,e , h, i, j , f, g ,图5.7 树的长子兄弟表法,张乃孝 算法与数据结构C语言描述,32,5.2.2 树林的存储表示,父指针表示法 子表表示法 长子-兄弟表示法,张乃孝 算法与数据结构C语言
17、描述,33,树林的父结点表示方法,张乃孝 算法与数据结构C语言描述,34,1,2 ,3 ,5,9 ,8 ,6 ,7,树林的子表表示法,张乃孝 算法与数据结构C语言描述,35,t,A, B,D ,C ,E, H, J , K ,F, G ,树林的长子兄弟表示法,张乃孝 算法与数据结构C语言描述,36,5.3 二叉树,5.3.1 二叉树的基本概念 5.3.2 二叉树的性质 5.3.3 二叉树的基本运算 5.3.4 二叉树的周游 5.3.5 树、树林与二叉树的转换,张乃孝 算法与数据结构C语言描述,37,二叉树: 它是结点的有限集合,这个集合或者为空集 或者由一个根及两棵不相交的分别称作这个根 的“
18、左子树”和“右子树”的二叉树组成。 它的每一个结点至多有两棵子树,并且子树 有左右之分,不能随意颠倒。,5.3.1 二叉树的基本概念,张乃孝 算法与数据结构C语言描述,38,二叉树的基本形态:,左子树,右子树,右子树,左子树,(1)空二叉树,(2)只有一个根结点,(3)有根结点 和左子树,(4)有根结点 和右子树,(5)有根结点 和左,右子树,张乃孝 算法与数据结构C语言描述,39,二叉树不是树的特殊情形,它们是两个概念。 树和二叉树之间最主要的差别是:二叉树中结点的子树要区分为左子树和右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 (3)和(4)是两棵不同的二叉
19、树,但作为树,它们是相同的。 在二叉树中可定义类似树中的概念。,张乃孝 算法与数据结构C语言描述,40,满二叉树:如果一棵二叉树的任何结点或者是树叶,或者有两棵非空子树,则此二叉树称作“满二叉树”。 完全二叉树:如果一棵二叉树至多只有最下面的两层结点度数可以小于2,并且最下面一层的结点都集中在该层最左边的若干位置上,则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。,张乃孝 算法与数据结构C语言描述,41,满二叉树,完全二叉树,张乃孝 算法与数据结构C语言描述,42,扩充二叉树 : 把原二叉树的结点都变为度数为2的分支结点,也就是说,如果原结点的度数为2,则不变,度数为1,则增加一个分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 二叉 ppt 课件
链接地址:https://www.31doc.com/p-2582860.html