资源描述
树和图,西安交通大学计教中心 ,树的递归定义:,树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。 2）除根以外的集合可被划分为m个不相交的子集T1，T2，Tm，其中每个子集都是树。它们称为根root的子树。,与树相关的术语, 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度的最大值。 叶子结点：没有非空子树的结点。 分支结点：至少有一个非空子树的结点。 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。, 兄弟结点：具有相同父结点的结点互为兄弟结点。 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 树的深度：树中结点所在的最大层次。 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 森林：由零棵或有限棵互不相交的树组成的集合。,二叉树的定义,二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。,特殊形式的二叉树,满二叉树：当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树。完全二叉树：从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。满二叉树可看作是完全二叉树的一个特例。,二叉树有下列重要性质：,（1）在二叉树的第k层上至多有2k-1个结点(k1) 证明：当k=1时，命题显然成立。假定k=n-1时命题成立，则第n层（k=n）的结点数最多是第n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结点。命题成立。 （2）深度为h的二叉树上至多含2h-1个结点(h1) 证明：根据性质1容易知道深度为h的二叉树最多有20+21+2h-1个结点，即最多有2h-1个结点。,（3）包含n(n0)个结点的二叉树总的分支数为n-1 证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。,（4）任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1 证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为： n0 + n1 + n2（2-2） 再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1 + 2n2（2-3） 由（2-2）（2-3）两式可知：n0=n2+1,（5）具有n个结点的完全二叉树的深度为log2(n)+1 证明：假设二叉树的深度为h，则必有2h-1-1n2h-1，于是有2h-1n+12h，也就是 2h-1n2h，从而得到h-1log2(n)h，于是h=log2(n)+1。,（6） 若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点： 若i=1，则该结点是二叉树的根，无父结点。否则，编号为i/2的结点为其父结点； 若2in，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点； 若2i+1n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。 证明通过对i进行归纳即可得证。,二叉树的链式存储,结点定义： struct BinTreeNode ElemType data; struct BinTreeNode *leftChild, *rightChild; ; 这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶子结点或一个新生成的结点而言，其左孩子和右孩子指针都应为空值。,利用这种结点形式存储的树一般称为二叉链表。 从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。,二叉树的常用算法包括：获取根结点指针、判断树是否为空、插入或删除结点、插入或删除子树、二叉树遍历等。 二叉树类可描述如下： class BinTree public: BinTreeNode *root;/定义根结点指针 BinTree() root=NULL; /构造函数，定义空树 /判断树是否为空 bool IsEmpty() return root=NULL; /在叶子结点p下插入左子树q void Ins_lchild(BinTreeNode *p,BinTreeNode *q) p-leftChild=q; ( 接下页 ),( 接上页 ) /在叶子结点p下插入右子树q void Ins_rchild(BinTreeNode *p,BinTreeNode *q) p-rightChild=q; /删除结点p的左子树 void Del_lchild(BinTreeNode *p) p-leftChild=NULL; /删除结点p的右子树 void Del_rchild(BinTreeNode *p) p-rightChild=NULL; void PreOrder(BinTreeNode *t);/先序遍历 void InOrder(BinTreeNode *t);/中序遍历 void PostOrder(BinTreeNode *t);/后序遍历 ;,二叉树的遍历,二叉树遍历是只按照某种顺序访问二叉树的每个结点，并且每个结点只被访问一次。这是二叉树中经常用到的操作，有三种主要的遍历算法先序遍历、中序遍历和后序遍历。,（1）先序遍历 对一颗非空二叉树进行先序遍历时，首先访问根结点，然后按先序遍历方式访问左子树，最后按先序遍历方式访问右子树。先序遍历算法如下： void BinTree:PreOrder(BinTreeNode *t) if (t) Visit( t ); /访问根结点 PreOrder( t-leftChild ); /遍历左子树 PreOrder( t-rightChild ); /遍历右子树 ,（2）中序遍历 对一颗非空二叉树进行中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历算法如下： void BinTree:InOrder(BinTreeNode *t) if(t) InOrder( t-leftChild );/ 遍历左子树 Visit( t ); / 访问根节点 InOrder( t-rightChild ); / 遍历右子树 ,（3）后序遍历 对一颗非空二叉树进行中序遍历时，首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。后序遍历算法如下： void BinTree:PostOrder(BinTreeNode *t) if(t) PostOrder( t-leftChild ); /遍历左子树 PostOrder( t-rightChild ); /遍历右子树 Visit( t ); /访问根节点 ,图的基本概念,图的来源：通信网、交通网等，它表现了数据对象间多对多的联系。在该结构中，数据元素一般称为顶点。 图的定义： 图是由顶点集合及顶点间的关系集合组成的一种数据结构。一般记作Graph( V, E )。其中V是顶点的有限非空集合；E是顶点之间关系的有限集合。,以下是图的相关术语 边：若顶点x到y是的一条双向通路，则称为边，用(x，y)表示。 弧：若顶点x到y是的一条单向通路，则称为弧，用表示。 邻接点：如果(x,y)是图中的一条边，则称x与y互为邻接点；如果是图中的一条弧，则称y为x的邻接点。 顶点的度：一个顶点v的度是与它相关联的边的条数。, 无向图：若图是由一些顶点和边构成则称之为无向图。 有向图：若图是由一些顶点和弧构成则称之为有向图。 权：某些图的边或弧具有与它相关的数，称之为权。这种带权图叫做网络。, 路径：在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1，vp2，vpm，到达顶点vj。则称顶点序列( vi，vp1，vp2，vpm，vj )为从顶点vi到顶点vj的路径。若路径上各顶点均不互相重复，则称这样的路径为简单路径。 路径长度：非带权图的路径长度是指此路径上边或弧的条数，带权图的路径长度是指路径上各边或弧的权之和。, 子图：设有两个图G(V，E)和G(V，E)。若V包含V且E包含E，则称图G是图G的子图。 连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。 强连通图：在有向图中，若对于每一对顶点vi和vj，都存在从vi到vj和从vj到vi的路径，则称此图是强连通图。, 生成树：一个连通图的生成树是它的极小连通子图。即包含了所有顶点以及最少的边或弧的子图，并且这些边或弧使得任意两顶点相互连通。在含有n个顶点的无向图中，生成树一定有n-1条边，且生成树的形式可能有多个。,图的存储方式,1邻接矩阵 利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵。 邻接矩阵 存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,图的邻接矩阵存储可以用下面的结构体表示： #define MAX_NUM 100 / 最大顶点个数 typedef struct VertexType vexsMAX_NUM; /顶点信息数组 ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵 int vexnum,arcnum; /图的实际顶点数和弧(边)数 int kind; /图的种类标志, 1有向图, /2有向网,3无向图,4无向网 MGraph; 其中ArcType是顶点关系的数据类型。VertexType是顶点的数据类型。MAX_NUM表示最多可存的顶点数。,假设无向图G=(V,E)是一个有n个顶点的图，则图的邻接矩阵A是n阶方阵，其内容如下：,其中W(i, j)是与边或弧相关的权。,对于含权的网络而言，其邻接矩阵可定义如下：,(a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵,2邻接表 邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。 （1）头结点都存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。 （2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。 （3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。,邻接表的结点结构,(c)网络的表结点,(a)头结点,(b)无权图的表结点,图的邻接表描述,#define MAX_NUM 100/顶点最大允许数量 struct AdjNode /表结点类型定义 int adjvex; /该邻接点在数组中的位置 InfoType info;/该弧相关信息 struct AdjNode *next; /指向下一邻接点的指针 ; typedef struct VNode /头结点类型定义 VertexType data; /顶点信息 AdjNode *first; /指向邻接表第一个结点 AdjListMAX_NUM;,typedef struct AdjList headArray; /头结点数组 int vexnum, arcnum; /图的当前顶点数和弧数 int kind; /图的种类标志 ALGraph; 其中AdjNode为表结点，InfoType为与边相关信息的数据类型（可以包括权等）。VNode为头结点，VertexType是顶点的数据类型，MAX_NUM表示最多可以存放的顶点个数。,图的遍历方法,1深度优先搜索 假定从图中某个顶点v 出发进行遍历，则首先访问此顶点，然后依次从v的各个未被访问的邻接点出发，执行深度优先搜索遍历，直至图中所有和v有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,用非递归的方式描述如下：首先访问图中某一起始顶点v0，由v0出发，访问它的任一邻接点vi；再从vi出发，访问与vi邻接但还没有访问过的顶点vj；如此进行下去，直至到达某一顶点vt后，发现vt所有的邻接顶点都被访问过。于是从vt退到前一次刚访问过的顶点vs，看看vs是否还有其他没有被访问的邻接顶点。如果有则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,bool visitedMAX; /顶点访问标志数组 /从第v个顶点出发递归地深度优先遍历图G的 /某个连通子图 void DFS(ALGraph G, int v) AdjNode *p; visitedv = TRUE; coutnext ) if(!visitedp-adjvex) DFS(G,p-adjvex); ,2广度优先搜索 假定从图中某个顶点v 出发进行遍历，则首先访问此顶点，再依次访问v的所有未被访问过的邻接点，然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和v有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,以图(a)为例，假设从A出发进行广度优先搜索，首先访问A，然后依次访问A的各个未被访问过的邻接顶点B、E、D,再分别从B、E、D出发，访问它们的所有还未被访问过的邻接顶点C、F、G。,为了实现逐层访问，广度优先搜索算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。,A B E D C F G,哈夫曼树和哈夫曼编码,设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。 例如：某个文件由A、B、C、D四个字符组成，其中A用得最多，C次之。 方案1: A 1 C 0 B 10 D 11 那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。 为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。,(a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树,任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应，该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。,可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表0，右分支代表1，则不论字符是采用何种0、1组合形式构成的编码，它必然对应某个二叉树中一个结点。,1）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。而某个字符编码的长度就是对应的二叉树中根到某个叶子的分支的数目（又称为根到叶子的路径长度）。 2）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。也就是用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，显然这种加权和除以字符总数就是每个字符的加权平均编码长度。,二叉树带权路径长度：设二叉树有n个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。一般记作： 其中，wi为第i个叶子的权重，li为第i个叶子到根的路径长度。 哈夫曼树：以一些带有固定权值的结点作为叶子所构造的，具有最小带权路径长度的二叉树称为哈夫曼树。,假定有n个具有权值的结点，则哈夫曼树的构造算法如下： 根据给定的n个权值w1, w2, , wn，构造n棵二叉树的集合F=T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树； 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； 从F中删去这两棵树，同时加入刚生成的新树； 重复和两步，直至F中只含一棵树为止。,假定有一段报文由a、b、c、d四个字符构成，它们的使用频率比为6421，则用a、b、c、d作为叶子结点构造哈夫曼树的过程如图所示。,若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。,【例2-5】假定编码系统中有五个字符X、S、D、E、A，它们的使用频率比为29578，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。,最小生成树,考虑一个通信网的建设问题。假定在多个城市间建立通信网络，将城市作为顶点，将所有可能的通信线路作为边，就构成一个图结构。再以通信线路的造价作为边的权重就构成一个无向网络。在保证通信功能的前提下，为了使总造价最小，需要寻找网络中权重之和最小的连通子图。,（1）普里姆算法 假定G= V, E 为连通网络，其中V为顶点集合，E为带权边集合。设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。而后考察这样的边，它的一个顶点uU，另一个顶点vV-U，每次从所有这样的边中选择权值最小的边(u, v)加入集合T，并把顶点v加入到集合U中。如此不断重复，直到所有顶点都加入到集合U中为止。,（2）克鲁斯卡尔算法 假定G= V, E 为连通网络，其中V为顶点集合，E为带权边集合。先构造一个包含所有顶点，没有边的非连通图T= V, ，图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在T的不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。,
展开阅读全文