《大学计算机基础课件：第4章 数据结构》由会员分享，可在线阅读，更多相关《大学计算机基础课件：第4章 数据结构（86页珍藏版）》请在金锄头文库上搜索。
1、Company LCompany Logo数据结构概述数据结构概述080611080611 班号班号 82519610 82519610 计算机学院办公室电话号码计算机学院办公室电话号码10001 10001 哈工程大学邮编哈工程大学邮编230102780618748 230102780618748 身份证号码身份证号码 v例1：v0806118251961010004230102780618748结论结论1.杂乱的数据不能表达和交流信息杂乱的数据不能表达和交流信息Company Logo的主要内容的主要内容v例例2 电话号码查询系统电话号码查询系统v 设有一个电话号码薄，它记录了设有一个电话
2、号码薄，它记录了n个人的名字和其相应的个人的名字和其相应的电话号码，假定按如下形式安排：电话号码，假定按如下形式安排：v (a(a1 1，b b1 1)(a)(a2 2，b b2 2) )(a(an n，b bn n) )v其中其中ai，bi(i=1，2n) 分别表示某人的名字和对应电话分别表示某人的名字和对应电话号码号码v问题：问题：设计一个算法，当给定任何一个人的名字时，该算设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。有这个人，则该算法也能够报告
3、没有这个人的标志。结论结论2.数据之间是有联系的数据之间是有联系的 这些联系常常影响算法的选择和效率。这些联系常常影响算法的选择和效率。 DS就是要研究数据之间的联系。就是要研究数据之间的联系。Company Logo的主要内容的主要内容v例例3 酒店管理系统中的客房分配问题酒店管理系统中的客房分配问题.v 要求要求: v 出借率机会均等，保持一个平均的磨损率出借率机会均等，保持一个平均的磨损率v 房间分配方法房间分配方法v 采用采用“先退的房间先被起用先退的房间先被起用”的算法的算法v 房间信息组织方法房间信息组织方法:v 所有所有“空空”的同类房间的数据模型应该是一个的同类房间的数据模型应
4、该是一个“队队列列” v 从从“队头队头”分配客房；退掉的空客房排在分配客房；退掉的空客房排在“队尾队尾”。Company Logo职工号职工号姓名姓名性别性别出生年月出生年月职务职务单位单位0101郭建成郭建成男男19521952年年8 8月月处长处长0202肖明肖明男男19581958年年6 6月月科长科长教材科教材科0303晨曦晨曦女女19541954年年1212月月科长科长考务科考务科0404赵丽霞赵丽霞女女19621962年年8 8月月主任主任办公室办公室0505崔小龙崔小龙男男19491949年年8 8月月科员科员教材科教材科0606袁莉袁莉女女19651965年年4 4月月科员科
5、员教材科教材科0707王芳王芳女女19621962年年6 6月月科员科员考务科考务科0808张宏愿张宏愿男男19571957年年3 3月月科员科员考务科考务科0909马明华马明华男男19651965年年1010月月科员科员考务科考务科1010李冰李冰男男19661966年年7 7月月科员科员办公室办公室例例5 表表1-1教务处人事简表教务处人事简表 1010条记录，每条记录有条记录，每条记录有6 6个数据项，每条记录的职工号不同，用职工号来代表整个职工记录。个数据项，每条记录的职工号不同，用职工号来代表整个职工记录。 03080207040609100501按按职职工工年年龄龄从从大大到到小小
6、排排列列03080207040609100501领导和领导和被领导的关系被领导的关系07040810090205060301朋友关系朋友关系线性线性结构结构树型树型结构结构图形图形结构结构Company Logo结论结论数据之间是有结构的数据之间是有结构的例5中数据之间呈线性结构、分层结构（树状结线性结构、分层结构（树状结构）、图形结构构）、图形结构DSDS就是要研究数据之间的各类结构就是要研究数据之间的各类结构就是要研究数据之间的各类结构就是要研究数据之间的各类结构的主要内容的主要内容Company Logo的主要内容的主要内容v例例6：图书目录管理：图书目录管理v书目信息：书目信息：v 书
7、名，作者，登录号，分类，出版年月书名，作者，登录号，分类，出版年月v对图书目录操作：对图书目录操作：v 查找：某书在书库中是否存在？查找：某书在书库中是否存在？v 插入：购进新书时的登录；插入：购进新书时的登录；v 删除：报废或丢失的书，需从目录中去掉；删除：报废或丢失的书，需从目录中去掉；结论结论在某种数据结构上可定义一组运算在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算就是要研究各类数据结构上的各种运算Company Logovv DSDS主要研究内容：主要研究内容：主要研究内容：主要研究内容：v数据的各种数据的各种逻辑结构逻辑结构和和物理结构物理结构，以及它们之，以
8、及它们之间的相应关系间的相应关系v并并并并对每种结构定义相适应的各种运算对每种结构定义相适应的各种运算v设计出相应的算法设计出相应的算法v分析算法的效率分析算法的效率的主要内容的主要内容Company Logo基本术语基本术语数据数据 描述客观事物的数字、描述客观事物的数字、字符以及一切能够输入到字符以及一切能够输入到计算机中，并且能够被计计算机中，并且能够被计算机程序处理的算机程序处理的符号的集符号的集合合结构结构 数据元素之间具有的关数据元素之间具有的关系。系。数据结构数据结构 具有结构的数据元素的具有结构的数据元素的集合。集合。 DS=(D,R)数据元素数据元素 数据整体中相对独立数据整
9、体中相对独立的基本单位的基本单位,数据这个集数据这个集合中的一个一个的个体合中的一个一个的个体 数据元素也称为数据数据元素也称为数据结点。结点。数据对象数据对象 具有相同特性的数据具有相同特性的数据元素的元素的集合。集合。 Company Logo基本术语基本术语1. 数据元素之间的联系称之为数据元素之间的联系称之为 ， 就是具有结构的数据元素的集合。就是具有结构的数据元素的集合。结构结构数据数据结构结构2. 是一个二元组是一个二元组Data-Structure=(D,R)其中，其中，D是数据元素的有限集合，是数据元素的有限集合，R是是D上的关系上的关系的集合。的集合。数据结构数据结构某一数据
10、对象某一数据对象Company Logo基本术语基本术语v例：学生课外活动小组例：学生课外活动小组SA，B，C，D，E，F，GR,ADGBCEFCompany Logo数据的逻辑结构和存储结构数据的逻辑结构和存储结构具有某种逻辑结构具有某种逻辑结构的数据在计算机的数据在计算机存存储器储器中的存储方式中的存储方式(存储映象存储映象)。数据元素之间具有数据元素之间具有的的逻辑关系逻辑关系(结构结构)独立于计算机独立于计算机逻辑结构逻辑结构物理结构物理结构顺序存储结构顺序存储结构链式存储结构链式存储结构Company Logo数据的逻辑结构和存储结构数据的逻辑结构和存储结构线性结构线性结构树型结构树
11、型结构图状结构图状结构逻辑结构逻辑结构纯集合结构纯集合结构03080207040609100501按按职职工工年年龄龄从从大大到到小小排排列列03080207040609100501领导和领导和被领导的关系被领导的关系07040810090205060301朋友关系朋友关系ABCDECompany Logo数据的逻辑结构和存储结构数据的逻辑结构和存储结构顺序存储结构顺序存储结构链式存储结构链式存储结构索引存储结构索引存储结构存储结构存储结构散列存储结构散列存储结构Company Logo线性表及其基本操作线性表及其基本操作学生成绩登记表学生成绩登记表姓姓名名英语英语数据结构数据结构高数高数学号
12、学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬Company Logo线性表及其基本操作线性表及其基本操作职工工资登记表职工工资登记表姓姓名名岗位津贴岗位津贴基本工资基本工资奖金奖金职工号职工号丁一丁一6002782000101李二李二3001901000102张三张三3001861000103孙红孙红5002182000104王冬王冬3001901000105数据元素之间的关系是什么？数据元素之间的关系是什么？Company Logo线性表及其基本操作线性表及其基本操作v线性表：线性表：简称简称表表，是，是n（n0
13、）个具有）个具有相同类型相同类型的的数据元素的数据元素的有限序列有限序列。v线性表的长度：线性表的长度：线性表中数据元素的线性表中数据元素的个数个数。v空表：空表：长度等于长度等于零零的线性表，记为：的线性表，记为：L=( )。v非空表记为非空表记为：L（a1, a2 , , ai-1, ai , , an)线性表的定义线性表的定义其中，其中，ai（1in）称为数据元素；）称为数据元素；下角标下角标i 表示该元素在线性表中的位置或序号表示该元素在线性表中的位置或序号。Company Logo线性表及其基本操作线性表及其基本操作a1a3a4ana2线性表的图形表示线性表的图形表示线性表线性表（a
14、1,a2,ai-1,ai ,an)的图形表示如下：的图形表示如下：几个线性表的例子几个线性表的例子几个线性表的例子几个线性表的例子 数列数列：(25，12，78，34，100，88)1 1 1 1a1a2a3a4a5a6一个数据元素一个数据元素为一个整数为一个整数2 2 2 2字母表字母表：(A，B，C，,Z)a1a2a3a26一个数据元素一个数据元素为一个字母为一个字母Company Logo线性表及其基本操作线性表及其基本操作a1a3a4ana2线性表的特性线性表的特性1.有限性有限性：线性表中数据元素的个数是有穷的。：线性表中数据元素的个数是有穷的。2.相同性相同性：线性表中数据元素的类
15、型是同一的。：线性表中数据元素的类型是同一的。3.顺序性顺序性：线性表中相邻的数据元素：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1,ai)，即，即ai-1是是ai的的前驱前驱，ai是是ai-1的的后继后继；a1无前驱，无前驱，an无后继，其它每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。 Company Logo线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）342367434存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依
16、次依次存储线性表中的数据元素存储线性表中的数据元素Company Logo线性表的顺序存储结构线性表的顺序存储结构如何求得任意元素的存储地址？如何求得任意元素的存储地址？0i-2i-1n-1Max-1 a1 ai-1 ai an空闲空闲长度长度顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai ,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)Company Logo线性表的顺序存储结构线性表的顺序存储结构0i-2i-1n-1Max-1 a1 ai-1 ai an空闲空闲长度长度Loc(ai)=Loc(a1)+(i - -1)c顺序表顺序表cLoc(ai)Loc(a
17、1)一般情况下，一般情况下，(a1，a2，,ai-1，ai ,an)的顺序存储：的顺序存储：Company Logo线性表的顺序存储结构线性表的顺序存储结构33v例：例：（3535，1212，2424，4242），），在在i=2i=2的位置上插入的位置上插入3333。顺序表的插入顺序表的插入 435122442a1a2a3a401234422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件表满：表满：length=MaxSize合理的插入位置：合理的插入位置：0ilength-1（i指的是元素的序号）指的是元素的序号）Company Logo线性表的顺序存储结构线性表的顺
18、序存储结构v例：（例：（35, 33, 12, 24, 42），），删除删除i=2的数据元素。的数据元素。顺序表的删除顺序表的删除535a1a2a3a401234422412334a5122442删除后顺序表的内容删除后顺序表的内容需要考虑的异常情况：需要考虑的异常情况：(1). .是否表空？是否表空？(2). .删除位置是否合适删除位置是否合适？(正常位置：正常位置：0in-1)Company Logo线性表的链式存储结构线性表的链式存储结构存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素的存储单元存放线性表的元素。连续连续不连续不连续零散分布零散分布单链表：单链表：线性表
19、的链接存储结构。线性表的链接存储结构。Company Logo线性表的链式存储结构线性表的链式存储结构0200020803000325存储特点：存储特点：1.逻辑次序和物理次序逻辑次序和物理次序不一定相同。不一定相同。 2.元素之间的逻辑关系元素之间的逻辑关系用用指针指针表示。表示。例：例：(a1, a2 ,a3, a4)的存储示意图的存储示意图单链表单链表 a10200 a20325 a30300 Company Logo线性表的链式存储结构线性表的链式存储结构单链表单链表结点结点数据域数据域指针域指针域单链表是由若干单链表是由若干结点结点构成的；构成的；单链表的结点只有一个指针域。单链表的
20、结点只有一个指针域。data：存储数据元素存储数据元素next：存储指向后继结点的地址存储指向后继结点的地址datanext单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域0200020803000325 a10200 a20325 a30300 Company Logo栈的概念及实现栈的概念及实现栈：栈：限定仅在限定仅在表尾表尾进行插入和删除操作的进行插入和删除操作的线性表线性表。空栈：空栈：不含任何数据元素的栈。不含任何数据元素的栈。（a1,a2,an）栈顶栈顶栈底栈底允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶，另一端称为，另一端称为栈底栈底。 Company L
21、ogo栈的概念及实现栈的概念及实现a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的示意图栈的示意图Company Logo栈的概念及实现栈的概念及实现栈的操作特性：栈的操作特性：后进先出后进先出a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的示意图Company Logo栈的概念及实现栈的概念及实现例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，元素只允
22、许进一次栈，则可能的出栈序列有多少种？则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶情况情况1：出栈序列：出栈序列：c b Company Logo栈的概念及实现栈的概念及实现例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？情况情况2：栈底栈底栈顶栈顶ab栈顶栈顶c出栈序列：出栈序列：b c a注意：注意：栈只是对表插入和删除操作的栈只是对表插入和删除操作的位置位置进行了限进行了限制，并没有限定插入和删除操作进行的制，并没有限定插入和删除操作进行的
23、时间时间。Company Logo栈的概念及实现栈的概念及实现栈的顺序存储结构及实现栈的顺序存储结构及实现顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？ 012345678a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。 Company Logo栈的概念及实现栈的概念及实现出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=- -1 012345678a1topa2topa3top栈满：栈满：top=MAX_SIZE栈的顺序存储结构
24、及实现栈的顺序存储结构及实现Company LogoIII.栈的应用栈的应用子程序的调用和返回子程序的调用和返回函数调用的时候要进行现场保护，调用返回时要恢复现场。函数调用的时候要进行现场保护，调用返回时要恢复现场。当多个过程嵌套调用时，后调用先返回。当多个过程嵌套调用时，后调用先返回。过程之间的信息可以用栈来实现过程之间的信息可以用栈来实现表达式求值表达式求值3*（7-2）Company Logo队列队列队列的逻辑结构队列的逻辑结构空队列：空队列：不含任何数据元素的队列。不含任何数据元素的队列。队列：队列：只允许在只允许在一端一端进行插入操作，而进行插入操作，而另一端另一端进行进行删除操作的
25、线性表。删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。许删除（也称出队）的一端称为队头。 （a1,a2,an）队尾队尾队头队头Company Logo队列的操作特性：队列的操作特性：先进先出先进先出a1a2a3入队入队队尾队尾队头队头出队出队队头队头队列的逻辑结构队列的逻辑结构Company Logo0 1 2 3 4 入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rearfrontrear队列的顺序存储结构及实现队列的顺序存储结构及实现设置设置队
26、头、队尾队头、队尾两个指针两个指针 Company Logo例：例：a1a2依次出队依次出队0 1 2 3 4 入队入队出队出队a1a2a3a4rearfront front front队列的顺序存储结构及实现队列的顺序存储结构及实现Company Logo例：例：a1a2依次出队依次出队特殊线性表特殊线性表特殊线性表特殊线性表队列队列队列队列0 1 2 3 4 入队入队出队出队a3a4rearfront队列的移动有什么特点？队列的移动有什么特点？队列的顺序存储结构及实现队列的顺序存储结构及实现Company Logo例：例：a1a2依次出队依次出队0 1 2 3 4 入队入队出队出队a3a4
27、rearfront整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向移动性单向移动性队列的顺序存储结构及实现队列的顺序存储结构及实现特殊线性表特殊线性表特殊线性表特殊线性表队列队列队列队列Company Logo假溢出：假溢出：当元素被插入到数组中下标最大的位置上之当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。空闲空间，这种现象叫做假溢出。继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear队列的顺
28、序存储结构及实现队列的顺序存储结构及实现特殊线性表特殊线性表特殊线性表特殊线性表队列队列队列队列Company Logo循环队列：循环队列：将存储队列的数组头尾相接。将存储队列的数组头尾相接。如何解决假溢出？如何解决假溢出？0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6队列的顺序存储结构及实现队列的顺序存储结构及实现特殊线性表特殊线性表特殊线性表特殊线性表队列队列队列队列Company Logo队列的应用：队列的应用：分时操作系统：多个用户程序排成队列，分时地循环使用中央分时操作系统：多个用户程序排成队列，分时地循环使用中央处理机处理机内存缓冲区：主机将要输入或
29、输出的信息先送至缓冲区，然后内存缓冲区：主机将要输入或输出的信息先送至缓冲区，然后输入或输出设备从缓冲区中按队列的先进先出原则依次取出数据输入或输出设备从缓冲区中按队列的先进先出原则依次取出数据Company Logo树的基本概念及存储结构树的基本概念及存储结构树的定义树的定义树：树：n（n0）个个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； 当当n1时时，除除根根结结点点之之外外的的其其余余结结点点被被分分成成m（m0）个个互互不不相相交交的的有有限
30、限集集合合T1, ,T2, , , ,Tm，其其中每个集合又是一棵树，并称为这个根结点的中每个集合又是一棵树，并称为这个根结点的子树子树。树的定义是采用递归方法树的定义是采用递归方法Company Logo树的基本概念及存储结构树的基本概念及存储结构A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树Company Logo树的基本概念及存储结构树的基本概念及存储结构(a)一棵树结构一棵树结构(b)一个非树结构一个非树结构(c)一个非树结构一个非树结构树的定义树的定义ACBGFEDHIACBGFDACBGFDECompany Logo树的基本概念及存储结构树
31、的基本概念及存储结构树的应用举例树的应用举例文件结构文件结构MyComputerC:D:E:etcWINDOWSProgramFilesPictureMCompany Logo树的基本概念及存储结构树的基本概念及存储结构树的基本术语树的基本术语结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各结点度的最大值。树中各结点度的最大值。CGBDEFKLHMIJACompany Logo叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFK
32、LHMIJA树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company Logo孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个结点树中某结点子树的根结点称为这个结点的的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双亲结点双亲结点；兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company Logo路径：路径：如果树的结点序列如果树的结点序列n1,n2,nk有如下关系：结有如下关系：结点点ni是是ni+1的双
33、亲（的双亲（1=ik），则把，则把n1,n2,nk称为称为一条由一条由n1至至nk的路径；路径上经过的边的个数称为的路径；路径上经过的边的个数称为路路径长度径长度。CGBDEFKLHMIJA树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company Logo祖先、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结到结点点y，那么那么x就称为就称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。CGBDEFKLHMIJA树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company Logo结点所在层数：结点所在层数：根
34、结点的层数为根结点的层数为1 1；对其余任何结点，；对其余任何结点，若某结点在第若某结点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层。树的深度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company LogoCBDEFKLHJA71234568910层序编号：层序编号：将树中结点按照从上层到下层、同层从左将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从到右的次序依次给他们编以从1 1开始
35、的连续自然数。开始的连续自然数。树的基本术语树的基本术语树的基本概念及存储结构树的基本概念及存储结构Company Logo二叉树及存储结构二叉树及存储结构二叉树的定义二叉树的定义二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和者为空集（称为空二叉树），或者由一个根结点和两棵两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子右子树树的二叉树组成。的二叉树组成。问题转化：将问题转化：将树树转换为转换为二叉树二叉树，从而利用二叉树解，从而利用二叉树解决树的有关问题。决树
36、的有关问题。研究二叉树的意义？研究二叉树的意义？Company Logo二叉树及存储结构二叉树及存储结构二叉树的特点：二叉树的特点：每个结点最多有每个结点最多有两两棵子树；棵子树；二叉树是二叉树是有序有序的，其次序不的，其次序不能任意颠倒能任意颠倒。注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。ABCDEFGABABCompany Logo二叉树及存储结构二叉树及存储结构二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结
37、点同时有左右子树Company Logo二叉树及存储结构二叉树及存储结构具有具有3 3个结点的个结点的树树和具有和具有3 3个结点的个结点的二叉树二叉树的形态的形态v二叉树和树是两种树结构。二叉树和树是两种树结构。Company Logo二叉树及存储结构二叉树及存储结构斜树斜树1. .所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树；2. .所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1.在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深
38、度相同。斜树的结点个数与其深度相同。斜树的特点：斜树的特点：ABCABCCompany Logo二叉树及存储结构二叉树及存储结构满二叉树满二叉树在一棵二叉树中，如果所在一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点：1.叶子只能出现在最下一层；叶子只能出现在最下一层；2.只有度为只有度为0和度为和度为2的结点。的结点。特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJKLM NO1112 13 14 Company Logo二叉树及存储结构二叉树及存储结构满二叉
39、树满二叉树不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多A1523467BCDEFGLM89特殊的二叉树特殊的二叉树Company Logo二叉树及存储结构二叉树及存储结构完全二叉树完全二叉树对一棵具有对一棵具有n个结点的个结点的二叉树按层序编号，如果二叉树按层序编号，如果编号为编号为i（1in）的结点的结点与同样深度的满二叉树中与同样深度的满二叉
40、树中编号为编号为i的结点在二叉树的结点在二叉树中的位置完全相同。中的位置完全相同。特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJKLM NO1112 13 14 15A15234678910BCDEFGHIJCompany Logo二叉树及存储结构二叉树及存储结构在满二叉树中，从最后在满二叉树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树。棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树
41、中的结点与满二叉树中的结点10不是同一个结点不是同一个结点特殊的二叉树特殊的二叉树Company Logo二叉树及存储结构二叉树及存储结构1.叶子结点只能出现在叶子结点只能出现在最下两最下两层层，且最下层的叶子结点都集，且最下层的叶子结点都集中在二叉树的中在二叉树的左部左部；2.完全二叉树中如果有度为完全二叉树中如果有度为1的结点的结点，只可能有，只可能有一个一个，且该，且该结结点只有点只有左孩子左孩子。3.深度为深度为k的完全二叉树在的完全二叉树在k-1层上一定是层上一定是满满二叉树。二叉树。完全二叉树的特点完全二叉树的特点特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJC
42、ompany Logo二叉树及存储结构二叉树及存储结构二叉树的基本性质二叉树的基本性质 性质性质5-1二叉树的第二叉树的第i层上最多有层上最多有2i- -1个结点（个结点（i1）。）。证明：证明： 当当i=1时，时，2i-1=20=1，结论正确；，结论正确； 假设第假设第i-1层上的结点最多为层上的结点最多为2i-2； 那么第那么第i层上的结点最多为层上的结点最多为2*2i-2=2i-1，结论正确。，结论正确。 1 2 4 8 16 Company Logo性质性质5-2一棵深度为一棵深度为k的二叉树中，最多有的二叉树中，最多有2k- -1个结点，最少个结点，最少有有k个结点。个结点。证明：证
43、明： 按每一层最多的结点数求和，便是树的最多的结点数。按每一层最多的结点数求和，便是树的最多的结点数。 2 20 + 2 + 21 + + + 2 + 2k-1 = 2 = 2k-1-1深度为深度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树，深度为深度为k且具有且具有k个结点的二叉树个结点的二叉树不一定不一定是斜树。是斜树。二叉树的基本性质二叉树的基本性质 二叉树及存储结构二叉树及存储结构Company Logo性质性质5-3在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的的结点数为结点数为n2，则有则有:n0n21。证明
44、证明:设结点总数为设结点总数为n，度为，度为1的结点数为的结点数为n1，则有则有n=n0+n1+n2(4-1)由于二叉树中除根之外的每个结点都带有一个向上的由于二叉树中除根之外的每个结点都带有一个向上的分支，设分支总数为分支，设分支总数为e，则，则e=n-1(4-2)由于这些分支不是度为的结点射出的分支，就是度由于这些分支不是度为的结点射出的分支，就是度为的结点射出的分支，则为的结点射出的分支，则e=1*n1+2*n2(4-3)由式由式(4-2)和式和式(4-3)，得，得n-1=n1+2*n2(4-4)由式由式(4-1)和式和式(4-4)，得，得1=n0-n2即即n0n2+1二叉树的基本性质二
45、叉树的基本性质 二叉树及存储结构二叉树及存储结构Company Logo性质性质5-4具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n +1。证明：证明：设具有证明：证明：设具有n个结点的完全二叉树的深度个结点的完全二叉树的深度为为k，则由性质，则由性质2。可知。可知2k-1-1n2k-1则则2k-1n2k取以取以2为底的对数，得为底的对数，得k-1log2nk因为因为log2n处于两个连续的整数处于两个连续的整数k-1和和k之间，所以之间，所以k-1=log2n即即k=log2n+1完全二叉树的基本性质完全二叉树的基本性质 二叉树及存储结构二叉树及存储结构Compan
46、y Logo性质性质5-5对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开始按层开始按层序编号，则对于任意的序号为序编号，则对于任意的序号为i（1in）的结点（简称为结的结点（简称为结点点i），），有：有：(1)如果如果i1，则结点则结点i的双亲结点的序号为的双亲结点的序号为 i/2；如果如果i1，则结点则结点i是根结点，无双亲结点。是根结点，无双亲结点。(2)如果如果2in，则结点则结点i的左孩子的序号为的左孩子的序号为2i；如果如果2in，则结点则结点i无左孩子。无左孩子。(3)如果如果2i1n，则结点则结点i的右孩子的序号为的右孩子的序号为2i1；如果如果2i1n，
47、则结点则结点i无右孩子。无右孩子。完全二叉树的基本性质完全二叉树的基本性质 二叉树及存储结构二叉树及存储结构Company Logo18910456723对一棵具有对一棵具有n个结点的完全二叉个结点的完全二叉树中从树中从1开始按层序编号，则开始按层序编号，则l结点结点i的双亲结点为的双亲结点为 i/2；l结点结点i的左孩子为的左孩子为2i；l结点结点i的右孩子为的右孩子为2i1。性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。完全二叉树的基本性质完全二叉树的基本性质 二叉树及存储结构二叉树及存储结构Compa
48、ny Logo二叉树及存储结构二叉树及存储结构顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一维数组存储二叉树中的结二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的点，并且结点的存储位存储位置置（下标）应能体现结点之间的（下标）应能体现结点之间的逻逻辑关系辑关系父子关系。父子关系。如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以唯一地反映出中结点的序号可以唯一地反映出结点之间的逻辑关系结点之间的逻辑关系。Company Logo二叉树及存储结构二叉树及存储结构ABCDEFGHIJ数
49、组下标数组下标12345678910完完全全二二叉叉树树的的顺顺序序存存储储以编以编号号为下为下标标A15234678910BCDEFGHIJCompany Logo二叉树及存储结构二叉树及存储结构二二叉叉树树的的顺顺序序存存储储ABC DE F G数组下标数组下标12345678910111213以编以编号号为下为下标标AFGEBCDCompany Logo二叉树及存储结构二叉树及存储结构一棵斜树的顺序存储会怎样呢？一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需分配个结点需分配2k1个存储单元。个存储单元。一棵二叉树改造后成完全二一棵二叉树改造后成完全二叉树形态，叉
50、树形态，需增加很多空结需增加很多空结点点，造成存储，造成存储空间空间的的浪费浪费。二叉树的顺序存储结构一般仅适合存储二叉树的顺序存储结构一般仅适合存储完全完全二叉树二叉树ABC137D15ABCDCompany Logo二叉树及存储结构二叉树及存储结构二叉链表二叉链表基本思想：基本思想：令二叉树的每个结点对应一个链表结点，链表结点令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信除了存放与二叉树结点有关的数据信息外，还要设置指示左右息外，还要设置指示左右孩子的指针。孩子的指针。结点结构：结点结构：lchilddatarchild其中，其中，data：数据域，存放该结点
51、的数据信息；数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。右指针域，存放指向右孩子的指针。Company Logo二叉树及存储结构二叉树及存储结构二叉链表二叉链表具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？具有具有n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针。个空指针。AACDGFEHBBCDEFGHCompany Logo二叉树的遍历及线索二叉树二叉树的遍历及线索二叉树遍历二叉树遍历二叉树: 按照某种搜索路径巡访二叉树中每个结点，使
52、得每个结点按照某种搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次。访问的含义是对结点作做某种处理，如输均被访问一次。访问的含义是对结点作做某种处理，如输出结点信息。出结点信息。遍历方式遍历方式 先序遍历先序遍历: 访问根结点访问根结点;先序遍历左子树先序遍历左子树;先序遍历右子树先序遍历右子树. 中序遍历中序遍历: 中序遍历左子树中序遍历左子树;访问根结点访问根结点;中序遍历右子树中序遍历右子树. 后序遍历后序遍历: 后序遍历左子树后序遍历左子树;后序遍历右子树后序遍历右子树;访问根结点访问根结点. 层序遍历：层序遍历：Company Logo二叉树及存储结构二叉树及存储结构前序遍历前
53、序遍历递归算法递归算法AGBCDFE执行轨迹执行轨迹先序遍历二叉树操作定义为：先序遍历二叉树操作定义为：若二叉树非空操作如下：若二叉树非空操作如下：1. 访问根结点；访问根结点；2. 先序遍历左子树；先序遍历左子树；3. 先序遍历右子树。先序遍历右子树。Company Logo二叉树的遍历ABCEFD先序遍历先序遍历若二叉树非空，则依次执行下列若二叉树非空，则依次执行下列操作：操作：a、访问根结点；、访问根结点；b、前序遍历左子树；、前序遍历左子树； c、前序遍历右子树。、前序遍历右子树。 在先序遍历中按访问的次序排在先序遍历中按访问的次序排 列结点序列称为先序序列。以左列结点序列称为先序序列
54、。以左图为例，其先序序列为：图为例，其先序序列为：A B D F C ECompany Logo二叉树的遍历ABCEFDv中序遍历中序遍历若二叉树非空：若二叉树非空：a、中序遍历左子树、中序遍历左子树 b、访问根结点、访问根结点 c、中序遍历右子树、中序遍历右子树v在中序遍历中按访问的次序在中序遍历中按访问的次序排列结点序列称为中序序列。排列结点序列称为中序序列。以左图为例，其中序序列为：以左图为例，其中序序列为：B F D A C ECompany Logo二叉树的遍历二叉树的遍历ABCEFDv后序遍历后序遍历 若二叉树非空：若二叉树非空： a、后序遍历左子树、后序遍历左子树 b、后序遍历右
55、子树、后序遍历右子树 c、访问根结点、访问根结点 在后序遍历中按访问的次在后序遍历中按访问的次序排列结点序列称为后序序排列结点序列称为后序序列。以左图为例，其后序列。以左图为例，其后序序列为：序序列为： F D B E C ACompany Logo二叉树的遍历ABEDCFGH先序遍历:A B D E C F G H中序遍历: D B E A G H F C 后序遍历: D E B H G F C A Company Logo1、依次输入、依次输入ABCDEF六个字符，利用一个栈和一个队列做缓六个字符，利用一个栈和一个队列做缓冲，如何进行操作才可以得到冲，如何进行操作才可以得到ABCFED的输
56、出顺序？的输出顺序？将将ABC送入队列，然后输出，得送入队列，然后输出，得ABC将将DEF送入栈，然后输出，得送入栈，然后输出，得FED2、对图中的二叉树，分别写出前序遍历、中序遍历和后序遍历的、对图中的二叉树，分别写出前序遍历、中序遍历和后序遍历的节点顺序？节点顺序？N1N2N3N4N5N6N7N8N9前序：前序：124785936中序：中序：748259136后序：后序：Company Logo3、已知某二叉树的前序遍历序列是、已知某二叉树的前序遍历序列是ABDC，中序序列是，中序序列是DBAC，则，则后序遍历是什么？后序遍历是什么？ABCDDBCA4、有三个节点构成的二叉树，共有多少种不同的形态？、有三个节点构成的二叉树，共有多少种不同的形态？五种五种Company Logo
