第2节二叉树的基本操作（1课时）第4章树浙教版（2019）选修一

二叉树的建立01二叉树的遍历02二叉树遍历的Python程序实现03

掌握二叉树的两种建立方式。01了解抽象数据类型的概念、抽象数据类型的描述、抽象数据类型的作用。03熟练掌握二叉树的三种遍历方式。02

PART01二叉树的建立

新课导入树？完全二叉树满二叉树

新课导入想想一对于图中的两棵二叉树(一张满二叉树，一张完全二叉树)，如何组织、存储节点信息?问题可采用数组形式和链表形式存储节点信息。也可采用数组形式和链表形式，与学生一起模拟建树过程。办法

二叉树的建立一1从二叉树的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，根节点的编号为0，最后一个节点的编号为n–1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。完全二叉树完全二叉树数组表示示意图完全二叉树的数组表示数组实现

二叉树的建立一对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示。然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左往右的顺序对n个节点进行编号，第四章根节点的编号为0，最后一个节点的编号为n–1。非完全二叉树甲原二叉树非完全二叉树的数组表示甲所示的一棵非完全二叉树补全为乙所示的完全二叉树乙补全后的二叉树丙数组实现示意图依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标一一对应。

二叉树的建立一甲原二叉树乙补全后的二叉树丙数组实现示意图对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二叉树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如上图甲所示，一个深度为k且只有k个节点的树需要如上图乙所示2k–1个节点的存储空间才能表示出来。非完全二叉树的数组表示

二叉树的建立一探讨与讨论1.用数组表示的二叉树的方式更适合完全二叉树还是非完全二叉树?为什么?对于完全二叉树而言，一维数组的表示方式既简单又节省存储空间。但对于一般的二又树来说，采用一维数组表示时，结构虽然简单，却容易造成存储空间的浪费。如图4.2.2甲所示，一个深度为k且只有k个节点的树需要如乙图所示2k1个节点的存储空间才能表示出来。

二叉树的建立一探讨与讨论1.某二叉树如下图所示，用数组来表示为（）D

二叉树的建立一2链表实现二叉树也可以采用链表来实现，用任意一组存储单元来存储二叉树的节点，用指向节点的指针来表示节点之间的关系。二叉树的节点可能有两个孩子右孩子左孩子此二叉树的节点至少需要3个域：一个数据域和两个指针域。

二叉树的建立一链表实现两个指针域分别指向节点的左孩子和右孩子，这两个指针分别称为左指针和右指针，这样得到的链表也称为二叉链表。二叉树及其对应的二叉链表实现示意图

二叉树的建立一拓展链接二叉树的list实现二叉树节点可以看成一个三元组，元素是左、右子树和本节点数据。Python的list可以用于组合这样的三个元素。下面介绍用list构造二叉树的方法。（1）空树用None表示。（2）非空二叉树用包含三个元素的列表[d,l,r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。构更加复杂。二叉树

二叉树的建立一只需知道数据之间相互链接的顺序探讨与讨论1.某二叉树对应的一维数组表示如图所示:下列关于该二叉树的说法正确的是()A.该二叉树的度为3B.该二叉树有2个叶子节点C.该二叉树是一棵完全二叉树D.该二叉树前序遍历结果为ABCDE123456ABCD?EB

二叉树的建立一只需知道数据之间相互链接的顺序探讨与讨论2.已知一棵完全二叉树共有200个节点，下列说法正确的是()A.该完全二叉树的高度为7B.该完全二叉树有99个叶子节点C.该完全二叉树有100个度为2的节点D.该完全二叉树有1个度为1的节点D

二叉树的遍历二概念①前序遍历（根-左-右）②中序遍历（左-根-右）③后序遍历（左-右-根）按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。遍历方式④层序遍历

二叉树的遍历二前序遍历根左右※规则：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。※从右图中得到的前序遍历顺序为：A-B-D-H-E-C-F-I-G-J-K。前序遍历的过程

二叉树的遍历二中序遍历左根右※规则：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问