资源简介

(共48张PPT)
专题四　树及应用
思维导图
归纳提炼
一、树与二叉树
1.树(Tree)的几个基本概念
树是一种非线性的数据结构。
(1)树可以描述为由n(n≥0)个节点构成的一个有限集合以及在该集合上定义的一种节点关系。
(2)节点(Node):集合中的元素称为树的节点,n=0的树称为空树。
根节点:在树形结构中,没有前驱的节点称为根节点(Root),又称为开始节点。
父节点、孩子节点:在树形结构中,对于两个以边直接连接的节点,上端节点称为下端节点的父节点(Parent),下端节点称为上端节点的孩子节点(Child),简称为子节点。
(3)子树:树中某个节点下面所有节点所构成的树称为该节点的子树。
(4)边:树的两个节点之间如果有一条边连接,那么称这两个节点之间存在一条边。
对于一棵具有n个节点的树,它有n-1条边。
(5)度(Degree)
节点的度:树的一个节点所拥有的子树个数称为该节点的度。
树的度:最大的节点的度称为树的度。
节点的度和树的度共同体现了树的宽度。
(6)叶子节点:度为0的节点称为叶子节点(Leaf),又称为终端节点。
(7)树的深度(高度):树中节点的层数(Level)从根开始计算,根的层数为1,其余节点的层数等于其父节点的层数加1。树中节点的最大层数称为树的高度或深度(Depth)。
2.二叉树
(1)二叉树的定义
二叉树是指除根节点外的所有节点可分为两个互不相交的有限集合,分别称为左子树和右子树,左子树和右子树也是二叉树。
二叉树的所有节点的度都小于或等于2,当n=0时,二叉树是一棵空树。
二叉树的子树有左右之分,且左右子树的次序不能颠倒。
(2)二叉树的高度(深度)
二叉树中节点的最大层数称为二叉树的深度或高度。
(3)二叉树的五种形态:
3.特殊的二叉树
(1)满二叉树
符合满二叉树的两个条件为:
①每个节点的度数为2或为0。
②所有叶子节点都在同一层。
(2)完全二叉树
符合完全二叉树的两个条件为:
①至多只有最下面两层中的节点度数小于2。
②最下面一层的叶子节点都依次排列在该层最左边位置。
(3)哈夫曼树
①哈夫曼树又称最优二叉树。
③最优二叉树是指在具有n个带权叶子节点的所有二叉树中,称带权路径长度WPL最小的二叉树。
正确区分满二叉树和完全二叉树的方法:
(1)满二叉树的判断方法:指叶子节点都在最下面一层上,除叶子节点外其他每个节点的度数为2。
(2)完全二叉树的判断方法:可将一棵二叉树先变为满二叉树,然后从上到下,同层从左到右的次序从1开始连续编号,如果能按从大到小的顺序连续删除该满二叉树的若干节点后得到该二叉树,则该二叉树为完全二叉树。
重难点剖析
4.二叉树的性质
(1)二叉树的第k层上最多有2k-1(k≥1)个节点。
(2)深度为k的二叉树最多有(2k-1)(k≥1)个节点。
(3)在任意一棵二叉树中,若度为2的节点数量为n2,叶子节点(度为0的节点)数为n0,则n0=n2+1。
二、二叉树的基本操作
1.建立二叉树的方法
建立二叉树的操作方法为:按照层的顺序进行,先由第1层开始,依次到下一层,在每一层中按照从左到右的顺序创建节点。
2.用数组实现二叉树的创建
(1)完全二叉树
①从二叉树的根节点开始,按从上到下、自左向右的顺序对n个节点进行编号,根节点的编号为0,最后一个节点的编号为n-1。
②然后依次将二叉树的节点用一组连续的数组元素来表示,节点编号与数组的下标一一对应。
(2)非完全二叉树
①对于非完全二叉树,先将它补全为一棵完全二叉树,补上的节点及分支用虚线表示。
②然后按照完全二叉树的方法,将节点存储在数组中。
3.用链表实现二叉树的创建
二叉树用链表实现时,二叉树的节点至少需要3个域:一个数据域和两个指针域。如下图所示:
其中lchild和rchild是指针域,存放指向节点的左孩子节点和右孩子节点的指针,data是数据域。
4.二叉树的遍历
(1)二叉树的遍历是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。
(2)根据访问根节点的先后顺序可以分为:前序遍历、中序遍历和后序遍历。
①前序遍历
前序遍历,也称为先序遍历,前序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问根节点,再访问左子树,最后访问右子树。
②中序遍历
中序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问左子树,再访问根节点,最后访问右子树。
③后序遍历
后序遍历的规则为:若二叉树为空,则空操作返回;否则,先访问左子树,再访问右子树,最后访问根节点。
二叉树的三种遍历是根据访问根节点的先后次序来命名的,前序遍历的访问顺序为根左右(BLR),中序遍历的访问顺序为左根右(LBR),后序遍历的访问顺序为左右根(LRB)。
重难点剖析
三、二叉树的构建与遍历程序实现
1.使用数组(列表)建立二叉树
空树用None表示,非空二叉树用包含三个元素的列表[d,l,r]表示,分别存储着根节点的元素和左右子树,因此二叉树的list实现采用嵌套括号([])的形式。
用数组(列表)构建二叉树的代码如下:
def create_tree(tree,data):
for i in range(len(data)):
　　　depth=0　　　　#程序的第0层相当于树的第1层
if i==0:　　　　　　　　　#根节点
　 tree[ldepth]=data[i]
else:
　#while循环结束表示找到存放数据的节点(索引)位置
　while tree[depth]!=0:
　　 if data[i]>tree[depth]:　#往右寻找
　　　　 depth=depth*2+2　 #父节点的右孩子位置
　　 else:　#往左寻找
　　　　 depth=depth*2+1　#父节点的左孩子位置
tree[depth]=data[i]　#找到数据应存放的节点位置,并存储该节点
2.建立二叉树节点
class Node:　#Node类,用来存储二叉树的节点信息
def_init_(self,data=None,left=None,right=None):
　　　self.data = value　#值
　　　self.left = left　　#左节点
　　　self.right= right　#右节点
　　def print_root(self):
　　　print(self.data)
3.使用链表建立二叉树
def insert(self,data):
　if self.data:　　　　　　　　#如果根节点不存在
　　if data　if self.left:
　 self.left.insert(data)　#递归调用往下一层
　else:
　 self.left=Node(data)　#建立新节点存放数据
　else:　　　　　　　　　　#插入值大于当前节点值
　 if self.right:
　 self.right.insert(data)
　else:
　 selft.right=Node(data)
else:　　　　　　　　　　　#如果根节点不存在
　　self.data=data　　　　#建立根节点
4.遍历二叉树
def preTraverse(root):　　　　#前序遍历
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
def midTraverse(root):　　　#中序遍历
if root==None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
def afterTraverse(root):　　　　#后序遍历
if root==None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
5.给定二叉树的节点信息,输出遍历结果
if_name_ =='_main_':
root=Node('A',Node('B',Node('D'),Node('E')),Node('C',right=Node('F',Node('G'))))
print('前序遍历:')
　preTraverse(root)
　print('中序遍历:')
　midTraverse(root)
　print('后序遍历:')
　afterTraverse(root)
四、数据类型与抽象数据类型
1.数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
2.抽象数据类型是指一个数学模型及定义在该模型上的一组操作,即一个数据对象、数据对象中各数据元素之间的关系以及对数据元素的操作。
【归纳总结】 抽象数据类型与数据结构的关系。
抽象数据类型与数据结构是两个不同的概念,不能混为一谈。具体为:
①数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。
②抽象数据类型是指一个数学模型及定义在该模型上的一组操作,“抽象数据类型”本质是“数据类型”。我们可以用“抽象数据类型”来实现“数据结构”。
3.抽象数据类型(ADT)的描述
(1)定义一个抽象数据类型(ADT),需要清晰地表述出各方面的形式要求(如操作的名字、参数的个数和类型等)和功能要求(希望这个操作完成什么样的计算或产生什么效果等)。
(2)描述抽象数据类型的标准格式:
ADT 抽象数据类型名:
Data
　　数据元素之间逻辑关系的定义
Operation
　　操作1
　　　　　初始条件
　　　　　操作结果描述
　　操作2
　　　　　……
　　操作n
　　　　　……
endADT
(3)线性表抽象数据类型
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)　　　 #删除最后一个元素
del(self,i)　　　　 #删除第i个元素
search(self,elem)　　 #查找元素elem在表中第一次出现的位置
forall(self,op)　　 #对表中的每个元素执行op操作
4.抽象数据类型的作用
(1)程序结构清晰、层次分明,便于程序正确性的证明和复杂性的分析;
(2)因为其模块化的特点,在程序设计中容易纠正,具有很好的可维护性;
(3)由于抽象数据类型的表示和实现都可以封装起来,便于移植和重用;
(4)降低了算法与程序设计的复杂度,有助于在开发过程中少出差错,保证编写的程序有较高的可靠性,有益于算法的优化,提高程序的运行效率。
典型例题
[例1] 在一棵树中,没有前驱节点的节点是(　 　)
A.父节点 B.空节点 C.叶节点 D.根节点
D
解析:在树形结构中,没有前驱的节点称为根节点,也称开始节点,因此答案为D。
[例2] 按照二叉树的定义,具有3个节点的二叉树形态有(　 　)
A.3种 B.5种 C.6种 D.7种
B
解析:在二叉树中,具有3个节点的二叉树有五种,因此,答案为B。具体如下图所示。
[例3] 有如下图所示的一棵树。
该树的度和深度分别为(　 　)
A.3,3 B.4,3 C.3,4 D.8,4
C
解析:本题主要考查的是树的度和深度。树的度是指宽度,树的宽度为最大节点的度,树中节点B的度最大为3,因此树的度为3。树的深度,也称高度,是指树中节点的最大层数,根节点的层数为1,因此树的深度为4,答案为C。
[例4] 若二叉树的根的高度为1,则高度为h的二叉树中节点数最多为(　 　)
A.(2*h-1)个 B.(2h-1)个
C.(2h-1)个 D.(2h+1)个
C
解析:高度为h的满二叉树的节点数最多,节点总数为(2h-1)个,因此答案为C。
[例5] 一棵高度为h的满二叉树,从上到下,同层从左到右的次序从1开始连续编号,若父节点的编号为x(8>x>1),则它的右孩子的节点编号为(　 　)
A.x+1 B.2*x-1 C.2*x D.2*x+1
D
解析:在一棵满二叉树中,若父节点的编号为x,则它的左孩子的节点编号为2*x,右孩子的节点编号为2*x+1,因此答案为D。
[例6] 某二叉树如下图所示,用数组来表示为(　 　)
D
A.
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 a b c d e f g
B.
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 a b c d e f g
C.
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 a b c d e f g
D.
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 a b c d e f g
解析:本题主要考查的是二叉树的数组表示。图中的二叉树为非完全二叉树,先将它补全为一棵完全二叉树,即补全c节点的右孩子节点和d节点的左孩子节点,然后按照完全二叉树的方法来表示,因此答案为D。
[例7] 某二叉树如图所示,若其中的一个叶子节点增加右子树(仅包含节点N),则新二叉树的中序遍历结果不可能是(　 　)
A.CNBDAE B.CBDNAE
C.CBDAEN D.NCBDAE
D
解析:本题主要考查二叉树相关知识。中序遍历的规则是左-根-右,若某个叶子节点仅添加右子树,则N不可能是C的左节点,因此答案为D。
[例8] 在一个三叉树中,度为3的节点数有2个,度为2的节点数有1个,度为1的节点数有2个,则度为0的节点数为　　　　。
6
解析:本题主要考查树的度与边之间的关系。度为0的节点,即为叶子节点。设叶子节点数为n个,该三叉树的总节点数为2+1+2+n,度为3的节点数有2个,则有3*2条边,度为2的节点数有1个,则有1*2条边,度为1的节点数有2个,则有2*1条边,三叉树的总边数=总节点数-1,即有2+1+2+n-1=3*2+1*2+2*1,求得n=6,因此度为0的节点数(叶子节点数)为6个。
[例9] 设有一棵k叉树,其中只有度为0和k两种节点,设n0,nk分别表示度为0和度为k的节点个数,则n0 和nk之间的关系(形式如n0 = 数学表达式,数学表达式仅含nk ,k和数字)为　　　　　　　　。
n0=(k-1) nk+1
解析:本题主要考查k叉树的应用。设k叉树中共有x个节点,则有n0 +nk=x,度为k的节点,表示每个节点均有k个子节点,即有k*nk条边,k叉树的总边数为x-1,即k*nk=x-1,因此可得到n0 +nk= k*nk+1,则n0=(k-1) nk+1。
[例10] 构造最优二叉树(哈夫曼树)。各节点的权依次为1,6,5,3,8,10,构造一棵最优二叉树,画出最优二叉树并计算最优二叉树的带权路径长度WPL。
答案: 最优二叉树为: ,WPL=79
解析:本题主要查考的是最优二叉树。方法为:每次选择2个权最小的节点组成新节节,让新节点加入二叉树中,然后再从中选择2个权最小的节点组成新节点,最终形成一根二叉树,如图所示。根据最优二叉树计算最优二叉树的带权路径长度WPL=(1+3)*4+5*3+(6+8+10)*2=79。
感谢观看

展开更多......

收起↑