数据结构(中)课件

1、数据结构(中)1第6章 树与二叉树第7章 图2第六章 树与二叉树3学习重点： 树的定义及其基本术语 二叉树的定义及性质 二叉树的存储方法 二叉树的遍历 树的存储方法 树的遍历 二叉树与树、森林的转换 二叉树的应用 46.1 树的概念及术语6.2二叉树6.3二叉树的遍历6.4 二叉树与树、森林的转换6.5 树的存储结构6.6 树的遍历6.7 二叉树的应用56.1 树 的 概 述 所谓“树（Tree）”是指由n（n0）个结点构成的有限数据元素的集合T。当n=0时，称其为“空树”。当n0时，树中诸结点应该满足下面的两个条件： 6.1.1 树的定义6（1）有且仅有一个特定的结点，它没有前 驱，是该树的

2、根，称为树的根结点；（2）除根结点外的其余结点，可分为m （m0）个互不相交的有限集合：T1， T2，Tm，每一个集合Ti（0im） 又是一棵树，被称为是根的子树。 7有关树的术语（1）结点：它不仅有数据本身，还有指向其孩子的若干分支 孩子结点：某结点的各子树的根，称为这个结点的孩子结点 双亲结点 兄弟结点：有相同双亲的孩子称为兄弟结点 祖先结点：从根结点到该结点的双亲结点，都是此结点的祖先结点 8有关树的术语（2）结点的度：指该结点的子树的个数 叶子结点：度为0的结点，也称为终端结点 分支结点：度不为0的结点，也称为非终端结点 树的层数：树的根所在结点的层数为1，其他结点的层数等于它的双亲结

3、点的层数加1 9有关树的术语（3）树的深度：树中结点的最大层数称为树的深度（也称高度） 森林：零棵或有限棵互不相交的树的集合称为森林 有序树和无序树：如果树中结点的各子树从左到右是有次序的（即位置不能互换），那么这样的树称为有序树；否则是无序树。 106.1.2 树的基本操作1初始化一棵空树；2销毁一棵已存在的树；3求树的根结点；4求结点的的双亲结点；5求树的深度；6前序遍历树；7中序遍历树；8后序遍历树；9层序遍历树。116.1.3 树的表示方式（A（B（E，F），C（G），D（H，I（K），J）（c）树形表示法 (d) 广义表表法法图6.4 二叉树的表示126.2二叉树二叉树，它是一种非常

4、重要的非线性数据结构，有着广泛的用途。主要介绍以下几个方面的内容： 二叉树的定义及性质； 二叉树的存储实现（顺序和链式存储）； 遍历二叉树（即对二叉树存储结点访问的各种形式）； 哈夫曼树及编码。136.2.1 二叉树的定义 所谓“二叉树”，是一个由结点组成的有限集合。这个集合或为空，或由一个称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为根结点的左子树和右子树。14二叉树有如下的特征：二叉树可以是空的，空二叉树没有任何结点；二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的； 二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。15图6.6 二叉树的五种基本形态(a)

5、 (b) (c) (d) (e)166.2.2 二叉树的重要性质性质1:在任何一棵二叉树的第i（i1）层上，最多有2i-1个结点【证明】二叉树的第1层只有一个结点。所以，当i=1时，2i-1=20=1成立。 假设结论对第i层成立，即第i层最多有2i-1个结点。由于二叉树每个结点的度最多为2，因此第i+1层结点的个数，最多应该是第i层结点个数的2倍，即22i-1 = 2i，命题得证。17性质2: 树高为k（k1）的二叉树，最多有2k1个结点。 【证明】由性质6-1可知，在树高为k的二叉树里，第1层有20个结点，第2层有21个结点，第3层有22个结点，第k层有2k-1个结点。因此，要求出树高为k的

6、二叉树的结点个数，就是求和： 20 + 21 + 22 + 2k-1=2k-1.证毕18 性质3:如果一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有关系：n0 = n2 + 1。 【证明】设二叉树中度为1的结点个数为n1，那么二叉树总的结点个数n应该是： n = n0 + n1 + n2（1）19 另一方面，二叉树中除根结点外，其余每个结点都有一个向上的分支指向其父结点。如设二叉树种分支边数为m，那么二叉树总的结点个数n应该是分支边数m加上1（这个1是根结点），即： n = m + 1 （2）20 注意到每一条分支边或是由度为1的结点发出，或是由度为2的结点发出，度为1的结

7、点发出一条边，度为2的结点发出两条边。因此，又有关系： m = n1 + 2n2 （3） 把式（3）代入式（2），得： n = n1 + 2n2 + 1 （4） 综合式（1）和式（4），立即可以得出所需要的结论。21两种特殊形态的二叉树满二叉树：深度为k并且含有2k-1个结点的二叉树称，如图6.7所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图6.7中每个结点上的数字即是该结点的编号。完全二叉树：深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时，则称此二叉树为完全二叉树，如图6.8所示。22图6.7 满二叉树 图6.8 完全二

