(
课件网) 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.中序遍历 中序遍历的规则是：若二叉树为空，则空操作返回；否则，先访问 ... ...
