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

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 ^