数据结构实用教程（C语言版）中ppt课件

1、数据构造适用教程数据构造适用教程C C言语版中言语版中第五章 树 第六章 图第五章 树 v树形构造的逻辑特征是：有且仅有一个开场结点，可有假设干个终端结点，其他的内部结点都有且仅有一个前趋结点，可以有假设干个后继结点，也就是说构造中的数据元素间存在着一对多的层次关系。v本章首先简单引见树的根本概念，然后重点讨论二叉树的逻辑构造、存储构造及其运算，线索二叉树和线索二叉链表以及如何利用线索来实现遍历运算，并分析树、森林与二叉树之间的相互转换问题，最后引见二叉树和树的典型运用。主要内容：51 树的定义 52 二叉树 二叉树的定义及性质 二叉树的存储 二叉树的遍历及实现算法 53 线索二叉树 中序线索

2、二叉树的定义 中序线索二叉树上遍历的实现 利用中序线索实现前序遍历和后序遍历 54 树和森林55 哈夫曼树51 树的定义 一、树的定义1、树的二元组定义：设tree=D，S，其中D是数据元素的集合，S是D中数据元素之间关系的集合。设关系rS，相对r，满足以下条件： 1D中有且仅有一个开场结点，该结点被称为树的根Root；2除树根结点外，D中其他的结点有且仅有一个前趋结点；3从根到其他结点都有途径。那么称tree是相对r的树形构造。如下图的树：该树采用二元组表示如下：设tree=D，S，rSD=A， B， C， D， E， F， G， H， Ir=， ，其中A是开场结点，即树的根；除根A外，其他

3、的结 点有且仅有一个前趋结点，但对于后继结点却没有限制，A有三个后继结点B、C和D，B和G分别有两个后继结点，D只需一个后继结点，剩下的结点E、F、C、H、I都没有后继，属于终端结点。IHGFECDBA树形构造与线性构造比较：在线性构造中，有且仅有一个开场结点和一个终端结点，其他的内部结点都有且仅有一个前趋和一个后继。在树形构造中也是有且仅有一个开场结点称为根，但终端结点称为叶子可以为恣意多个，其他的内部结点都有且仅有一个前趋，但可以有恣意多个后继。树形构造中放宽了对结点的后继的限制。线性构造中每个元素的后继最多为一个，而树形构造的后继可以为多个。假设树中每个非终端结点的后继刚好为一个时，就是

4、线性表，线性构造是树形构造的一种特殊方式。 2、树的递归定义树是一种递归的数据构造，也可以用递归的方式来定义树，树的递归定义如下：树是nn0个结点的有限集合记作T，它满足两个条件：1有且仅有一个特定的称为根的结点；2其他的结点可分为mm0个互不相交的有限集合T1，T2，Tm，其中每个集合又是一棵树，并称其为根的子树Subtree。 3、树的表示方法除了前面引见的树形表示法和二元组表示法外，还有其他三种常用的表示方法：凹入表表示法、嵌套集合表示法和广义表表示法。其中，树形表示法是最常用的表示方法，本书主要采用树形表示法由于连线的箭头全部向下，所以省略箭头。 4、树中常用的一些根本术语：1与层次相

5、关的术语：在树中，有且仅有一个开场结点，称为根结点Root，在树中处于最上层；除根结点外的其他一切结点都有且仅有一个前趋，每个结点的前趋结点称为该结点的父双亲结点Parent，在树中处于该结点的上一层；树中的每个结点都可以有假设干个后继结点，每个结点的后继点称为该结点的子孩子或子女结点Child，在树中处于该结点的下一层，它们是该结点的子树的根。没有后继的结点称为叶子结点Leaf，叶子结点是树的终端结点，可以为多个。双亲一样的结点互称为兄弟Silbing，在树中处于同一层。2树中结点之间具有分支：一个结点的子树的个数，称为该结点的度Degree，树中度最大的结点的度数称为该树的度。3途径Pat

6、h是树中结点的序列，设结点序列为b1，b2，bj，假设序列中恣意两个相邻结点都满足bi是bi+1的双亲，1ij-1，那么称该结点序列为从b1 到bj的途径。途径长度为序列中结点总数减1，即所经过的边的数目。假设树中存在一条从b 到bj的途径，那么称b是bj的祖先Ancestor，而bj是b的子孙Descendant。4假设树中一切子树都看成是从左到右的次序陈列子树不能互换，那么称此树为有序树Ordered Tree。而不思索子树陈列顺序的树，称为无序树Unordered Tree。5森林Forest是mm0棵互不相交的树的集合。52 二叉树一、二叉树的定义及性质一、二叉树的定义及性质 1、二叉

7、树、二叉树Binary Tree是是nn0个结个结点的有限集合，满足：点的有限集合，满足：当当n=0时，为空二叉树。时，为空二叉树。当当n0时，是由一个根结点和两棵互不相交时，是由一个根结点和两棵互不相交的分别称作这个根的左子树和右子树的二叉树的分别称作这个根的左子树和右子树的二叉树组成。组成。在二叉树中，每个结点左子树的根为该结点在二叉树中，每个结点左子树的根为该结点的左孩子的左孩子Left Child，右子树的根为该结，右子树的根为该结点的右孩子点的右孩子Right Child。 2、二叉树通常有五种根本形状:3、二叉树具有以下重要的性质：性质 1 二叉树第i层上最多有2i-1i1个结点。