8、叉树 23性质4:具有n个结点的完全二叉树树深为 +1（其中 表示不大于x的最大整数）。【证明】假设某完全二叉树的结点总数是n ，它的值应该大于树深为K-1的满二叉树结点数2k-1-1，小于等于树深为K的满二叉树结点数2k-1。 2k-1-1 n 2k-124由于该不等式各项均为整数，当对两端两项各加1时不等式发生变化得： 2k-1 n 2k 再对其取对数得： k-1 log2n 1时，该结点的双亲结点编号为 ；若2in，它有编号为2i的左孩子，否则没有左孩子； 若2i+1n，则它有编号为2i+1的右孩子，否则没有右孩子。276.2.3 二叉树的存储结构1. 顺序存储结构 将二叉树的所有元素放

9、在一维数组之中。这是最简单的顺序存储结构。 #define MAXLEN 20 typedef char DataType; DataType btMAXLEN ; 其中，bt是一维数组，每个数组元素存储树的一个结点的数据信息。我们假定让0号位置（即bt0）空置不用，从1位置开始存储二叉树的所有元素。我们按照完全二叉树上编号自上而下、从左至右的顺序将每个元素存入数组当中。 28如左图中的完全二叉树存入到数组中，可以很容易地看到第i个结点及其双亲和左、右孩子结点2i 、2i+1的存储位置。 29若二叉树为一棵单边树如图6.9所示，要如何存储？虽然此二叉树只有四个结点，但对于任何一棵二叉树来说，都

10、有插入新的结点的可能。依然要保留其存储空间。即可见，对于四个结点的单边树，要开辟8个存储空间来存储。若有一棵深度为K的二叉单边树，那么至少有2k个存储空间，则有2kK个空间为空，这样有许多空间浪费了。这种存储结构适合用于存储完全二叉树、满二叉树。一般的二叉树较少采用这种存储结构。302链表存储结构 二叉树的链表结构，常见的有二种：二叉链表和三叉链表。由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的指针组成，如图6.10（a）所示。31根据结点的定义，二叉链表的每个结点有一个数据域和两个指针域，一个指向其左孩子，一个指向其右孩子，见图6.10（b）。其结点结构描述如下：st

11、ruct node Datatype data; /*数据域*/ node *lchild; /*指向其左孩子的指针域*/ node *rchild; /*指向期右孩子的指针域*/32 可使用三叉链表。它是比二叉链表多了一个指向其双亲的指针域，如图6.10（c）所示。其结点描述如下：struct node3 Datatype data; /*数据域*/ node3 *lchild; /*指向其左孩子的指针域*/ node3 *rchild; /*指向其右孩子的指针域*/ node3 *parent; /*指向其双亲的指针域*/33346.3 二叉树的遍历所谓遍历是指按一定的次序将每个元素都访问

12、一遍，且只能访问一次。访问是指对结点进行各种操作的简称，包括输出、查找、修改等等操作。在线性结构中我们没有提出遍历的概念及说法，因为线性结构相较而言比较简单，元素之间只存在有前后的次序问题，访问操作我们只限定在在了输出操作上，即按从前到后的顺序逐个输出.35遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。36遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。对于二叉树结构来讲，元素之间的关系不再是简单的先后关系，每个结点都可以有两棵子树（后继）。如何遍历呢？ 37二叉树的是由

13、三个单元组成：根结点（T）、左子树（L）、右子树（R）。若能依次遍历这三个部分，就是遍历了整个二叉树。按我们从左至右的习惯，我们可以有三种遍历方案，即根左子树右子树（TLR）；左子树根右子树（LTR）；左子树右子树根（LRT）。分别称之为先序遍历，中序遍历，后序遍历 38例如有一棵二叉树它有4个结点。为了便于理解遍历的思想，暂且为每个没有子树的结点均补充上相应的空子树，用来表示，见图6.12。设想有一条搜索路线（用虚线表示），它从根结点的左侧开始，自上而下自左至右搜索，最后由根结点的右侧向上出去。不难看出，若考虑到空子树的话，恰好搜索线途经每个有效的树结点都是三次。 39把搜索线第一次经过就访

14、问的结点列出，它们是A、B、C、D，这就是先序遍历的结果。那么搜索线第二次经过才访问的则是中序遍历，其结果是B、A、D、C。搜索线第三次经过才访问的就是后序遍历，结果是B、D、C、A。 406.3.1 先序遍历 先序遍历二叉树递归定义为： 若二叉树根空，则返回； 否则：（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。41先序遍历递归算法如下：void fstorder(Bnode *p) if(p!=NULL) printf( %6c,p-data); /*访问根结点*/ fstorder (p-lch) ; /*对左子树按先序遍历进行*/ fstorder (p-rch);

