数据结构 教学课件 ppt 作者 晋良颖 5
62页1、第 五 章 树与二叉树 51树的定义及基本术语 511树的定义,退出,图5.1 树的示例,图5.2,512基本术语 1、根 2、度(结点的度和树的度) 3、叶 4、分枝结点 5、双亲、子女、祖先、子孙 6、兄弟、堂兄弟 7、结点的层次、树的深度(高度) 8、有序树、无序树 9、森林,12二叉树 521二叉树的性质 (1) 在二叉树的第i上至多有2i-1个结点(i=1) (2) 深度为k的二叉树至多有2k-1个结点。 (3) 设任何一棵二叉树中,叶结点数为n0,度为1 的结点数为n1,度为2的结点数为n2,则有:n0=n2+1 (4) 具有n个结点的完全二叉树其深度为:k= log2n+1 (应改为底函数),(5)对于具有n个结点的完全二叉树有如下特点: i=1则是树根,若i1则它的双亲为i/2(取整); 如果2in 则 i没有左子女,否则它的左子女为2i; 如果2i+1n 则 i没有右子女,否则它的右子女为2i+1;,图5-3,522 二叉树的存储结构 1、顺序存储 顺序存储的二叉树的定义如下: #define N 50 /*树结点的最大个数*/ typedef elemtype SQ
2、TREEN;,图5-4,1、链式存储,图5-5,图 5-6,一般二叉树的两种结点类型定义如下: typedef struct treenode elemtype data; /*树中结点的数据值。可根据需要替换元素类型elemtype*/ struct treenode *lchild, *rchild; /*指向树结点的左、右孩子指针*/ TREENODE, * TREENODEPTR ; /*二叉树的二叉链表结点类型*/,typedef struct treenode elemtype data; /*树中结点的数据值。可根据需要替换元素类型elemtype*/ struct treenode *lchild, *rchild ,*parent; /*指向树结点的左、右孩子指针和双亲指针*/ PTREENODE, *PTREENODEPTR; /*二叉树的三叉链表结点和指针类型*/,1、按层次顺序为输入,建立二叉树的三叉链表的算法,图 5-7,(1)、输入按层次顺序并用0表示有关的指针为空。输入为: 8,5,10,1,6,9,11,0,3,0,7,0,0,0,0,2,4,0,0,0
3、,0,0,0。 #define N 50 /*定义树中结点数目的上限,做队容量,设树中实际结点数为n*/ 算法 5.1 如书第110页所示,(2)、以层次顺序输入结点值,但不输入非0值,每输入一个结点值时,同时输入它按完全树编号方法所编的序号。,表5.1,算法 5.2 如书第111页所示,图 5-8 其广义表表示为:A(B(C(,D(E,F),G(,H),I(J,K) 算法 5.3 如书第113页所示,53 遍历二叉树 如果以L代表左子树、D代表根,R代表右子树,则二叉树的遍历方案可以有: DLR、LDR、LRD和DRL、RDL、RLD六种 对于根来说,遍历只有三种情况,即前、中、后。若规定遍历子树的顺序为自左向右,则只有DLR、LDR、LRD三种。 531二叉树的遍历算法 1、 二叉树的LDR、DLR和LRD三种遍历的递归算法 (1)、中序遍历 算法 5.4 如书第114页所示,(2)、前序遍历 算法 5.5 如书第115页所示 (3)、后序遍历 算法 5.6 如书第115页所示 例如,对图5-7(a)所示的二叉树,三种遍历的结果为: 中序:1,2,3,4,5,6,7,8,9,10,
《数据结构 教学课件 ppt 作者 晋良颖 5》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 晋良颖 5》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页