8、 性质 2 深度为k的二叉树最多有2k-1i1个结点。性质 3 在恣意一棵二叉树中，假设叶子结点数为n0，度为2的结点数为n2，那么n0=n2+1。 两种特殊的二叉树：满二叉树和完全二叉树 每层结点数都到达最大值的二叉树称为满二叉树Full Binary Tree。除最下面一层外其他各层的结点数都到达最大值，并且最下一层上的结点都集中在最左边的假设干位置上，那么此二叉树为完全二叉树Complete Binary Tree。 a满二叉树 b完全二叉树 c类似完全二叉树显然，满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。假设将满二叉树的最下层上结点从最右边开场延续删去假设干个，就可以得到一棵

9、完全二叉树。性质 4 具有n个结点的完全二叉树的深度为 或 。性质 5 对一棵具有n个结点的完全二叉树，按照层次从上到下、每一层从左到右的次序亦称二叉树的层次次序将一切结点依次陈列，可得到结点的层序序列，其中根结点的序号为1，其他结点的序号延续陈列。对任一序号为i的结点称结点i，有：1假设结点i有双亲除根结点外，即i1，那么双亲的序号为i/2。2假设结点i有左孩子即2in时，那么左孩子为2i，即恣意结点左孩子的序号一定为偶数。3假设结点i有右孩子即2i+1n时，那么右孩子为2i+1，即恣意结点右孩子的序号一定为奇数。4当i为偶数且in时，它有右兄弟，右兄弟为i+1；当i为奇数且i1时，它有左兄

10、弟，左兄弟为i-1。 2log1n (1)2logn二、二叉树的存储 1顺序存储 1完全二叉树的顺序存储对一棵具有N个结点的完全二叉树，将一切结点按照从上到下、从左到右的次序依次陈列，得到完全二叉树中结点的层序序列，其中根结点的序号为1，然后将这个序列依次存储在长度为N+1的数组bt中为了坚持序号和下标一致，下标为0的单元不用，完全二叉树及其顺序存储构造如下图。下标012345678结点ABCDEFGH2普通二叉树的顺序存储 普通二叉树与完全二叉树对照，在空缺的位置处添加虚点用特殊字符，如“#表示，从而将普通的二叉树扩展成完全二叉树，然后将扩展后的完全二叉树顺序存储。即带着添加的虚点一同将完全

11、二叉树中的结点按层序陈列，按照序号将一切结点依次存放在一维数组中，其中根结点的编号为1。 下标01234567891011结点ABDCE#F2链接存储每个结点除了存储本身的数据外，需求附加两个指针域分别指向该结点的左孩子和右孩子，这就是二叉链表。 有时为了运算方便，每个结点再附加一个指针域存储双亲结点的指针，即带父指针的二叉链表，也称为三叉链表 。二叉链表是二叉树的链接存储构造中为最常用的一种，其中lchild和rchild分别表示指向结点左、右孩子的指针。lchilddatarchild 二叉链表存储构造的C言语描画为： typedef char DataType; typedef stru

12、ct Node DataType data; struct Node *lchild,*rchild; BiTree; BiTree *root; /*根结点的指针*/ 二叉树中的每个结点都为BiTree类型，它们之间经过lchild指针和rchild指针联络在一同，可以经过保管根结点的指针root来独一标识一棵二叉树。3、二叉链表的建立算法的实现步骤如下：1初始化队列和二叉链表；2读取用户输入的结点信息，假设不是虚点，那么建立一个新结点，同时将结点的地址入队；3新结点假设为第一个结点，那么将此结点的地址存入根指针中；否那么，从队头中取出双亲结点的指针，将此结点作为左孩子或右孩子链接到双亲结点

13、上，假设此结点的编号为偶数那么为左孩子，否那么为右孩子。当一个结点的两个孩子都已链接终了，即结点编号为奇数时，队头元素出队，此时的队头元素必定是下一个新结点的双亲结点；4反复步骤23，直到遇到终了标志符。#define MAXSIZE 100typedef struct/*顺序队列的定义 */ BiTree * dataMAXSIZE; int front,rear;SeQueue;BiTree * createTree() SeQueue Q,*q=&Q;/* 队列 */ BiTree *root,*s; char ch; root=NULL;/* 置空二叉树 */ q-front