15、 /*对右子树按先序遍历进行*/ 42先序遍历递归调用的执行过程如下: 436.3.2中序遍历中序遍历二叉树递归定义为： 若二叉树根空，则返回； 否则：（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 44中序遍历递归算法如下： void middleorder(Bnode *p) if(p!=NULL) middleorder(p-lch) ; /*对左子树按中序遍历进行*/ printf( %6c,p-data); /*访问根结点*/ middleorder(p-rch);/*对右子树按中序遍历进行*/ 456.3.3 后根遍历后根遍历可以递归的定义为： 如果根不空: (

16、1) 按后根次序遍历左子树； (2) 按后根次序遍历右子树； (3) 访问根结点； 否则返回。46后根遍历递归算法如下： void lastorder(Bnode *p) if(p!=NULL) lastorder(p-lch) ; /*对左子树按后先序遍历进行*/ lastorder(p-rch); /*对右子树按后先序遍历进行*/ printf( %6c,p-data); /*访问根结点*/ 476.3.4 按层遍历按层遍历引入了队列作为辅助工具。算法思想为：（1）将二叉树根入队列；（2）将队头元素出队列，并判断此元素是否有左右孩子，若有，则将它的左右孩子入列，否则转（3）；（3）重复步骤

17、（2），直到队列为空 48viod levelorder(Bnode *p) Bnode *q20; front= rear=0; /*/队头与队尾指针*/ if( p!=NULL) rear+; qrear=p; /*根结点不空，进队 */ while ( front!=rear) front +; p=qfront; printf(“%6c”,p-data); /*出队并访问该队头元素 */ if( p-lch!=NULL) rear+; qrear=p-lch; /* 若左孩子不空，进队*/ if( p-rch!=NULL) rear+; qrear=p-rch; /*若右孩子不空，进队

18、*/ 496.3.5 非递归遍历算法递归算法简明精练，但效率较低。因为系统需要维护一个工作栈以保证递归函数的正确执行。在实际应用中往往会用到非递归方法。在某些高级语言中，没有提供递归调用的语句及功能。为了提高程序设计的能力，有必要进行由递归方法到非递归方法的基本训练。非递归算法的关键问题在于如何实现由系统完成的递归工作栈。此时，可人为地设置栈来仿照系统工作栈的工作过程。501前序遍历的非递归算法 对递归方法执行的分析可看出，每进行一次深层次调用都需保留当前调用层上的一些信息，主要是指向根结点的指针。 在先序遍历的非递归算法中。设置一个栈S来存放所经过的根结点的指针。为了在访问完某个结点及其左子

19、树后，方便地找到此结点的右子树. 所以，在访问完某个结点后，将该结点的指针保存在栈中. 51先序非递归的过程如下: （1）设置一个空栈。 （2）若二叉树不空，访问根结点，并将其指针入栈，然后遍历它的左子树。 （3）左子树遍历结束后，若栈不空，将栈顶元素出栈，遍历栈顶元素的右子树。直至栈空为止。 52先序遍历非递归算法如下：void fstorder(Bnode *p)top=-1; /*空栈*/while(p!=NULL|top!=-1) while(p!=NULL) printf(“%6c”,p-data); top+; stop=p; p=p-lch; if(top=-1)p=stop;

20、top-; p=p-rch; 532中序遍历的非递归算法中序遍历与前序遍历不同之处在于第一次遇到根结点时，并不访问，而是去遍历其左子树，当左子树遍历结束后，才访问根结点，那么，中序的非递归算法当中，可将根指针先入栈，当其左子树遍历完毕后，再从栈中弹出并访问它。 54中序非递归遍历算法如下：void middleorder(Bnode *p)top=-1; /*空栈 */while(p!=NULL|top!=-1) while(p!=NULL) top+; stop=p; p=p-lch; if(top=-1)p=stop; printf(“%6c”,p-data); top-; p=p-rch

21、; 55&A&A&B&A&C&C&D&C遇根A其地址进栈遍历A的左子树遇根B其地址进栈遍历B的左子树B的左子树为空；出栈访问BB的右子树为空出栈访问A遍历A的右子树遇根C其地址进栈遍历C的左子树遇根D其地址进栈遍历D的左子树D的左子树为空；出栈访问DD的右子树为空出栈访问C；C的右子树空；栈空结束。图6.14 二叉树的中序非递归栈563. 后序遍历非递归算法后序遍历当中，二叉树的根结点需要其左右子树都遍历结束后才访问，其非递归算法较复杂些。除之前所需的栈，另需一个辅助栈s2用来记录经过某根结点的次数。两个栈的类型： Bnode *s10；int s220；57void lastorder(Bn

22、ode *p) qp； top0； bool1； printf(“n 后根遍历: n”) do while (q!NULL) top+； stopq； s2top1； qq-lch; if (top=0) bool0； else 第二次及第三次经过栈的操作 while bool； printf(“n”); 中序非递归遍历算法如下：58/*第二次及第三次经过栈的操作*/ if(s2top=1) s2top2； /* 第2次经过，不出栈 */ qstop； qq-rch； else qstop；/* 第3次经过，出栈并且访问结点 */ s2top0；top-； printf(“6c”，q-data

23、)； qNULL； 596.3.6 二叉树的建立在此，介绍两种创建二叉树的方法。1、利用二叉树的性质5。2、递归建立二叉树601、利用二叉树的性质5 根据二叉树的性质5，对任意二叉树，先将其补全为满二叉树，并对每个结点进行编号，再去掉所有补上结点，得到每个结点的编点。如图6.15 (a)所示。61 由于此树并非完全二叉树，所以结点的编号并不连续。算法中使用一个辅助向量s用于存放树结点的指针（即地址），如si中应该存放编号为i的结点的地址指针。此例原始数据序列如图6.15(b)所示，照此一一输入即可生成二叉链表。 62其生成过程如下：当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指

