第14课 二叉树的基本操作与抽象数据类型-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第14课　二叉树的基本操作与抽象数据类型(见学生用书P105)

 

——4.2　二叉树的基本操作　4.3　抽象数据类型，教材P106～118

1.掌握使用数组和链表等数据结构建立二叉树的方法。　2.掌握二叉树遍历的基本操作方法。　3.了解抽象数据类型的概念。

1． 二叉树的遍历

建立二叉树的操作，可以按照　层　的顺序进行，先由第　1　层开始，依次到下一层，在每一层中按照　从左到右　的顺序创建节点。

(1)数组实现

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

②非完全二叉树：用数组表示非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示，数据存储时对应位置空缺，其他节点在数组中的位置参照完全二叉树。

③对于一般的二叉树来说，一个深度为k且只有k个节点的树需要2k－1个节点的存储

空间才能表示出来，容易造成存储空间的浪费。

(2)链表实现

用链表实现二叉树，每个节点至少需要　3　个域，一个　数据域　和两个　指针域　。数据域用于存放本节点的　数据信息　，左右两个指针域分别指向节点的　左孩子和右孩子　。

(3)list构造二叉树法

①空树用None表示。

②非空二叉树用包含三个元素的列表[d，l，r]表示，其中：d表示根节点的元素，l和r是两棵子树，采用与整个二叉树同样结构的list表示。例如：

2． 二叉树的遍历

(1)二叉树的遍历，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被　访问一次且仅被访问一次　。二叉树的遍历方式有很多，主要有　前序遍历　、　中序遍历　、　后序遍历　等。

①前序遍历：若二叉树为空，则空操作返回；否则，先访问根节点，再访问左子树，最后访问右子树。简单描述：　根左右　；把每层的子树看成一个单独的树，依然按照前序遍历进行。

②中序遍历：若二叉树为空，则空操作返回；否则，先访问左子树，再访问根节点，最后访问右子树。简单描述：　左根右　；把每层的子树看成一个单独的树，依然按照中序遍历进行。

③后序遍历：若二叉树为空，则空操作返回；否则，先访问左子树，再访问右子树，最后访问根节点。简单描述：　左右根　；把每层的子树看成一个单独的树，依然按照后序遍历进行。