14、=1; q-rear = 0; /* 置空队列，队尾保管新创建结点的指针，队头保管新结点的双亲的指针 */ ch=getchar() ; /* 输入一个字符 */ while(ch!=) /* 假设输入字符不是终了符，那么反复处置 */ s=NULL; if(ch!=#) /*不是虚点，那么创建新结点，假设是虚点，s=NULL*/ s=(BiTree *)malloc(sizeof(BiTree); s-data=ch; s-lchild=NULL; s-rchild=NULL; q-rear+;/* 队尾指针后移 */ q-dataq-rear=s; /* 新结点地址或虚点地址NULL入队

15、*/ if(root=NULL) root=s;/* 假设新结点为第一个结点，那么保管此结点为根结点 */ else if(q-dataq-front!=NULL) /* 双亲不是虚点时，将新结点链接在双亲上 */ if(q-rear%2=0) q-dataq-front-lchild=s; /* 新结点为左孩子 */ else q-dataq-front-rchild=s; /* 新结点为右孩子 */ if(q-rear%2=1) q-front +; /* 左右孩子处置终了后，出队*/ ch=getchar();/* 输入下一个字符 */ return root;三、二叉树的遍历及实现算法

16、 二叉树的遍历Traversal是指沿着某条搜索途径访问二叉树中的每个结点，且每个结点仅访问一次。 “访问是指对结点的操作，其含义可以很广，如可以是输出结点的信息、修正结点数据等。 二叉树由根结点、左子树、右子树三个根本部分组成，遍历一棵非空二叉树的问题可分解为：访问根结点、遍历左子树和遍历右子树。假设分别用L、D、R分别表示上述三个子问题，那么可有6种不同的遍历次序：DLR、LDR、LRD、DRL、RDL、RLD。商定左子树的访问在右子树之前，那么讨论三种遍历方法：DLR：前序遍历PreOrderLDR：中序遍历InOrderLRD：后序遍历PostOrder。二叉树是递归的数据构造，由于它

17、的左、右子树也是二叉树，因此对左、右子树的遍历依然是遍历二叉树的问题，要用一样的次序来完成。所以，可以用递归的方法来定义二叉树的遍历运算：1前序遍历二叉树DLR 假设二叉树非空，那么： 1访问根结点； 2前序遍历左子树； 3前序遍历右子树。2中序遍历二叉树LDR 假设二叉树非空，那么： 1中序遍历左子树； 2访问根结点； 3中序遍历右子树。3后序遍历二叉树LRD 假设二叉树非空，那么： 1后序遍历左子树； 2后序遍历右子树； 3访问根结点。编写递归算法需求把握两个方面内容：递归项和递归出口亦称终止条件。这里的递归项比较明显，由于对左、右子树的遍历就是对二叉树的遍历，那么遍历左子树和遍历右子树都

18、为递归项。另外，只需二叉树不为空，就可以将其分成根、左子树、右子树三个部分，分别进展访问。但假设二叉树为空树，遍历运算就终了了，所以递归出口是二叉树为空。由此，可以得出二叉树遍历的递归算法。void PreOrder(BiTree * T) /* 前序遍历二叉树*/ if (T) /* 当二叉树非空，进入递归过程；否那么，遍历运算终了*/ printf(%c,T-data); /* 访问根结点 */ PreOrder(T-lchild); /* 前序遍历左子树 */ PreOrder(T-rchild); /* 前序遍历右子树 */ void InOrder (BiTree * T)/* 中序

19、遍历二叉树*/ if (T) InOrder (T-lchild); /* 中序遍历左子树 */ printf(%c,T-data); /* 访问根结点 */ InOrder (T-rchild); /* 中序遍历右子树 */ void PostOrder (BiTree * T)/* 后序遍历二叉树*/if (T) PostOrder (T-lchild); /* 后序遍历左子树 */ PostOrder (T-rchild); /* 后序遍历右子树 */ printf(%c,T-data); /* 访问根结点 */ 二叉树的中序遍历递归算法的执行过程：中遍历算法执行时的系统栈变化 ：仿照系

20、统栈在实现递归过程中的作用，本人定义一个栈将递归算法转化为非递归的算法。 非递归算法的C函数如下：#define MAXSIZE 100typedef BiTree* SElemType ;typedef struct SElemType dataMAXSIZE;/* 顺序栈中保管的是结点指针 */ int top; SeqStack;void InOrder(BiTree *p) SeqStack *s; s= initSeqStack(); while(1) while(p) push(s,p); p=p-lchild; if (empty(s) break; p= top(s);pop(

21、s); printf(“%c, p-data); p=p-rchild;53 线索二叉树当结点的左指针域为空无左孩子时，用它的左指针域存放该点在某种遍历次序下的前趋结点的指针，当结点的右指针域为空无右孩子时，用它的右指针域存放该点在某种遍历次序下的后继结点的指针。简单地说：左空指前趋，右空指后继。以这种结点构成的二叉链表称为线索二叉链表。指向前趋或后继的指针称为线索Thread。加上线索的二叉树称为线索二叉树。以某种次序遍历，使二叉树变为线索二叉树的过程称作线索化。对每个指针域再附加一个标志，当指针域中存放的是孩子指针时，标志为0；当指针域中存放的是线索时，标志为1。 线索二叉链表存储构造的C

22、言语描画如下：typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;lchildltagdatartagrchild一、中序线索二叉树的定义 假设线索二叉树的线索中保管的是结点在前序遍历下的前趋和后继的指针，那么这种线索称为前序线索；同理，假设保管的是中序遍历下的前趋和后继的指针，称为中序线索；假设保管的是后序遍历下的前趋和后继的指针，称为后序线索。对应的线索二叉树有前序线索二叉树、中序线索二叉树和后序线索二叉树，线索链表有前序线

23、索链表、中序线索链表和后序线索链表。 假设要实现中序线索化的运算，在内存中建立中序线索二叉链表，需求先按照线索树中的结点构造建立二叉链表存储构造，即每个结点的左、右标志域均为0。在这样的存储构造上进展中序线索化，只需按中序遍历二叉链表，在遍历过程中用线索取代空指针即可。设两个指针，一个指针pre一直指向刚刚访问过的结点，一个指针p指向当前正在访问的结点。详细方法是：1假设结点*p有空指针域，那么将相应的标志域置为1；2假设结点*p有中序前趋结点*prepre！=NULL那么：1假设结点*pre的右标志为1pre-rtag = =1，那么令pre- rchild为指向其中序后继结点*p的指针右线