24、针存入s1。当结点编号i1时，产生一个新的结点之后，也要将指向该结点的指针存入si。由性质5可知：j=i/2 为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让sj-lch = si；如果i为奇数，则它是双亲结点的右孩子，即让sj-rch = si。 63结点存储结构如前所描述为Bnode ，辅助向量：Bnode *s20。二叉树生成算法如下：Bnode *creat() Bnode *t=NULL; printf(n i,x=);scanf(%d%d,&i,&x); while (i!=0)&(x!=0) q=(struct node*)malloc(sizeof(struct

25、node); /* 产生一个结点 */ q-data=x; q-lch=NULL; q-rch=NULL; si=q; if (i=1) t=q; /* q为树根结点 */ else j=i/2; /* j为双亲结点编号 */ if (i%2)=0) sj-lch=q; else sj-rch=q; printf(n i,x=);scanf(%d%d,&i,&x); returu t; 642、递归建立二叉树 我们按先序递归遍历的思想来建立二叉树。其建立思想如下：（1）建立二叉树的根结点；（2）先序建立二叉树的左子树；（3）先序建立二叉树的右子树。65 算法描述如下： Bnode *creat

26、() Bnode *p; scanf(%d, &x); /*输入结点的数据域*/ if(x=0) p=NULL; elsep=(Bnode *)malloc(sizeof(Bnode); p-data=x; /*建立根结点*/ p-lch=creat(); /*建立左子树*/ p-rch=creat(); /*建立右子树*/ return p; 66问题：了解了二叉树,二叉树的遍历,那么二叉树遍历可以在哪里可以用得上呢？ 676.3.7 二叉树遍历的应用举例利用二叉树遍历算法的思路，若访问结点的操作不局限于输出结点的数据域的值，而将访问扩展到结点的判别、计数等等操作。可以解决关于二叉树其他实际

27、问题。本小节主要利用二叉树的递归遍历来实现。 681统计二叉树的叶子结点的数量 叶子结点是指那些没有左子树，也没有右子树的结点。那么，先设置一个计数器m，记录叶子结点的数量，那么，可以在遍历的过程中，判断结点是否为叶子结点，是，则计数量m加1，这样，直到遍历结束，就可以得到叶子结点的数量。69以先序遍历方法统计叶子结点的数量，其算法如下：void numofleaf(Bnode *p, int *m) if(p!=NULL)if(p-lch=NULL&p-rch=NULL) /*叶子结点左、右子树为空*/ (*m)+; numofleaf(p-lch,m); numofleaf(p-rch,m

28、); 70这里，m作为引用型形参，每一次递归调用时，都可以实时记录叶子结点的个数。相应的主调函数示意如下： main() Bnode *t; t=creat(); /* 建立二叉树t */ m=0; /* 全局变量m置初值 */ numofleaf(t,m); /* 求树t叶子结点的个数m */ printf(n m=%4d,m); /* 输出结果 */ 712求二叉树的树深在6.1节中，我们介绍了树深。我们除了计算二叉树结点所处的最大层次数之外，树的深度也可以这样得到：设二叉树根所在结点的深度为1，比较其左子树和右子树的深度，取其深度的最大值N，那么树的深度为N加1。可以利用二叉树的先序、中

29、序或后序遍历的思路来完成， 72其算法如下：int fstdepth( Bnode *p) if(p=NULL) return 0; elseint dl=fstdepth(p-lch); /*左子树的深度 */ int dr=fstdepth(p-rch); /*/右子树的深度 */ return 1+(dldr?dl:dr); /*树的深度 */ 73 相应主调函数如下： main()Bnode *t; t=creat(); h=fstdepth(t); printf(”树深度为%d”,h);746.4 二叉树与树、森林的转换我们着重介绍了二叉树，而本章的主题内容是树与二叉树，那么，树与二

30、叉树之间有什么联系呢？ 756.4.1 树与二叉树的转换1、树转换成二叉树，其方法为： （1）加线在树中所有相邻的兄弟之间加一条线段。 （2）抹线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点的连线。 （3）调整以每一个结点为轴心，将其右侧所有结点按顺时针转动45度，使之成为一棵二叉树。其转换过程如图6.14所示。76（a）原来的树 （b）加线 图6.14 树转换成二叉树77（c）抹线 （d）调整图6.14 树转换成二叉树注意：由于树的根结点没有右兄弟，所以转换后，二叉树根结点的右子树一定为空 782、二叉树转换成树，其方法为： 树与二叉树的转换是可逆的，将二叉树转

31、换为树的方法依然是三步，具体如下： （1）加线若某结点是其双亲结点的左孩子，则把该孩子的右孩子、右孩子的右孩子、，都与该结点用线连起来。 （2）抹线删去二叉树中所有双亲结点与右孩子结点的连线。 （3）调整把虚线改为实线，把结点按层次排列。 图6.15给出了二叉树转换为一般树的过程。 79（a）二叉树 （b）加线 图6.15 树转换成二叉树80 （c）抹线 （d）调整 图6.15 树转换成二叉树816.4.2 森林与二叉树的转换森林是树的集合。既然树可以与二叉树互相转换，那么森林是否可以与二叉树进行转换呢？若是可以，该如何操作呢？ 821、森林转换为二叉树 我们知道，当一棵树转换为二叉树时，此二

32、叉树是没有右子树的。现在，我们就来利用这个空的右子树的位置。转换方法如下： （1）转换将森林中的每棵子树转换成二叉树，我们可以给每个二叉树进行编号为第1、2、3、n棵二叉树。 （2）加线在所有的二叉树的根结点之间加一条连线，即依次将第i+1棵二叉树作为第i棵二叉树的右子树。 图6.16是将一个森林转换成一棵二叉树的例子。83(a) 一般树的森林(b) 二叉树的森林84(c) 第二棵子树并入第一棵子树(d) 最终的二叉树852、二叉树转换为森林其具体步骤为：（1）抹线将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森

33、林。 （2）还原将每棵二叉树按二叉树还原一般树的方法还原为一般树。于是得到森林。你能画出这个森林吗?86问题：从6.4节当中，我们了解到二叉树与树、森林的转换。这是在逻辑关系上的转换，那么为什么我们一定要转换呢？它的实际意义是什么呢？ 876.5 树的存储结构对于树来说，树中结点这间的逻辑关系是一个双亲结点，可能有多个孩子，我们该如何将树存储在计算机中呢？是否仍然可以用顺序存储和链式存储呢？ 886.5.1 树的双亲表示 由树的定义可知，树中每个结点都有且仅有一个双亲对点，按这个特点，在每个数组元素中存放一个结点信息和其双亲结点的下标位置。这种存储方式叫做双亲表示法。数组元素的表示如下： 其中

34、：data域，用来存储结点信息； parent域，用来存储该结点的双亲在数组中的下标位置。data parent89 图6.17表示了左图的双亲表示法 图6.17 树的双亲表示法 906.5.2 孩子表示法树的孩子表示法是一种基于链表的存储方法。可称之为多重链表表示法，即结点中的每个指针域指向一个孩子。因为树的每个结点度是不同的，我们可以让结点的指针域的数量等于树的度，其结点结构为：91图6.18给出了左图所示的树采用多重链表表示法的存储示意图 图 6.18 多重链表表示法92从图中可以看出，空链域的数量会比较多，如果出现树的度很大，假如树的度为12且只有一个结点的度为12，其他大多数的结点度

35、很小，只为1。那么空链域会更多，就会造成浪费空间。936.5.3 孩子兄弟表示法孩子-兄弟表示法是树最常用的表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。树的孩子兄弟表示法又称为二叉链表表示法。构成孩子兄弟二叉链表的结点结构是：一个数据域和两个指针域，一个指针指向它的长子，另一指针指向它的一个兄弟。其结点结构为：94左图中树的孩子-兄弟二叉链表结构如图6.19(a)所示 图6.19 树的孩子兄弟表示示意图(a) 95假设把图6.19(a)中指向兄弟的水平方向指针改为下斜45，如图6.19(b)，不难发现它与一棵二叉树十分相似。由本章第6.2节可知二叉树结构规范、简单并具

36、有一些重的要性质，因此常将一般树结构转换为二叉树结构进行处理。966.6 树的遍历 树和森林又都与二叉树可以互相转换，转换的依据是树和森林的孩子兄弟存储表示。因此，根据二叉树遍历的思想可以实现树和森林的遍历。树和森林选用孩子兄弟链表存储结构，它的结点的结构如下：typedef struct node char data; struct node * firstchild; /* 指向第一个孩子*/ struct node *nextsilbing; /*指向下一个兄弟 */ CSnode;976.6.1 一般树的遍历1树的先序遍历 对一般树进行先序遍历，首先访问树的根结点，然后从左至右逐一先序

37、遍历根的每一棵子树。 98树的先序遍历递归该算法如下：void preordertre(CSnode * root) /* root 一般树的根结点 */ if(root!=NULL) printf(“%6c”,root-data); /* 访问根结点 */ preordertre( root- firstchild); preordertre( root- nextsilbing); 992树的后序遍历对一般树进行后序遍历，首先从左至右逐一后序遍历树根的每一棵子树，最后访问树的根结点。由于一般树转换为二叉树后，此二叉树没有右子树，对此二叉树的中序遍历结果与上述一般树的后序遍历结果相同。 10

38、0树的后序遍历递归算法：void postordertre(CSnode * root) /* root 一般树的根结点 */ if (root!=NULL ) postordertre( root- firstchild); printf(“%6c”,root-data); postordertre( root- nextsilbing); 1013树的按层遍历本算法运用队列做辅助存储结构。其步骤为：首先将树根入队列；出队一个结点便立即访问之，然后将它的非空的第一个孩子结点进队，同时将它的所有非空兄弟结点逐一进队；重复，这样便实现了树按层遍历。 102按层遍历算法如下：void levelt

39、raverse(CSnode * root) CSnode *q20; /* 辅助队列，假设树结点不超过19个 */ front=0; rear=0; /* 置空队列 */p=root; printf(“n ”); if(p!=NULL)rear+;qrear=p; /* 根结点进队 */ while(front!=rear) front+; p=qfront; /* 队首结点出队，并访问 */ printf(“%6c”,p-data); if(p- firstchild!=NULL) rear+; /* P第一个孩子，不空则进队 */ qrear=p- firstchild; /* 再找p的

40、一个个兄弟结点，不空则进队 */ while(p- firstchild!=NULL) rear+; qrear=p- nextsilbing;p=p- nextsilbing; /* 当队列为空时，结束循环 * / 1036.6.2 森林的遍历森林有两种遍历方法：（1）前序遍历森林：前序遍历森林中的每一棵树。（2）后序遍历森林：后序遍历森林中的每一棵树。104例如右图中的森林，前序遍历的序列为：A，B，C，D，E，F，G，H，I，J；其后序遍历的序列为：B，C，D，A，F，E，H，J，I，G。1056.7 二叉树的应用 树结构可以用来表示集合，应用比较广泛。它可以用于通信及数据传送中的二进制

41、编码、判定和决策、信息的检索和排序等 。1066.7.1 哈夫曼树路径、路径长度：从树一个结点到另一结点的分支构成两个结点之间的路径，路径上的分支的数目称为路径长度。树的路径长度：从根到树中每个结点路径长度。树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和。哈夫曼树：设有n个权值 ，构造一个具有n个叶子结点的二叉树，每个叶子结点带有权值，在所有的二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。107例如：给定中子结点的权值分别2，3，4，5，可以构造出形状不同的多个二叉树，如图6.20所示。 图6.20 不同带权路径长度的二叉树 1086.7.2 哈夫曼树的构造建立哈夫曼树

42、的方法如下：1根据已知的n个权值 ，首先构造n棵二叉树，每棵二叉树只有一个根结点，根结点的权值是，得到一个由n棵二叉树的集合F 。2在集合F中选取两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，新二叉树根结点的权值为两棵二叉树的根结点权值之和。1093在集合F中去掉两棵树，并将新建立的二叉树加入到集合F中去。4重复步骤2和3，直到F集合中只剩下一棵二叉树为止。 这棵二叉树即所求的哈夫曼树 110已知权值 W= 5, 6, 2, 9, 7 ，哈夫曼树的构造过程如下： （b）（a）111（c）（d）112（e）113注意：在上述例子中，我们没有指定新生成的二叉树的左、右子树是的权值是左大

43、右小，还是左小右大；也没有指定当出现两个权值相同时，先选哪个。所以，我们在构造一棵哈夫曼树时，其形态可能有多个，但若是指明了具体算法时，其形态就会唯一。 1146.7.3 哈夫曼树的实现算法讨论顺序存储结构下哈夫曼树的实现 .因为哈夫曼树中没有度为1的结点。由二叉树的性质2可知n0n21，而现在结点总数为02，也即201。如果叶子数0用n来表示，则二叉树结点总数为2n1，向量的大小就定义为2n1 115假设n10，存储结构如下： typedef struct int data； /* 权值域*/ int lch，rch； /*左、右孩子结点在数组中的下标*/ int tag； /* tag=0

44、 结点独立；tag=1 结点已并入树中*/ huff huff h20；116首先将所有叶子的权值输入向量h的data域中，并将lch，rch，tag域全置零。如前例中的权值 5, 6, 2, 9, 7 ，其初始化如表6-1所示，并按哈夫曼树的构造过程，最后结果如表6-2所示。117118int hufftree (huff h20) scanf(“n n=%d”，&n)； /* n为叶子结点的个数 */ for(j=1；j=n； j+) scanf(“%d”，&rj.data)； hj.tag0；hj.lch0； hj.rch0； i0；/*合并n-1次*/hx1.tag=1； hx2.ta

45、g=1； i+； hn+i.data=hx1.data+ hx2.data； /* m1+m2 */ hn+i.tag=0； hn+i.lch=x1； hn+i.rch=x2； t=2*n-1； return (t)； 119 while (in-1) /* 合并n-1次 */ x1=0； m1=32767； /* m1是最小值单元，x1为下标号 */ x2=0； m2=32767； /* m2为次小值单元，x2为下标号 */ for(j=1； j=n+i； j+) if (hj.datam1)&(hj.tag=0)） m2=m1； x2=x1； m1=rj.data；x1=j； else i

46、f (hj.datam2)&(hj.tag=0) m2=hj.data; x2=j; 1206.7.4 哈夫曼编码假定有一段电文，其中使用了5个字符Q、T、L、N、P，它们在电文中出现的次数分别为5、6、2、9、7。由它们所构造的哈夫曼树如6.21（e）所示。在树中让所有左分支的编码为0，右分支的编码为1，将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得到这个叶子结点所代表的字符的二进制编码，如图6.22所示。121图6.22 哈夫曼编码122本章小结树与二叉树属于非线性结构。除根以外，每个结点只能有一个前驱，除叶子结点外，每个结点都可以多个后继（即孩子结点）。二叉树是度至多

47、为2的有序树，有严格的左右之分，称之为左子树和右子树，二叉树的存储也有两类：顺序存储结构：适用于满二叉树和完全二叉树存储；链式存储结构。适合一般树的存储。分为二叉链表和三叉链表。123二叉树的遍历操作分为：先序遍历、中序遍历、后序遍历以及按层遍历。前三种可使用递归及非递归思想设计算法。后一种需要借助队列完成算法。遍历的实质是按某种规则将二叉树中的数据元素排列成一个线性序列。树、森林可以与二叉树相互转换。以便于利用二叉树的运算思想来完成树、森林的操作。哈夫曼树是二叉树的一种应用。124第7章 图7.1 图的基本概念7.2 图的存储结构7.3 图的遍历7.4 生成树与最小生成树7.5 最短路径7.

48、6 拓扑排序1257.1 图的基本概念7.2图的存储结构7.3 图 的 遍 历7.4生成树与最小生成树7.5最 短 路 径7.6 拓 扑 排 序 126 图是一种比树更为复杂的非线性结构。在图状结构中，任意两个结点之间都可能具有邻接关系，即在图的数据元素之间存在多对多的关系。 127 本章主要介绍以下几个方面的内容： 图的定义及常用术语； 图的各种存储结构； 图的遍历； 构造最小生成树的算法； 求最短路径的算法； 拓扑排序及其算法。1287.1 图 的 基本概念 在讲述图时，习惯把数据元素统称为是顶点。 “图”是图状结构的简称，它由一个非空的顶点集合V和一个描述顶点之间邻接关系的边集合E组成，

49、E中每条边连接的两个顶点都必须属于集合V。于是，一个图可以记为： G =（V，E） 7.1.1 图的定义129对于一个图G来说，边的集合E可以是空的。若vi、vj是V集合中的两个顶点，且有边连接，那么就用记号（vi，vj）表示顶点vi到顶点vj之间的边。通常，边是没有方向的，即若图G中有边（vi，vj），那么也可以说有边（vj，vi）。当图中的边不带有方向时，称该图为“无向图”。130 若图中的边是有向的，这样的图被称为“有向图”。在有向图中，有边（vi，vj），并不意味着也有边（vj，vi）。常称有向图的边为“弧”，把有向图中从顶点vi到顶点vj的弧记为，而把从顶点vj到顶点vi的弧记为，这

50、是两条不同的弧。由于有向图的弧是有方向的，因此常称弧的起始顶点为“弧尾”，弧的终止顶点为“弧头”。 131图7-1 无向图和有向图1321顶点的度、入度、出度 7.1.2 有关图的常用术语 无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，则表明顶点vi和vj互为邻接点，简称vi与vj相邻接。所谓顶点vi的“度”，是指与它相邻接的顶点的个数，记为D(vi)。 133 在有向图中，以顶点vi为弧尾的弧的个数，称为顶点vi的“出度”，记为OD(vi)；以顶点vi为弧头的弧的个数，称为顶点vi的“入度”，记为ID(vi)。这时，一个顶点vi的度是指它的入度与出度之和，即：D(vi)=ID(v

51、i)+OD(vi)。134 在无向图G中，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个边的序列：（vi, vi1），（vi1, vi2），（vim,vj） 其中顶点vi、vi1、vi2、vim、vj属于G的顶点集合V，边（vi, vi1）、（vi1, vi2）、（vim, vj）属于G的边的集合E。2路径、路径长度135 对于有向图G，所谓从顶点vi到顶点vj的一条“路径”，是指在顶点vi与顶点vj之间存在有一个弧的序列： ， 其中顶点vi、vi1、vi2、vim、vj属于G的顶点集合V，弧、属于G的弧的集合E。136所谓顶点vi到顶点vj的路径“长度”，是指

52、在这条路径上拥有的边的个数。137 若在一条路径上出现的顶点都不同，那么这条路径称为“简单路径”；若一条路径的第一个顶点和最后一个顶点相同，其他顶点不重复出现，那么这条路径称为“简单回路”；若一条路径的第一个顶点和最后一个顶点相同，那么这条路径称为“回路”，有时也称作“环”。3简单路径、简单回路、回路138 若一个有n个顶点的无向图，拥有n(n1)/2条边，那么就称该图为“无向完全图”。对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。 若一个有n个顶点的有向图，拥有n(n1)条弧，那么就称该图为“有向完全图”。对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。 4

53、无向完全图、有向完全图139 图7-2（a）所示为一个无向完全图，由于它有4个顶点，所以它有4(41)/2=6条边；图7-2（b）所示为一个有向完全图，由于它有4个顶点，所以它有4(41)=12条弧。 140图7-2 无向、有向完全图141 无论是无向图还是有向图，图中的每一条边或弧都与两个顶点有关。因此，在图的顶点数n、边数e以及各顶点的度D(vi)（1in）三者之间，有如下的关系存在：142 已知两个图G=（V，E），G=（V，E）。若有V是V的子集，E是E的子集，且E中的边（或弧）都依附于V中的顶点，那么就称G是G的一个“子图”。 5子图143图7-3 子图示例144 连通、连通图、连通

54、分量都是关于无向图的概念。 在无向图中，若从顶点vi到顶点vj之间有路径存在，则称vi与vj是“连通”的。如果无向图G中任意一对顶点之间都是连通的，则称该图G为“连通图”，否则是非连通图。6连通、连通图、连通分量145 在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个“连通分量”。146图7-4 连通图、非连通图、连通分量147 有时，可以给图的边或弧依附上某种数值，这种与图的边或弧相关的数值被称为“权”。边或弧上带有权的图称为“网图”或“网络”。7边的权、网络148图7-5 无向网图和有向网图1497.2 图的存储结构

55、所谓“邻接矩阵”，是指一种存储结构的组合：用一个一维数组存储图中顶点的数据信息；用两个变量分别记录图中顶点的个数以及图中边或弧的个数；用一个二维数组（即矩阵）存储图中各顶点间的邻接关系。通常，简略地只是把这个组合中的二维数组称作是图的“邻接矩阵”。7.2.1 邻接矩阵150 假设图G=（V，E）有n个顶点，为了表示n个顶点之间的邻接关系，说明一个nn的矩阵，并把其元素规定为： 151图7-6 无向图及相应的邻接矩阵152图7-7 有向图及相应的邻接矩阵153 对于一个网图来说，不仅应该通过邻接矩阵反映出顶点之间的邻接关系，还应该利用它反映出依附于边或弧的权值。因此，这时规定邻接矩阵的元素为：

56、154图7-8 图7-5中网图的邻接矩阵155 对于邻接矩阵，有如下特点。 （1）无向图的邻接矩阵是对称的对于无向图来说，由于有边（vi, vj）就意味着有边（vj, vi），所以无向图的邻接矩阵关于其主对角线总是对称的。156 （2）邻接矩阵与图中顶点的度有密切关系 对于无向（网）图，其相应的邻接矩阵中第i行（或第i列）里非零（且非）元素的个数，正好是第i个顶点vi的度D(vi)。157 对于有向（网）图，其相应的邻接矩阵中第i行里非零（且非）元素的个数，正好是第i个顶点vi的出度OD(vi)；其相应的邻接矩阵中第i列里非零（且非）元素的个数，正好是第i个顶点vi的入度ID(vi)。158邻

57、接矩阵的类型描述 #define MaxVertices 100#define MaxWeight 32767typedef structint VerticesMaxVertices; /*顶点信息的数组*/int EdgeMaxVertices MaxVertices; /*边的权信息的矩阵*/int numV; /*当前的顶点数*/int numE; /*当前的边数*/AdjMatrix; 159邻接矩阵表示下的基本操作 1建立一个图的邻接矩阵算法如下:Void CreateGraph(AdjMatrix *G, int n,int e) int i,vi,vj,w; /*w为边的权值*

58、/ G-numE=e; G-numV=n; Printf( 输入顶点的信息（整型）：) ;160 for ( i=0; inumV; i+ ) printf(n %d,i+1,: ); scanf(“%d”,&G-Verticesi); for ( i=0; inumE; i+ ) printf(n %输入边的信息（vi,vj,w）：); scanf(“%d ，%d ，%d “,&vi,&vj,&w); G-Edgevi-1vj-1=w; G-Edgevj-1vi-1=w; /*对于无向图*/ 1612输出图的邻接矩阵算法如下:void DispGraph(AdjMatrix G) int i

59、; Printf (n 输出顶点的信息（整型）：n ); for ( i=0; iG.numV; i+ )printf(“%d”,G.Verticesi, ); printf(n 输出邻接矩阵 ：n );162 for ( i=0; iG.numV; i+ ) printf(n %d”,i+1); for ( int j=0; jG.numV ;j+ ) printf( %d”，G.Edgeij， ); printf(n”)； 163分析用邻接矩阵表示图的不足之处：无论图中实际包含多少条边，图的读入、存储空间初始化等需要O（n2）个单位时间，这对边数较少（当边数mn*logn）的稠密图，这种存

60、储方式是有效的。164邻接链表（Adjacency List）是图的一种链式存储结构，与树型结构中的孩子链表相似。通常邻接链表也称邻接表。在邻接表中，对每一个顶点建立一个单链表，将同一个顶点发出的边链接在一个称为边链表的单链表中，链表中的每个结点表示一条依附该顶点的边，称为边结点。 7.2.2 邻接表165每个结点存放着该边的另一顶点的存储位置adjvex和指向同一链表中下一条边结点的指针nextarc，如果是带权图，边结点中还要保存该边上的权值等相关信息weight。166每一个单链表的头结点存放顶点的信息，由两部分组成，其中数据域data存放顶点的信息，链域firstarc用于指向链表中的