软件开发技术基础 第4版 课件 3.树和图

非线性数据结构

—树与图树的递归定义树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。2）除根以外的集合可划分为m个不相交子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。

西安交通大学计算机教学实验中心2GACFDEB树的一般形式与树相关的术语结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。结点的度：结点拥有的非空子树的个数。树的度：树中所有结点的度的最大值。叶子结点：没有非空子树的结点。分支结点：至少有一个非空子树的结点。孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。西安交通大学计算机教学实验中心3与树相关的术语兄弟结点：具有相同父结点的结点互为兄弟结点。结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。树的深度：树中结点所在的最大层次。有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。森林：由零棵或有限棵互不相交的树组成的集合。

西安交通大学计算机教学实验中心4二叉树的定义二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。特殊形式的二叉树西安交通大学计算机教学实验中心5AFC满二叉树GDBEAC完全二叉树DBE二叉树有下列重要性质在二叉树的第k层上至多有2k-1个结点(k≥1)深度为h的二叉树上至多含2h-1个结点(h≥1)包含n(n>0)个结点的二叉树总的分支数为n-1任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1具有n个结点的完全二叉树的深度为[log2(n)]+1西安交通大学计算机教学实验中心6二叉树有下列重要性质6.若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：①若i=1，则该结点是二叉树的根，无父结点。否则，编号为[i/2]的结点为其父结点；②若2i>n，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；③若2i+1>n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。西安交通大学计算机教学实验中心7二叉树的链式存储西安交通大学计算机教学实验中心8二叉树的链式存储ABC∧∧D∧∧E∧∧利用结点形式存储的树称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。

二叉树的遍历西安交通大学计算机教学实验中心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•无向图：若图是由一些顶点和边构成则称之为无向图。•

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

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

(b)有向图

(c)网络

图的基本概念

西安交通大学计算机教学实验中心12•路径：在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1、vp2、…、vpm到达顶点vj。则称顶点序列(vi，vp1，…，vpm，vj)为从顶点vi到顶点vj的路径。若路径上各顶点均不互相重复，则称这样的路径为简单路径。•路径长度：非带权图的路径长度是指此路径上边或弧的条数，带权图的路径长度是指路径上各边或弧的权之和•子图：设有两个图G＝(V，E)和G′＝(V′，E′)。若V包含V′且E包含E′，则称图G′是图G的子图。图的存储方式

西安交通大学计算机教学实验中心131．邻接矩阵:利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵。0132528130123410234(a)无向图

(b)有向图 (c)网络

0132401324012340123401230132(a)无向图邻接矩阵

(b)有向图邻接矩阵

(c)网络邻接矩阵

图的存储方式

西安交通大学计算机教学实验中心142．邻接表邻接表的结点结构(c)网络的表结点infonextadjvexnextadjvexfirstdata(a)头结点(b)无权图的表结点图的存储方式

图的存储方式

图的遍历方法

1．深度优先搜索

图的遍历方法

2．广度优先搜索

哈夫曼树和哈夫曼编码

假定有n个具有权值的结点，则哈夫曼树的构造算法如下：①根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；②在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；③从F中删去这两棵树，同时加入刚生成的新树；④重复⑵和⑶两步，直至F中只含一棵树为止。哈夫曼树和哈夫曼编码

假定有一段报文由a、b、c、d四个字符构成，它们的使用频