24、索，即pre- rchild=p；2假设结点*p的左标志为1p-ltag= =1，那么令p- lchild为指向其中序前趋结点*pre的指针左线索，即p- lchild=pre；3将pre指向刚刚访问过的结点*p，即pre=p，保管前趋结点指针。 中序线索化算法的C函数：BiThrTree *pre=NULL; /*全局变量，前趋指针*/ void inthreaded (BiThrTree * p) /* 中序线索化 */if(p) inthreaded(p-lchild); /* 线索化左子树 */ if(p-lchild=NULL) p-ltag=1;/* 根据左右孩子修正当前结点*p的

25、标志域 */ if(p-rchild=NULL) p-rtag=1; if(pre!=NULL) /* 当前结点*p有前趋只需中序遍历的第一个结点无前趋 */ if(pre-rtag=1) pre-rchild=p;/* 设置前趋结点*pre的后继 */ if(p-ltag=1) p-lchild=pre; /* 设置当前结点*p的前趋 */ pre=p;/* 保管刚刚访问的结点指针*/ inthreaded(p-rchild); /* 线索化右子树 */ 二、中序线索二叉树上遍历的实现 首先要找到中序遍历的第一个结点二叉树中最左下点，其左线索为空，然后依次找到该结点的中序后继，直到中序遍历的

26、最后一个结点其右线索为空，算法终了。同理，可从中序遍历的最后一个结点出发，依次找该结点的中序前趋，直到中序遍历的第一个结点，算法终了。在中序线索下查找*p结点的中序后继有两种情况：1假设*p的右标志为1p-rtag=1，右子树为空，那么p-lchild为右线索，指向*p结点的中序后继；2假设*p的右标志为0p-rtag=0，右子树非空，那么*p的中序后继为右子树的最左下结点。也就是从*p的右孩子开场，沿左指针往下找，直到找到一个没有左孩子的结点*qq-ltag= =1，那么*q就是*p的中序后继。中序遍历算法的C函数如下：void InOrderThread(BiThrTree *root)/

27、* 中序线索下的中序遍历 */BiThrTree *p; p=root; while(p-ltag=0) p=p-lchild; /* 找中序遍历的第一个结点，二叉树的最左下点 */ while(p) printf(“%c,p-data); /* 输出结点 */ if(p-rtag=1) p=p-rchild; /*分两种情况查找结点后继 */ else p=p-rchild; while(p-ltag=0) p=p-lchild; 三、利用中序线索实现前序遍历和后序遍历 利用中序线索不但能方便地进展中序遍历，还可以方便地进展前序和后序遍历。假设可以利用中序线索找到每个结点在前序遍历下的前趋或

