ID: 11824251

4.2 二叉树的基本操作 课件-2021-2022学年浙教版(2019)高中信息技术选修1(24张PPT)

日期:2024-12-19 科目:信息技术 类型:高中课件 查看:49次 大小:134404B 来源:二一课件通
预览图 1/9
24张,选修,信息技术,高中,2019,教版
  • cover
(课件网) 4.2 二叉树的基本操作 无论是线性结构还是非线性结构数据,都需要对数据元素逐个进行 组织存储和处理。 二叉树的基本操作,主要包括二叉树的建立和遍历等。 二叉树的建立 1.建立二叉树的操作,可以按照层的顺序进行,先由第1层开始,依次到 下一层,在每一层中按照从左到右的顺序创建节点。 二叉树的建立可以用数组或者链表数据结构来实现。 1.数组实现 用数组来表示二叉树时,分为以下两种情况。 (1)完全二叉树 从二叉树的根节点开始,按从上而下、自左向右的顺序对n个节点进行编号, 根节点的编号为0,最后一个节点的编号为n-1。然后依次将二叉树的节点用 一组连续的数组元素来表示,节点编号与数组的下标一一对应。 如下图中图甲所示的完全二叉树所对应的一维数组表示如图乙所示。 A B C D E 甲 完全二叉树 A B C D E 0 1 2 3 4 5 6 7 乙 数组表示示意图 (2)非完全二叉树 对于非完全二叉树,先将它补充为一棵完全二叉树,补上的节点 及分支用虚线表示,如下图图甲所示的一棵非完全二叉树补全为 图乙所示的完全二叉树。然后将补全后的完全二叉树,从它的根 节点开始,按从上而下、自左往右的顺序对n个节点进行编号, 根节点的编号为0,最后一个节点的编号为n-1。如图丙所示,依 次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示, 节点编号与数组的下标一一对应。 A B C A B C 甲 原二叉树 乙 补全后的二叉树 0 1 2 3 4 5 6 7 丙 数组实现示意图 A B C 对于完全二叉树而言,一维数组的表示方式既简单又节省存储空间。 但对于一般的二叉树来说,采用一维数组表示时,结构虽然简单, 却容易造成存储空间的浪费。 如图甲所示,一个深度为k且只有k个节点的树需要如图乙所示2k-1个节点 的存储空间才能表示出来。 2.链表实现 二叉树也可以采用链表来实现,用任意一组存储单元来存储二叉树的节点, 用指向节点的指针来表示节点之间的关系。 由于二叉树的节点可能有两个孩子,即左孩子和右孩子,因此二叉树的节点 至少需要3个域:一个数据域和两个指针域。两个指针域分别指向节点的左 孩子和右孩子,这两个指针分别称为左指针和右指针,这样得到的链表也 称为二叉链表。 如下图所示的是二叉树及其对应的二叉链表实现示意图。 A B D C E F G A 头指针 B ^ C ^ ^ D ^ E ^ F ^ ^ G ^ 二叉树的list实现 二叉树节点可以看成是一个三元组,元素是左、右子树和本节点 数据。 Python的list可以用于组合这样的三个元素。 下面介绍用list构造二叉树的方法。 (1)空树用None表示。 (2)非空二叉树用包含三个元素的列表[d,l,r]表示,其中:d表示 根节点的元素,l和r是两棵子树,采用与整个二叉树同样结构的list 表示。 这样就可以把二叉树映射到一种分层的list结构,每棵二叉树都有与之对应的(递归结构的)list。 A B C D F G E H I [‘A’,[‘B’,None,None], [‘C’,[‘D’,[‘F’,None,None], [‘G’,None,None]], [‘E’,[‘H’,None,None], [‘I’,None,None]]]] 二叉树的遍历 在完成二叉树的建立操作后,就可以对二叉树的各个节点进行访问,即遍历操作。 二叉树的遍历,是指按照一定的规则和次序访问二叉树中的所有节点,使得每个节点都被访问一次且仅被访问一次。按照不同的遍历方式对节点进行访问,其处理效率不完全相同。 二叉树的遍历方式有很多,主要有前序遍历、中序遍历和后序遍历等。 1.前序遍历 前序遍历的规则是:若二叉树为空,则空操作返回;否则,先访问 根节点,再访问左子树,最后访问右子树。 A B D E H C F I G J K 前序遍历顺序为:A-B-D-H-E-C-F-I-G-J-K 2.中序遍历 中序遍历的规则是:若二叉树为空,则空操作返回;否则,先访问 ... ...

~~ 您好,已阅读到文档的结尾了 ~~