第20章非线性数据结构

1、第第2020章章 非线性数据结构非线性数据结构本章介绍的非线性数据结构主要描述数据元素间的一本章介绍的非线性数据结构主要描述数据元素间的一对多和多对多关系。主要介绍二叉树、图两种非线性数据结对多和多对多关系。主要介绍二叉树、图两种非线性数据结构的定义、存储结构描述及其基本操作的实现方法。构的定义、存储结构描述及其基本操作的实现方法。20.1 20.1 二叉树二叉树二叉树是树形结构最简单的形式，也是应用最广泛的二叉树是树形结构最简单的形式，也是应用最广泛的树形结构。本节首先介绍二叉树的定义、性质，然后重点介树形结构。本节首先介绍二叉树的定义、性质，然后重点介绍二叉树的存储和遍历。绍二叉树的存储和

2、遍历。20.1.1 20.1.1 二叉树的定义二叉树的定义二叉树很像一棵倒悬着的树，从树根到分枝、直到叶二叉树很像一棵倒悬着的树，从树根到分枝、直到叶子把数据联系起来，分枝数最多为二枝，这种数据结构就叫子把数据联系起来，分枝数最多为二枝，这种数据结构就叫做二叉树结构，简称二叉树。做二叉树结构，简称二叉树。20.1.2 20.1.2 二叉树的性质二叉树的性质性质1 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点（个结点（i1）。）。性质2 深度为深度为k的二叉树中至多含有的二叉树中至多含有2k- -1个结点（个结点（k1）。）。性质3 对任何一棵二叉树对任何一棵二叉树T，如果其终端

3、结点数为，如果其终端结点数为n0，度为度为2的结点数为的结点数为n2，则，则n0= n2+1。性质4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1。性质5 如果对一棵有如果对一棵有n个结点的完全二叉树（其深度为个结点的完全二叉树（其深度为log2n+1）的结点按层序（从第）的结点按层序（从第1层到第层到第 log2n+1层，每层从层，每层从左到右）从左到右）从1起开始编号。则对任一编号为起开始编号。则对任一编号为i的结点（的结点（1in），有以下条件成立。），有以下条件成立。20.1.2 20.1.2 二叉树的性质二叉树的性质如果如果i=1，则编号为，则编号为i

4、的结点是二叉树的根，无双亲；如的结点是二叉树的根，无双亲；如果果i1，则其双亲结点，则其双亲结点parent(i)的编号是的编号是i/2。如果如果2in，则编号为，则编号为i的结点无左孩子（编号为的结点无左孩子（编号为i的结点的结点为叶子结点）；否则其左孩子结点为叶子结点）；否则其左孩子结点lChild(i)的编号是的编号是2i 。如果如果2i+1n，则编号为，则编号为i的结点无右孩子；否则其右孩的结点无右孩子；否则其右孩子结点子结点rChild(i)的编号是结点的编号是结点2i+1。20.1.3 20.1.3 二叉树的存储结构二叉树的存储结构1.二叉树的顺序存储结构二叉树的顺序存储结构2.二

5、叉链表存储结构二叉链表存储结构3.三叉链表存储结构三叉链表存储结构4.双亲链表存储结构双亲链表存储结构20.1.4 20.1.4 二叉树的遍历二叉树的遍历1.遍历的描述遍历的描述2.二叉树递归遍历算法二叉树递归遍历算法3.二叉树非递归遍历算法二叉树非递归遍历算法1）先序遍历）先序遍历2）中序遍历）中序遍历3）后序遍历）后序遍历20.2 20.2 图图图形结构是一种比线性结构和树形结构更复杂的非线图形结构是一种比线性结构和树形结构更复杂的非线性数据结构。在图形结构中，结点之间的关系可以是任意的性数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相邻，图中任意两个元素之

6、间都可能相邻。20.2.1 20.2.1 图的定义图的定义1.无向图和有向图无向图和有向图2.子图子图3.顶点的度顶点的度20.2.2 20.2.2 图的存储结构图的存储结构1.邻接矩阵存储结构邻接矩阵存储结构2.邻接表和逆邻接表存储结构邻接表和逆邻接表存储结构20.2.3 20.2.3 图的遍历图的遍历1.深度优先遍历深度优先遍历1）深度优先遍历算法思想）深度优先遍历算法思想2）算法实现）算法实现2.广度优先遍历广度优先遍历1）广度优先遍历算法思想）广度优先遍历算法思想2）算法实现）算法实现20.3 20.3 小结小结本章介绍了非线性数据结构二叉树和图的数据结构定本章介绍了非线性数据结构二叉

7、树和图的数据结构定义、存储结构描述和基本运算算法的实现。重点讨论了二叉义、存储结构描述和基本运算算法的实现。重点讨论了二叉树的先序、中序和后序遍历算法、图的存储结构表示及图的树的先序、中序和后序遍历算法、图的存储结构表示及图的深度和广度优先遍历算法的实现。下一章主要介绍数据的操深度和广度优先遍历算法的实现。下一章主要介绍数据的操作：查找和排序。作：查找和排序。20.4 20.4 习题习题1建立一个二叉树，并实现对其先序、中序和后序遍建立一个二叉树，并实现对其先序、中序和后序遍历输出。历输出。2采用二叉链的存储结构，按键盘输入的形式为结点采用二叉链的存储结构，按键盘输入的形式为结点元素赋值，结点元素为字符型。最后，实现按层遍历输出元素赋值，结点元素