资源简介

(共37张PPT)
4
树
第四章
A
B、C、D
A
B、C
H、I、J
3
2
3
6
7
3
4
树与二叉树
选择性必修1《数据与数据结构》
第四章 树
4.2 二叉树的基本操作
二叉树的建立
如何建立二叉树？
可以用数组或者链表数据结构来实现！
如何存储完全二叉树与非完全二叉树？
按层顺序进行：先由第1层开始，依次到下一层，在每、一层中按照从左到右的顺序创建节点。
二叉树的建立
1.数组实现
编号：从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号。
根节点的编号为0，最后一个节点的编号为n-1
将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。
（1）完全二叉树
二叉树的建立
（1）非完全二叉树
先补全为一棵完全二叉树，补上的节点及分支用虚线表示，如图所示；
然后将补全后的完全二叉树，对n个节点按序编号。
【从根节点开始，从上而下、自左往右，范围[0,n-1]】
依次将原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标—―对应。
如何建立？
二叉树的数组表示
A
C
B
A
C
B
如何用数组存储此二叉树？
数组下标 0 1 2 3 4 5 6
数组元素
A B C
二叉树的建立
虽然，对完全二叉树而言，一维数组的表示方式既简单又节省存储空间。
但对于一般二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。
一个深度为k，只有k个节点的树，需要个节点的存储空间才能表示出来。
2.链表实现
二叉树的建立
二叉链表：
用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。
二叉树可能有两个孩子【左孩子+右孩子】
因此二叉树的节点至少需要3个域:一个数据域和两个指针域。【左指针指向左孩子，右指针指向孩子】
拓展链接
二叉树的list实现
二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。下面介绍用list构造二叉树的方法。
综上，元组特点：
格式: ( , , , )
不可任意更改元素
元组是关系数据库中的基本概念，关系是一张表，表中的每行，即数据库中的每条记录是一个元组，每列就是一个属性，在二维表里，元组也称为行。
元组和列表十分类似，只不过元组和字符串一样是不可变的，即你不能修改元组，元组通过圆括号中用逗号分割的项目定义，元组通常用在使语句或用户定义的函数能够安全地采用一组值的时候，即被使用的元组的值不会改变。
拓展链接
二叉树的list实现
二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。下面介绍用list构造二叉树的方法。
(1）空树用None表示。
(2）非空二叉树用包含三个元素的列表[d,l,r]表示，【d：根节点；l和r两棵子树】
[‘A’,[‘B’,’None’,’None’],
[‘C’,[’D’,[’F’,’None’,’None’],
[’G’,’None’,’None’]],
[’E’,[’H’,’None’,’None’],
[’I’,’None’,’None’]]]]
二叉树的list实现
请将次二叉树用list来表示：
[‘A’,’None’,
[’B’,[’C’,’None’,[’E’,’None’,’None’]],
[’D’,[’F’,’None’,’None’],’None’]]]
二叉树的遍历
图形——直观，但在计算机处理时，需要把非线性结构 线性序列，才能方便程序的实现。
通过二叉树的遍历即可，遍历方式主要分为：前序遍历、中序遍历和后序遍历等。
1.前序遍历
规则:
若二叉树为空，则空操作返回;
否则，根节点 左子树 右子树
前序遍历顺序为:A-B-D-H-E-C-F-I-G-J-K
二叉树的遍历
2.中序遍历
规则:
若二叉树为空，则空操作返回;
否则，左子树 根节点 右子树
中序遍历顺序为:D-H-B-E-A-I-F-C-J-G-K
注意事项！！！
如果选取其中一种遍历策略对二叉树进行遍历，对于二叉树的左右子树，也需遵守该遍历原则，即二叉树的任意一个局部都必须遵守该遍历原则。
3.后序遍历
二叉树的遍历
规则:
若二叉树为空，则空操作返回;
否则，左子树 右子树 根节点。
后序遍历顺序为:H-D-E-B-I-F-J-K-G-C-A
4.层序遍历
二叉树的遍历
A
B
C
D
E
F
G
H
K
J
I
层序遍历顺序为:A-B-C-D-E-F-G-H-I-J-K
二叉树的遍历—— 习题
1.请写出下列二叉树的四种遍历顺序：
二叉树的遍历—— 习题
例2.已知二叉树T的前序遍历序列为A一B一D一G一H一C一E一F，中序遍历序列是G一D一H一B一A一E一C一F,则其后序遍历序列是( )
A.G一H一D一B一E一F一C一A
B.A一B一D一G一H一C一E一F
C.G一D一H一B一A一E一C一F
D.A一B一C一D一E一F一G一H
A
A
B
C
D
G
H
E
F
二叉树的遍历——数学表达式
中序遍历[左—根—右]: 8-(3+2*6)/5+4 【中缀表达式】
后序遍历:8 3 2 6*＋5 / - 4 + 【后缀表达式/逆波兰表达式】
逆波兰式的必要性：为确定运算顺序，括号是必不可少的。
后缀表达式：因为采用了运算符紧跟在两个操作数之后的方法，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为:从左到右依序完成计算。
二叉树
？ 思考与练习
1.写出如图4.2.10所示的二叉树的前序遍历、中序遍历、后序遍历的结果。
前序遍历：A B D E G H C F I J
中序遍历：D B G E H A C I J F
后序遍历：D G H E B J I F C A
二叉树
？ 思考与练习
2.如果某二叉树中有编号为1、2、3、4的四个节点,设计该二叉树，使得其前序遍历结果为1234，后序遍历结果为4321。
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
二叉树
如何确定唯一的二叉树？
前序+中序？中序+后序？前序+后序？
前序遍历【根—左—右】；中序遍历【左—根—右】；后序遍历【左—右—根】
前序+中序，中序+后序，均可确定唯一的一棵二叉树！！！
前序 + 后序
【根—左—右】 【左—右—根】
虽然可确定唯一的根节点，但若左子树/右子树为空时，则无法确定该空子树的位置！！！
选择性必修1《数据与数据结构》
制作者：邹修鸿
第四章 树
4.3 抽象数据类型
二十一世纪外国语学校
抽象数据类型
数据类型是程序设计领域最重要的基本概念之一，它是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
有下列Python程序语句:
a=13 #语句1
b=10 #语句2
c=a+b #语句3
print(c)
语句1、语句2在给变量a和b分别赋值的同时也定义了两个数据类型是整型的变量，而语句3中的“+”操作因为已经在整型类中已经定义，对于编程者来说，此时不必关心“+”操作的含义是如何让计算机理解的。
4.3.1 数据类型与抽象数据类型
抽象数据类型
抽象是指抽取出事物具有的普遍性本质，是对具体事物的一个概括。
抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息，实现抽象化后有利于对事物的抽象，便于实现功能、提高模块独立性。
人们对已有数据类型进行抽象，就有了抽象数据类型。
抽象数据类型(ADT)是指一个数学模型及定义在该模型上的一组操作。
ADT的基本思想是抽象，只需作为一个整体来研究，而与其在计算机内部如何表示和实现无关。
str就是一个抽象数据类型，其操作都有明确的抽象意义，编程者不必受制于操作内部的具体实现技术，在程序设计时可以直接使用。
抽象数据类型
使用Python的内建函数时，编程者只需考虑函数的功能是否满足实际需要，再确保函数调用时的表达式是否符合函数构造的要求，就可以使用此函数，而不需要知道该函数内部实现的任何具体细节。
4.3.2 数据类型的描述
抽象数据类型
描述抽象数据类型描述如下：
ADT 抽象数据类型名：
Data
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作2
……
操作n
……
endADT
！！！
4.3.2 数据类型的描述
线性表抽象数据类型
ADT List：
List(self) #创建一个新表
is_empty(self) #判断self是否为一个空表
len(self) #返回表的长度
prepend(self,elem) #在表头插入元素elem
append(self,elem) #在表尾插入元素elem
insert(self,elem,i) #在表的第i位置插入元素elem
del_first(self) #删除第一个元素
del_last(self) #删除最后一个元素
search(self,elem) #查找元素elem在表中第一次出现的位置
forall(self,op) #对表中的每个元素执行op操作
4.3.3 抽象数据类型的作用
抽象数据类型主要体现了程序设计中问题分解、抽象和信息隐藏的特征。
把问题分解成多个规模较小且容易处理的问题，将每个功能模块作为一个独立单元，隐藏具体的实现过程，通过一次或多次的模块调用来实现整个问题的解决。
好处：
使用抽象数据类型编写出来的程序结构清晰、层次分明，便于程序正确性的证明和复杂性的分析;
因为其模块化的特点，在程序设计中容易纠正，具有很好的可维护性;由于抽象数据类型的表示和实现都可以封装起来，便于移植和重用;
因为算法设计与数据结构设计的隔开，降低了算法和程序设计的复杂度，有助于在开发过程中少出差错，保证编写的程序有较高的可靠性，
同时，允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率。
！！！
拓 展 链 接
简单字符处理ADT
ADT String:
String(self,sseq) #基于字符序列sseq建立一个字符串
is_empty(self) #判断本字符串是否为空
len(self) #取得字符串的长度
char(self,index) #取得字符串中位置index的字符
substr(self,a,b) #取得字符串中[a:b]的子串，左闭右开区间
match(self,string) #查找串string在本字符串中第一次出现的位置
concat(self,string) #获得本字符串与另一个字符串string的拼接串
subst(self,str1,str2) #获得将本字符串中的子串str1替换成str2的结果串
拓 展 链 接
队列抽象数据类型ADT
ADT Queue:
Queue(self) #创建空队列
is_empty(self) #判断队列是否为空，空时返回True，否则返回False
enqueue(self,elem) #将元素elem加入队列，即入队
dequeue(self) #删除队列里最早进的元素并将其返回，即出队
peek(self) #查看队列里最早进入的元素，不删除
拓 展 链 接
二叉树抽象数据类型
ADT BinTree: #一个二叉树抽象数据类型
Bin Tree(self,data,left,right) #构造操作，创建一个新二叉树
is_empty(self) #判断self是否为一个空二叉树
num_nodes(self) #求二叉树的节点个数
data(self) #获得二叉树根节点存储的数据
left(self) #获得二叉树的左子树
right(self) #获得二叉树的右子树
set_left(self,btree) #用btree取代原来的左子树
set_right(self,btree) #用btree取代原来的右子树
traversal(self) #遍历二叉树中各节点数据的迭代器
forall(self,op) #对二叉树中的每个节点的数据中op操作
建树
二叉树的遍历
数据类型与抽象数据类型
抽象数据类型的描述及其作用
课堂小结
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
能从新课导入中的感知建树的方式 5 4 3 2 1 5 4 3 2 1
能理解树的前序遍历 5 4 3 2 1 5 4 3 2 1
能自主学习树的中序遍历和后序遍历，并能模拟出相应的遍历序列 5 4 3 2 1 5 4 3 2 1
能了解抽象数据类型，以及描述某种抽象数据类型和它的作用。 5 4 3 2 1 5 4 3 2 1
课堂作业
1.思考教材“问题与讨论”中的两个问题。
谢谢观看
制作者：XXXXXX

展开更多......

收起↑