28、后继，便可以进展前序遍历。由于前序遍历的次序为根结点、左子树、右子树，所以利用中序线索找*p结点前序遍历下的后继的方法为：1假设*p有左孩子，那么左孩子为前序后继；2假设*p无左孩子但有右孩子，那么右孩子为前序后继；3假设*p既无左孩子也无右孩子，那么沿着*p结点的右线索q-rtag=1不断向上走，直到找到*q结点，q-rchild不是线索是指针q-rtag=0，此时*(q-rchild结点就是*p的前序后继。同理，根据中序线索可以找到每个结点后序遍历下的前趋，从而进展后序遍历。利用中序线索进展前序遍历算法的C函数如下： void PreOrderThread(BiThrTree *root)

29、 /* 中序线索下的前序遍历 */BiThrTree *p; p=root; /* 查找前序序遍历的第一个结点，根结点 */ while(p)/* 不断找前序后继 */ printf(%c,p-data); / * 输出结点 */ if(p-ltag=0) p=p-lchild; /* 查找结点前序后继 */ else while(p&p-rtag=1) p=p-rchild; if(p) p=p-rchild; 利用中序线索进展后序遍历算法的C函数如下：void PostOrderThread(BiThrTree *root)/* 中序线索下的后序遍历 */BiThrTree *p;

30、 p=root; /* 查找后序遍历的最后一个结点，根结点 */ while(p)/* 不断找后序前趋 */ printf(“%c,p-data);if(p-rtag=0) p=p-rchild; /*查找结点前趋 */ else while(p&p-ltag=1) p=p-lchild; if(p) p=p-lchild; 54 树和森林一、树和森林的遍历一、树和森林的遍历 树的先根遍历定义为：假设树非空，先访问树的先根遍历定义为：假设树非空，先访问根结点，然后从左到右依次先根遍历每棵子树根结点，然后从左到右依次先根遍历每棵子树。树的后根遍历定义为：假设树非空，先从左树的后根遍历定义

31、为：假设树非空，先从左到右依次后根遍历每棵子树，最后访问根结点到右依次后根遍历每棵子树，最后访问根结点。显然，树的先根遍历和后根遍历过程都是递显然，树的先根遍历和后根遍历过程都是递归过程。归过程。图中树的先根遍历序列为：图中树的先根遍历序列为：A，B，F，D，C，G，E，H。 后根遍历序列为：后根遍历序列为：F，B，D，G，H，E，C，A。先根遍历森林定义为：假设森林非空，那么先根遍历森林定义为：假设森林非空，那么首先先根遍历森林中的第一棵树，然后从左到首先先根遍历森林中的第一棵树，然后从左到右依次先根遍历除第一棵树外其它树组成的森右依次先根遍历除第一棵树外其它树组成的森林。林。后根遍历森林定

32、义为：假设森林非空，那么后根遍历森林定义为：假设森林非空，那么首先后根遍历森林中的第一棵树，然后从左到首先后根遍历森林中的第一棵树，然后从左到右依次后根遍历除第一棵树外其它树组成的森右依次后根遍历除第一棵树外其它树组成的森林。林。同样，森林的先根遍历和后根遍历过程也都同样，森林的先根遍历和后根遍历过程也都是递归过程。是递归过程。先根序列：先根序列：A，B，F，D，C，G，E，H，I，J，K，L，M，N，O后根序列：后根序列：F，B，D，G，H，E，C，A，J，L，K，I，O，N， 二、森林与二叉树的转换 森林转化为二叉树的定义为：1假设森林为空，那么二叉树为空；2假设森林不空，那么二叉树的根为

33、森林中第一棵树的根；二叉树的左子树为第一棵树去掉根之后的子树森林转换成的二叉树；二叉树的右子树为森林除去第一棵树后剩下的树组成的森林转化成的二叉树。 简单的转换规那么：1在森林中的一切兄弟之间添加一条连线，一切的根结点以为是兄弟；2保管父点与第一个孩子之间的连线，去掉父点与其他孩子之间的连线； 3将此时树中的程度连线和垂直连线顺时针旋转45，整理成二叉树中的左右子女。 二叉树也可以转化为森林。其转换规那么为：1假设二叉树为空，那么对应的森林为空；2假设二叉树不空，那么森林中第一棵树的根即为二叉树的根，第一棵树根的各个子树为二叉树的左子树对应的森林；森林中其他的树为二叉树的右子树对应的森林。三、

34、树的存储1、双亲表示法 用一组延续的存储空间一维数组存储树中的各个结点，数组中的一个元素存储树中的一个结点，数组元素为构造体类型，其中包括结点本身的信息以及结点的双亲在数组中的序号，树的这种存储方法称为双亲表示法。 0A-11B02C03D04E25F16G27H42. 孩子链表表示法孩子链表表示法将结点的一切孩子用链接方式存储在一个单将结点的一切孩子用链接方式存储在一个单链表中，没有孩子的结点后面的单链表为空。链表中，没有孩子的结点后面的单链表为空。树中结点用顺序方式存储在一个长度为树中结点用顺序方式存储在一个长度为nn为为树中结点数的数组中，数组的每一个元素由树中结点数的数组中，数组的每一

35、个元素由两个域组成，一个域用来存放结点信息，另一两个域组成，一个域用来存放结点信息，另一个用来存放该结点的孩子链表的头指针。单链个用来存放该结点的孩子链表的头指针。单链表的构造也由两个域组成，一个存放孩子结点表的构造也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向在一维数组中的序号，另一个是指针域，指向下一个孩子结点。下一个孩子结点。3. 树的二叉链表孩子树的二叉链表孩子兄弟链表示法兄弟链表示法实践上就是将树转换为对应的二叉树，然后实践上就是将树转换为对应的二叉树，然后再采用二叉链表存储构造。将树转换为对应的再采用二叉链表存储构造。将树转换为对应的二叉树后，树中每个结点

36、的第一个孩子是对应二叉树后，树中每个结点的第一个孩子是对应二叉树中该结点的左孩子，而每个结点的右兄二叉树中该结点的左孩子，而每个结点的右兄弟对应二叉树中该结点的右孩子，所以该方法弟对应二叉树中该结点的右孩子，所以该方法又称孩子又称孩子兄弟链表示法。每个结点除其信息兄弟链表示法。每个结点除其信息域外，再添加两个指针域，分别指向该结点的域外，再添加两个指针域，分别指向该结点的第一个孩子结点和下一个兄弟结点。第一个孩子结点和下一个兄弟结点。 55 哈夫曼树一、哈夫曼树的定义及建立 结点的途径长度就是从根结点到每个结点的途径长度，其值为路经上的结点数减1。赋予了权值的结点的途径长度与该结点权值的乘积即

37、为结点的带权途径长度Weighted Path Length of Node。树的带权途径长度Weighted Path Length of Tree，缩写为WPL定义为：树中一切叶子结点的带权途径长度之和，记为：其中n表示叶子结点数，wi表示第i个叶子结点的权值，li代表第i个叶子结点的途径长度。1ni iiWPLwlWPLa=22+32+62+82=38WPLb=81+62+23+33=35WPLc=21+63+83+32=50WPLd=81+23+33+62=35哈夫曼树哈夫曼树Huffman Tree又称最优二叉树又称最优二叉树，是在含有，是在含有n个叶子结点，权值分别为个叶子结点，权

38、值分别为w1，w2，wn的一切二叉树中，带权途径长度的一切二叉树中，带权途径长度WPL最小的二叉树。最小的二叉树。 哈夫曼D.A.Huffman在上世纪五十年代初便提出了一个非常简单的算法来建立哈夫曼树，其算法描画如下：1将给定的n个权值w1，w2，.，wn作为n个根结点的权值，构造一个具有n棵二叉树的森林T1，T2，.，Tn，其中每棵二叉树只需一个根结点；2在森林中选取两棵根点权值最小的二叉树分别作为左、右子树，添加一个新结点作为根，从而将两棵树合并成一棵树，新根结点的权值为左右子树根结点权值之和。森林中因此也减少了一棵树；3反复上面步骤2的处置过程，直到森林中只需一棵二叉树为止，这棵二叉树

39、就是哈夫曼树。 从哈夫曼树构造过程和生成结果可知，哈夫曼树具有以下特点：1哈夫曼树不独一。 2哈夫曼树中只包含度为0和度为2的结点。 3树中权值越大的叶子结点离根结点越近。例例5.1 假设树中叶子结点的权值为假设树中叶子结点的权值为5，29，7，8，14，23，3，11，构造一棵哈夫曼树。，构造一棵哈夫曼树。1将给定的将给定的8个权值作为根结点，构造具个权值作为根结点，构造具有有8棵树的森林。棵树的森林。2从森林中选取根点权值最小的两棵二从森林中选取根点权值最小的两棵二叉树叉树3、5，分别作为左右子树，构造一棵新的，分别作为左右子树，构造一棵新的二叉树，新树根点权值为二叉树，新树根点权值为8，

40、森林中减少一棵，森林中减少一棵树。树。3反复步骤反复步骤2，直到森林中只剩一棵，直到森林中只剩一棵二叉树为止。二叉树为止。为方便查找双亲，将哈夫曼树的存储构造设计为三叉链表。每个结点包含四个域：weight为结点的权值，lchild、rchild、parent分别为左、右孩子和双亲结点的指针。含有N个叶子结点的哈夫曼树共有2N-1个结点，由此可定义一个长度为2N-1的数组tree来存储哈夫曼树，下标从1开场，0代表指针空NULL。存储构造用C言语描画为：# define N 7 /*叶子结点数*/# define M 2*N-1/*总结点数*/typedef struct/*哈夫曼树结点的存储

41、构造*/float weight;/*结点的权值*/int parent;/*双亲在数组中的下标*/ int lchild,rchild;/*左、右孩子在数组中的下标，叶结点的这两个指针值为0*/ HufmTree ;HufmTree treeM+1;/* 哈夫曼树的静态链表存储构造，下标为0的单元空出*/ weightparentlchildrchild在上述存储构造上实现哈夫曼算法的过程如下：1将哈夫曼树数组tree中的2N-1个结点初始化：即将各结点的权值、双亲、左孩子、右孩子均置为0。2读入N个叶子结点的权值，分别存入数组treei1iN的权值域中，构造包含N棵树的初始森林，森林中的每

42、棵树只需一个根结点。3循环N-1次，对森林中的树进展N-1次合并，产生N-1个新结点，依次放入数组treei中N+1i2N-1。每次合并的步骤是：1在当前森林的一切结点tree j1ji-1中，选取具有最小权值和次小权值的两个根结点parent域为0的结点，分别用p1和p2记住这两个根结点在数组tree中的下标。2将根为treep1和treep2的两棵树合并，使其成为新结点treei的左、右孩子，得到一棵以新结点treei为根的二叉树。即将treei.weight赋值为treep1.weight和treep2.weight之和；treei的左指针赋值为p1；treei的右指针赋值为p2；同时将

43、treep1和tree p2的双亲域均赋值为i，使其指向新结点treei，即它们在当前森林中已不再是根结点。 二、哈夫曼编码及译码 在进展文字传输时，数据通讯的发送方需求将原文中的每一个文字转换成对应的二进制0、1序列编码进展发送，接纳方接纳到二进制的0、1串后再复原成原文译码。其编码和译码的过程如下所示： 原文 电文二进制的0、1序列 原文常用的编码方式有两种：等长编码和不等长编码。 等长编码：ASC码，其特点是每个字符的编码长度一样。编码简单且具有独一性，当字符集中的字符在电文中出现的频度相等时，它是最优的编码。不等长编码：字符的编码长度不等，因此称这种编码方式为不等长编码。为了使译码独一

44、，那么要求字符集中任一字符的编码都不是其他字符编码的前面一部分，这种编码叫做前缀编码。 利用二叉树来对叶子结点进展编码，所得的编码一定为前缀码。假设要使报文总长最短，那么利用哈夫曼树对叶子结点进展编码一定是最优的编码。哈夫曼编码的实现方法如下：1利用字符集中每个字符的运用频度作为权值构造一个哈夫曼树；2从根结点开场，与左孩子的连线标上0，与右孩子的连线标上1；3由根到某叶子结点的路经上的0、1序列组成该叶子结点的编码。 例例5.2 假设有一个字符集包含假设有一个字符集包含8个字符个字符a，b，c，d，e，f，g，h，每个字符的运用频度权值分别为，每个字符的运用频度权值分别为5，29，7，8，1

45、4，23，3，11，为每个字符设计哈夫曼编码。，为每个字符设计哈夫曼编码。字符编码a0001b10c1110d1111e110f01g0000h001哈夫曼编码的实现算法 首先根据字符的权值构建哈夫曼树，然后从每个叶子结点开场不断的向上搜索双亲结点，直到根点为止，得出字符的哈夫曼编码。编码的存储构造及实现算法的C函数描画如下：typedef struct/*哈夫曼编码的存储构造*/char bitsN;/*保管编码的数组*/ int start; /*编码的有效起始位置，从该位置之后的01串为字符的编码 */ char ch; /*字符 */CodeType ;CodeType codeN+1

46、; /*字符编码数组，下标为0的单元空出 */ huffmanCode(HufmTree tree,CodeType code)/*利用哈夫曼树求字符的哈夫曼编码*/int i,c,p; for(i=1;i=N;i+)/*N次循环，分别得到N个字符的编码*/codei.start=N; c=i; p=treei.parent;/*获取字符的双亲*/ while (p!=0)/*不断往上层查找，直到根终了*/ codei.start; if(treep.lchild=c) codei.bitscodei.start =0; else codei.bitscodei.start =1; c=p;

47、p=treep.parent; 3、译码与编码过程相反，译码过程是从哈夫曼树的根结点出发，逐个读入电文中的二进制码，假设读入0，那么走向左孩子，否那么走向右孩子，一旦到达叶结点，便译出相应的字符。然后，重新从根结点出发继续译码，直到二进制电文终了。 decode(HufmTree tree,CodeType code)/* 知哈夫曼树和哈夫曼编码，对输入的01码进展译码 */ int i=m,b;/* treem中保管的是哈夫曼树的根，i=m表示从根点出发进展译码 */ int endflag=-1;/* 标识能否终了 */ int yiflag; /* 标识能否刚好译出一个字符 */ sca

48、nf(%d,&b);/*获取输入的第一个01码 */ while (b!=endflag) /*分析不断输入的01码，依次输出译出的字符，直到遇到终了符为止 */ yiflag=0; if (b=0) i=treei.lchild;/*读入0往左走 */ else i=treei.rchild;/*读入1往右走 */ if(treei.lchild=0)/*走到叶子结点，译出字符 */ printf(%c,codei.ch); i=m;/*重新从根点出发，预备译下一个字符 */ yiflag=1; scanf(%d,&b); if(yiflag!=1 ) printf( nER

49、RORn); /*假设输入的01码序列不规范，那么会提示译码错误 */第六章 图6.1 图的概念图(Graph)是一种结点之间为多对多关系的数据构造。逻辑特征是：可以有恣意个开场结点和恣意个终端结点，其他各个结点可以有恣意个前趋和恣意个后继。图中的结点常称为顶点。图的逻辑构造可以用二元组表示： Graph(V,E) V是顶点(vertex)的集合； E是边(edge)的集合。v有向图有向图(Digraph)假设图假设图G中的每条边都是有中的每条边都是有方向的，那么称图方向的，那么称图G为有向图。为有向图。例 G1 = (V1, E1)V1 = v1, v2, v3E1 = , , G2 = (

50、V2, E2)V2 = v1, v2, v3E2 = , , , , , v无向图无向图(Undigraph)假设图假设图G中的每条边都是没中的每条边都是没有方向的，那么图有方向的，那么图G称为无向图。称为无向图。例 G3 = (V3, E3)V3= v1, v2, v3, v4E3= (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v4)G4 = (V4, E4)V4= v1, v2, v3 E4= (v1, v2), (v1, v3), (v2, v3) v顶点的度v有向图中，顶点的度分成入度与出度v入度：该顶点入边的数目v出度：该顶点出边的数目v

51、无向图中，顶点的度为与该顶点相连的边数v邻接点与关联边v有向图中，假设是有向图中的一条边，那么顶点xv 和顶点y称为邻接点。称x邻接到y或y邻v 接于x，同时称边是顶点x和顶点yv 相关联的边Incident； v无向图中，假设x,y是无向图中的一条边，那么顶点v x和顶点y互为邻接点,并且称边(x, y)是v 顶点 x和顶点y相关联的边。v子图设有图G=(V,E) ，假设满足：vVVvEEvE中边所邻接的点均在V中出现v 那么 G= (V,E)也是一个图，并且称之为G的子图。v有向完全图n个顶点的有向图最大边数是n(n-1)v无向完全图n个顶点的无向图最大边数是n(n-1)/2v途径有向图G

52、=(V,E)中，假设存在一个顶点序列vp,vi1,vi2,vin,vq，使得,均是图中的边，那么称此序列是从顶点vp到vq一条途径。v途径长度该途径上经过边的数目。v回路一条途径第一个顶点和最后一个顶点一样的 叫v简单途径序列中顶点不反复出现的途径叫v简单回路除了第一个顶点和最后一个顶点外，其他顶点不反复出现的回路叫v有根图假设存在一个顶点v，从该顶点到其他各个顶点都有途径，那么称此图为有根图 v连通从顶点x到顶点y有一条途径，那么说x和y是连通的v连通图图中恣意两个顶点都是连通的叫连通图v连通分量无向图G的极大连通子图称为G的连通分量 v强连通图假设G中恣意两个顶点都是强连通的，那么称图G是

53、强连通图 v强连通分量 有向图G的极大强连通子图称为G的强连通分量 v权与图的边相关的数值叫权值。v网络边上带权的图称为网络 6.2 图的存储构造邻接矩阵表示顶点之间邻接关系的矩阵 设G=(V,E是具有n个顶点的图，那么G的邻接矩阵是一个n阶方阵A，A中元素的值aij可以定义为： v特点：v无向图的邻接矩阵对称；有n个顶点的无向图需存储空间为n 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nv无向图中顶点Vi的度是邻接矩阵A中第i行元素之和v有向图中，v顶点Vi的出度是A中第i行元素之和v顶点Vi的入度是A中第i列元素之和v网的邻接矩阵可定义为：可以得到邻接矩阵存储构造C言语描画如

54、下：#define n 5/* 图的顶点数 */#define e 6/* 图的边数 */#define max 10000/* 设置一个极大数无穷大 */typedef char vextype;/* 顶点类型 */typedef int adjtype;/* 权值类型 */typedef structvextype vertexn+1;/* 顶点数组 */adjtype edgen+1n+1;/* 邻接矩阵 */adj_matrix;邻接表邻接表法(Adjacency List)是图的一种链式存储构造 顶点采用顺序方式进展存储，用n个单链表来存储图中的边，第i个单链表是一切与第i个顶点相关

55、联的边链接而成的，称此单链表为第i个顶点的边表，边表中的每个结点称为边表结点。在顶点的顺序表中，每个元素添加一个指针域用来存放各个边表的头指针，称此顺序表为顶点表，而顺序表中的每个元素称为顶点表结点。顶点表和各顶点的边表一同组成图的邻接表。 邻接表存储构造C言语描画如下：typedef struct node int adjvex; /* 邻接点域 */ struct node *next; /* 指针域 */edgenode; /* 定义边表结点 */typedef struct vextype vertex; /* 顶点域 */ edgenode *link; /* 指针域 */vexno

56、de; /* 定义顶点表结点 */vexnode adjlistn+1;v特点v无向图中顶点Vi的度为第i个单链表中的结点数v有向图中v顶点Vi的出度为第i个单链表中的结点个数v顶点Vi的入度为整个单链表中邻接点域值是i的结点个数v逆邻接表：有向图中对每个结点建立以Vi终点的单链表边集数组边集数组(edgeset array)(edgeset array)是图的一种顺序存储方式，利用一维数组是图的一种顺序存储方式，利用一维数组来存储图中一切的边，数组中的每个元素用来存储图中的一条边，包来存储图中一切的边，数组中的每个元素用来存储图中的一条边，包括：始点、终点的序号及权值，该数组中所含元素的个数

57、要大于等于括：始点、终点的序号及权值，该数组中所含元素的个数要大于等于图中边的条数。图中边的条数。 边集数组邻接表法(Adjacency List)是图的一种链式存储构造 typedef struct edge int fromvex; /* 边的始点域 */int endvex; /* 边的终点域 */int weight; /* 边的权值域 */edgeset; /* 定义边集数组类型 */edgeset gee+1; /* 边集数组全局量 */ 6.3 图的遍历 深度优先遍历(DFS) 方法：对于给定的图G，假设初始时一切顶点均未被访问过，那么可从G中任选一顶点vi做为初始出发点，深度优

58、先搜索可定义为：访问出发点vi，置访问标志为1，然后依次从vi的未被访问过的邻接点vj出发，继续进展深度优先搜索，直至图中一切和vi有途径相通的顶点均被访问过。很显然图的深度优先搜索过程是递归的。它的特点是尽能够先对图从纵深方向进展搜索，故称为深度优先搜索。 DFS序列为：v1，v2，v4，v8，v5，v3，v6，v7。 v深度优先遍历算法v递归算法void DFS(int i) int j;printf (输出序号为输出序号为%d的顶点的顶点: %cn,i,adj-vertexi); visitedi=1; /* 标志标志vi曾经访问过曾经访问过 */for (j=1;jedgeij)&am

59、p;(!visitedj)DFS(j);void DFSL(int i) edgenode *p; printf(输出序号为%d的顶点: %cn,i,adjlisti.vertex); visited i=1; /* 标志vi曾经访问过 */ p=adjlisti.link; /* p为vi的边表头指针 */ while (p) /* 依次搜索vi的邻接点 */ if(!visitedp-adjvex) DFSL(p-adjvex); p=p-next; 在邻接矩阵上实现遍历的过程： 生成树连通图G的一个子图假设是一棵包含G的一切顶点的树，那么该子图称为G的生成树(Spanning Tree)

60、 。广度优先遍历(BFS)方法：对于给定图G，假设初始时的一切顶点均未被访问过，从图G中任选一顶点vi为初始出发点，广度优先搜索遍历可定义为：首先访问出发点vi，接着依次访问vi的一切的邻接的未被访问过的点w1， w2, wt，然后，再依次访问与w1，w2,wt相邻接的未被访问过的顶点。依此类推，直至图中一切和初始出发点vi有途径相通的顶点都已访问到为止。显然，此方法的特点是尽能够先对横向进展搜索，故称之为广度优先搜索。 BFS序列为：v1，v2，v3，v4，v5，v6，v7，v8 v广度优先遍历算法 在广度优先遍历中，先被访问的顶点，其邻接点亦先被访问，所以在算法的实现中需求运用一个队列，用来依次记住被访问过的顶点。 算法开场时，将初