软件开发技术基础（第4版）课件：非线性数据结构-树和图.pptx

非线性数据结构

—树与图

树的递归定义

树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：

1）其中有一个特定的元素称为T的根root。

2）除根以外的集合可划分为m个不相交子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。

2

与树相关的术语

结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。

结点的度：结点拥有的非空子树的个数。

树的度：树中所有结点的度的最大值。

叶子结点：没有非空子树的结点。

分支结点：至少有一个非空子树的结点。

孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。

3

与树相关的术语

兄弟结点：具有相同父结点的结点互为兄弟结点。

结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。

树的深度：树中结点所在的最大层次。

有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。

森林：由零棵或有限棵互不相交的树组成的集合。

4

二叉树的定义

二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。

特殊形式的二叉树

5

二叉树有下列重要性质

在二叉树的第k层上至多有2k-1个结点(k≥1)

深度为h的二叉树上至多含2h-1个结点(h≥1)

包含n(n0)个结点的二叉树总的分支数为n-1

任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1

具有n个结点的完全二叉树的深度为[log2(n)]+1

6

二叉树有下列重要性质

6.若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：

①若i=1，则该结点是二叉树的根，无父结点。否则，编号为[i/2]的结点为其父结点；

②若2in，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；

③若2i+1n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。

7

二叉树的链式存储

8

利用结点形式存储的树称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。

二叉树的遍历

9

三种主要的遍历算法——先序遍历、中序遍历和后序遍历。

1）先序遍历：首先访问根结点，然后按先序遍历方式访问左子树，最后按先序遍历方式访问右子树。

2）中序遍历：首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。

3）后序遍历：首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。

图的基本概念

10

图是由顶点集合及顶点间的关系集合组成的一种数据结构。一般记作Graph＝(V,E)。其中V是顶点的有限非空集合；E是顶点之间关系的有限集合。

•边：顶点x到y的一条双向通路，称为边，用(x,y)表示。

•弧：顶点x到y的一条单向通路，则称为弧，用x,y表示。

•邻接点：如果(x,y)是图中的一条边，则称x与y互为邻接点；如果x,y是图中的一条弧，则称y为x的邻接点。

•顶点的度：一个顶点v的度是与它相关联的边的条数。

图的基本概念

11

•无向图：若图是由一些顶点和边构成则称之为无向图。

•有向图：若图是由一些顶点和弧构成则称之为有向图。

•权：某些图的边或弧具有与它相关的数，称之为权。这种带权图叫做网络。

图的基本概念

12

•路径：在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1、vp2、…、vpm到达顶点vj。则称顶点序列(vi，vp1，…，vpm，vj)为从顶点vi到顶点vj的路径。若路径上各顶点均不互相重复，则称这样的路径为简单路径。

•路径长度：非带权图的路径长度是指此路径上边或弧的条数，带权图的路径长度是指路径上各边或弧的权之和

•子图：设有两个图G＝(V，E)和G′＝(V′，E′)。若V包含V′且E包含E′，则称图G′是图G的子图。

图的存储方式

13

1．邻接矩阵:利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵。

(a)无向图邻接矩阵(b)有向图邻接矩阵(c)网络邻接矩阵

图的存储方式

14

2．邻接表

邻接表的结点结构

(c)网络的表结点

(a)头结点

(b)无权图的表结点

图的存储方式

图的存储方式

图的遍历方法

1．深度