1、12 v 3 。4 5DS6DS数据结构数据结构Data Structure78 910111213：14：1516（1718 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面 192021 22 23241.简要回答下列问题：简要回答下列问题：a.数据与数据元素有何区别？数据与数据元素有何区别？b.逻辑结构与存储结构是什么？它们逻辑结构与存储结构是什么？它们是什么关系？是什么关系？c.什么是算法？它有什么特点？什么是算法？它有什么特点？25 2.试写一个算法，
2、统计输入的试写一个算法，统计输入的100个整个整数中奇数和偶数的个数。数中奇数和偶数的个数。3.设计下面问题算法，并分析最坏情况设计下面问题算法，并分析最坏情况时间复杂性时间复杂性:在数组在数组 A1.n中查找值为中查找值为 K的元素，的元素，若找到输出其位置若找到输出其位置 i(0 i n+1),否则输出否则输出0。26 4.设设 n 为正整数，写出下列程序段的时间为正整数，写出下列程序段的时间复杂度：复杂度：（1）for(I=1;In;I+)m=m+I;for(j=0;jn;j+)count+=m+j;27（2）for(I=0;In;I+)m=m+I;for(j=0;j10;)count+
3、=m+j;j+;28（3）k=1;s=0;while(snext&jnext&jnext;+j;P=p-next;+j;if(!(p-next)|j i-1)return ERROR;if(!(p-next)|j i-1)return ERROR;/删除位置不合理删除位置不合理 q=p-next;p-next=q-next;q=p-next;p-next=q-next;/删除并释放结点删除并释放结点*e=q-data;free(q);e=q-data;free(q);return OK;return OK;/ListDelete_L/ListDelete_L81 两个有序单链表合并为一个有序单
4、链表两个有序单链表合并为一个有序单链表(非递减非递减)MergeList_L(Linklist La,LinkList Lb,LinkList LcMergeList_L(Linklist La,LinkList Lb,LinkList Lc)pa=La-next;pbpa=La-next;pb=Lb-next;=Lb-next;LcLc=pc=La;=pc=La;While(pa&pbWhile(pa&pb)If(pa-data data data)-data)pc-next=pa;pc=pa;pa=pa-next;pc-next=pa;pc=pa;pa=pa-next;elsepc-nex
5、t=pb;pc=pb;pb=pbelsepc-next=pb;pc=pb;pb=pb-next;-next;pc-next=pa?pa:pbpc-next=pa?pa:pb;free(Lb);free(Lb);82838485)prior 86：AB87p8889 90bcaP ;p-next-prior=p-prior;91p-prior-next=p-next;p-next-prior=p-prior;bacp92 93结点数据占用存储量量结点数据本身占用存储存储密度941.描述以下三个概念的区别：描述以下三个概念的区别：头结点、头指针和开始结点头结点、头指针和开始结点2.从尾指针出发能访
6、问到链表上所有结点的从尾指针出发能访问到链表上所有结点的链表有链表有 。3.假设有两个按元素值递增的线性表假设有两个按元素值递增的线性表 A、B，编写算法将两表合并为一个按元素值递减编写算法将两表合并为一个按元素值递减的线性表的线性表C。（分别以顺序、链式实现）（分别以顺序、链式实现）95 4.设线性表存放在向量设线性表存放在向量 AMAXSIZE的的前前elenum个分量中，且递增有序。试写一个分量中，且递增有序。试写一算法，将算法，将 x 插入线性表适当位置上，以保插入线性表适当位置上，以保持线性表的有序性，并且分析算法的时间持线性表的有序性，并且分析算法的时间复杂性。复杂性。5.以链式存
7、储结构实现上题。以链式存储结构实现上题。96 6.在双向链表上实现线性表的下列基本运在双向链表上实现线性表的下列基本运算：算：(1)初始化初始化(2)定位定位(3)插入插入(4)删除删除9798）99100 101.102 栈和线性表类似，也栈和线性表类似，也有两种（顺序、链式）有两种（顺序、链式）实现方法实现方法103 104 105 top=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)to
8、ptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空106107108 typedef struct node int data;struct node *link;LinkList;结点定义结点定义 .topdata link栈底栈底栈顶栈顶109 110111112栈的应用栈的应用 113栈的应用栈的应用114子过程子过程3srr115116 递归算法的一般形式递归算法的一般形式117 118 119运行结果：1，2，2，3，3，3，120主程序主程序(1)print(w)w=3;3print(2);（1）w=3 top(2)输出：输出：3,3,3w2
9、print(1);（2）w=2 （1）w=3 top(3)输出：输出：2,2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)输出：输出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3)输出：输出：2,2(2)2(1)3top(4)输出：输出：1(3)1(2)2(1)3top(2)输出：输出：3,3,3 (1)3top返回返回(3)1(2)2(1)3top(4)0结束结束(1)121 假设表达式中有多种扩号，可以用栈来进行扩号假设表达式中有多种扩号，可以用栈来进行扩号匹配检验，具体做法为：匹配检验，具体做法为：非括号字符跳过不理；碰上左扩号
10、，入栈；非括号字符跳过不理；碰上左扩号，入栈；碰上右扩号，出栈，并且检查出栈元素是否与当碰上右扩号，出栈，并且检查出栈元素是否与当前右扩号相匹配，若匹配继续检查，否则匹配失前右扩号相匹配，若匹配继续检查，否则匹配失败。败。请同学们下去自己编请同学们下去自己编程序试试。程序试试。122123124 125 126队列的主要操作队列的主要操作(Q,&e)127;128129 130p=(QueuePtr)malloc(sizeof(Qnodep=(QueuePtr)malloc(sizeof(Qnode););p-data=x;p-data=x;p-next=NULL;p-next=NULL;Q-
11、rear-next=p;Q-rear-next=p;Q-rear=p;Q-rear=p;131if(Empty(Q)return ERROR;if(Empty(Q)return ERROR;else s=Q-front-next;else s=Q-front-next;/*指向被删结点指向被删结点*/if(s-next=NULL)if(s-next=NULL)Q-front-Next=Null;Q-front-Next=Null;Q-rear=Q-front;Q-rear=Q-front;Else Q-front-next=s-next;Else Q-front-next=s-next;*e=
12、s-data;e=s-data;free(s);free(s);return OK;return OK;132front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront1
13、33134 ：；实现：利用实现：利用“模模”运算运算 入队：入队：rear=(rear+1)%M;sqrear=x;出队：出队：front=(front+1)%M;x=sqfront;队满、队空判定条件队满、队空判定条件.135rearfrontmaxSize-1入队入队:rear=(rear+1)%MaxSize;elementsrear=item出队：出队：front=(front+1)%MaxSize;队空：队空：rear=front;队满：队满：(rear+1)%maxSize=front;012front012rear队列初始化：队列初始化：front=rear=0;=0;n存储队列
14、的数组被当作首尾相接的表处理。存储队列的数组被当作首尾相接的表处理。n队头、队尾指针队头、队尾指针加加1 1时从时从MaxSizeMaxSize -1-1直接进到直接进到0 0，可用语言的取模可用语言的取模(余数余数)运算实现。运算实现。136tJ4,J5,J6出队J7,J8,J9入队解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间：队空：队空：front=rear 队满：队满：(rear+1)%M=front137;138void en_cycque(int sq,int front,int rear,int x)if(
15、rear+1)%MAXSIZE)=front)printf(overflow);else rear=(rear+1)%MAXSIZE;sqrear=x;139int del_cycque(int sq,int front,int rear,int*q)if(front=rear)return(0);else front=(front+1)%MAXSIZE;*q=sqfront;return(1);1401.铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车
16、顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。1412.假设以数组Qm存放循环队列中的元素,同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(enqueue)和删除(delqueue)元素的操作。142143数组的性质数组的性质 数组元素数目固定数组元素数目固定元素类型相同元素类型相同下标有界且有序下标有界且有序 144一维数组一维数组数组图示数组图示 145数组图示数组图示 14614
17、7232221131211aaaaaaA 多维数组以一维方多维数组以一维方式存储，即数组元素式存储，即数组元素还是数组！还是数组！148LOC(i)=LOC(i-1)+l=+i*l一维数组的存储一维数组的存储149二维数组的存储二维数组的存储231322122111aaaaaa a23 a22 a21 a13 a12 a11 a23 a13 a22 a12 a21 a11150)(2 1 02 22 12 021 21 11 01 0 20 10 00aijLocMNANANANAMAAAAMAAAAMAAAA求对例：例：151 n维数组 各维元素个数为各维元素个数为 m1,m2,m3,mn
18、下标为下标为 i1,i2,i3,in 的数组元素的存储地址：的数组元素的存储地址：limialimimmmimmmiaiiiLOCnjnjknkjnnnnnn*)(),(111143232121152 153。1,1221100nnaaaa00 1,12,11,22322211211100100nnnnnnaaaaaaaaaaa00154jijini;k 1|;1|;232jijinji k 155 1,10,1111000nnnaaaaa0 1,122111,00100nnnaaaaaa0156 jijinnjii;2/)1(2/)1(k jijinnjni iin;2/)1()1(2/)1
19、()1(k 157 158 159三元组表类型说明：三元组表类型说明：#define SMAX 16typedef int datatype；typedef structint i,j;/*行列号行列号*/datatype v;/*元素值元素值*/node;typedef structint m,n,t;/*行、列数，非零元素个数行、列数，非零元素个数*/node dataSMAX;/*三元组表三元组表*/SpMatrix;r ro ow w c co ol l v va al lu ue e 160 三元组表示例三元组表示例100001013200M 1 3 2 2 0 2 1 1 1 1
20、2 0 3 1 0 5 4 3行数行数 列数列数 元素个数元素个数 行行 列列 值值1610000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022000A6776转置为 162 163 行行行行 (r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1
21、 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 -6 6 4 3 3 2 2 -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 164 设矩阵列数为设矩阵列数为Cols，对矩阵三元组表扫描，对矩阵三元组表扫描Cols次。次。第第k次检测列号为次检测列号为k的项。
22、的项。第第k次扫描找寻所有列号为次扫描找寻所有列号为k的项，将其行号变列的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。号、列号变行号，顺次存于转置矩阵三元组表。设矩阵三元组表总共有设矩阵三元组表总共有Terms项，其时间代价为项，其时间代价为 O(Cols*Terms)。若矩阵有若矩阵有200行，行，200列，列，10,000个非零元素，总共个非零元素，总共有有2,000,000次处理。次处理。165时间复杂度：时间复杂度：O(nO(n*t)t)166 167168 树树是一类重要的非线性数据结构，是以是一类重要的非线性数据结构，是以分支关系定义的层次结构分支关系定义的层次结构v
23、定义定义：树树(tree)是是n(n=0)个结点的有限集个结点的有限集T，其中：，其中：有且仅有一个特定的结点，称为树的有且仅有一个特定的结点，称为树的，当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交互不相交的有限集的有限集T1,T2,Tm，其中每一个集合本身，其中每一个集合本身又是一棵树，称为根的又是一棵树，称为根的如果如果n=0，称为空树；，称为空树；169 树中至树中至 多有一个结点多有一个结点-根根 树中各子树是互不相交的集合树中各子树是互不相交的集合170171 172173174A只有根结点的树ABCDEFGHIJKLM有子树的树根子树175ABCDEFGHIJ
24、KLMABCDEFGHIJKLM 176(d)(d)(d)177树型表示树型表示bacghdefij178凹入表表示凹入表表示abdeijfcgh179嵌套集合表示嵌套集合表示嵌套括号表示嵌套括号表示ijdfghabcea(b(d,e(i,j),c(g,h)180ABABABAB 定义定义：是是n(n=0)个结点的有限集，它或个结点的有限集，它或为空树为空树 (n=0)，或由一个根结点和两棵分别称为或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成左子树和右子树的互不相交的二叉树构成 每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 的结的结点点)二叉
25、树的子树有左、右之分，且其次序不能任意二叉树的子树有左、右之分，且其次序不能任意颠倒颠倒 181A只有根结点的二叉树A只有根结点的二叉树空二叉树空二叉树AB右子树为空ABAB右子树为空AB左子树为空ABAB左子树为空ABC左、右子树均非空ABCABC左、右子树均非空 182 假设对所有假设对所有j(1j(1ji)jBDCD L R先序遍历序列：A B D C先序遍历:2065.3.1 5.3.1 二叉树的遍历二叉树的遍历Void PreOderTraverse(BiTree T)if(T!=NULL)printf(T-data);PreOrderTraverse(T-lchild);PreOr
26、derTraverser(T-rchild);/*先序遍历先序遍历*/主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);2075.3.1 5.3.1 二叉树的遍历二叉树的遍历2085.3.1 5.3.1 二叉树的遍历二叉树的遍历InOrde
27、r(BinTreeNode*current)if(current!=NULL)InOrder(currentleftChild);Visit(currentdata);InOrder(currentrightChild);中序遍历地归算法如下：中序遍历地归算法如下：2095.3.1 5.3.1 二叉树的遍历二叉树的遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:2105.3.1 5.3.1 二叉树的遍历二叉树的遍历211LastOrder(BinTreeNode*current)if(current!=NULL)LastOrder(curren
28、tleftChild);LastOrder(currentrightChild);Visit(currentdata);后序遍历递归算法如下：后序遍历递归算法如下：5.3.1 5.3.1 二叉树的遍历二叉树的遍历2125.3.1 5.3.1 二叉树的遍历二叉树的遍历ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:B2135.3.1 5.3.1 二叉树的遍历二叉树的遍历2145.3.1 5.3.1 二叉树的遍历二叉树的遍历 递归算法逻辑清晰、易懂，但在实现时，由递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑于函数调用
29、栈层层叠加，效率不高，故有时考虑非递归算法。非递归算法。215 5.3.1 5.3.1 二叉树的遍历二叉树的遍历 先找到左下结点，即沿左链一直下来，先找到左下结点，即沿左链一直下来，直到左链为空，这时，所有路过的结点进栈。直到左链为空，这时，所有路过的结点进栈。然后结点出栈并访问，对于每个出栈结点，即然后结点出栈并访问，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访表示该结点和其左子树已被访问结束，应该访问该结点的右子树。问该结点的右子树。（1）当前指针指向根结点。）当前指针指向根结点。（2）当前指针指向其左孩子并进栈，重复）当前指针指向其左孩子并进栈，重复（2），直到左孩子为）
30、，直到左孩子为NULL （3）退栈，打印出栈结点，将当前指针指）退栈，打印出栈结点，将当前指针指向右孩子，向右孩子，（4）若栈非空或当前指针非）若栈非空或当前指针非NULL，执行，执行（2）；否则结束。）；否则结束。2165.3.1 5.3.1 二叉树的遍历二叉树的遍历InOrder(BinTreeNode*T)InitStack(s);p=T;While(p|!StackEmpty(s)if(p!=NULL)Push(s,p);p=p-lchild;ElsePop(s,p);visit(p-data);P=p-rchild;2175.3.1 5.3.1 二叉树的遍历二叉树的遍历二叉树的遍历方
31、法小结二叉树的遍历方法小结-+/a*b-efcd先序遍历：先序遍历：中序遍历中序遍历：后序遍历：后序遍历：层次遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e f-+a*b-c d/e f2185.3.1 5.3.1 二叉树的遍历二叉树的遍历二叉树的小结二叉树的小结1 1、二叉树：二叉树：或为空树，或由根及两棵不相交的或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二左子树、右子树构成，并且左、右子树本身也是二叉树；叉树；2 2、二叉树二叉树既可以用顺序结构存储，也可用链式结既可以用顺序结构存储，也可用链式结构存储；构存储；3 3、
32、遍历：遍历：按某种搜索路径访问二叉树的每个结点按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。，每个结点仅被访问一次。二叉树的遍历可以分解二叉树的遍历可以分解为：访问根，遍历为：访问根，遍历左子树和左子树和遍历遍历右子树，三种遍历右子树，三种遍历算法：算法：先序遍历、中序遍历、后序遍历先序遍历、中序遍历、后序遍历；2195.3.2 5.3.2 二叉树的遍历应用二叉树的遍历应用 方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将计数器加若是叶子结点，则将计数器加1。int countleaf(BiTree T)
33、int n1,n2;if(T=NULL)return(0);if (T-lchild=NULL)&(T-rchild=NULL)return(1);else n1=countleaf(T-lchild);n2=countleaf(T-rchild);return(n1+n2);一、统计二叉树中叶子结点的个数一、统计二叉树中叶子结点的个数2205.3.2 5.3.2 二叉树的遍历应用二叉树的遍历应用int depth(bitreeint depth(bitree *t)t)int int dep1,dep2;dep1,dep2;if(t=NULL)return(0);if(t=NULL)retu
34、rn(0);else else dep1=depth(t-lchild dep1=depth(t-lchild););dep2=depth(t-rchild dep2=depth(t-rchild););if(dep1 dep2)return(dep1+1);if(dep1 dep2)return(dep1+1);else return(dep2+1);else return(dep2+1);二、二、求二叉树的深度求二叉树的深度 二叉树深度=MAX(左子树深度，右子树深度）+1221孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）5.4 5.4 树的存储结构树的存储结构实现：用二叉
35、链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点 操作容易 破坏了树的层次typedef struct node datatype data;struct node *fch,*nsib;JD;abcdefhgi a b c d e f g h i2225.4.1 5.4.1 树的存储结构树的存储结构 孩子兄弟存储结构是为每个结点设计三个域：每个结点设计三个域：一个数据元数据元素域素域，一个该结点的第一个孩子结点指针域，一个该结点的下一个该结点的第一个孩子结点指针域，一个该结点的下一个兄弟结点指针域一个兄弟结点指针域。由于树的孩子兄弟存储结构有两个两个
36、指针域指针域，并且这两个指针是有序的，所以孩子兄弟存储结构是把树转换为二叉树的存储结构。把树转换为二叉树所对应的结构恰好就是这种孩子兄弟存储结构 孩子兄弟存储结构的最大优点优点是可方便地实现树和二叉树可方便地实现树和二叉树的相互转换的相互转换。孩子兄弟存储结构的缺点也和孩子表示法的缺点一样：从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。2235.4.2 5.4.2 树与二叉树的转换树与二叉树的转换树与二叉树上结点的对应关系树与二叉树上结点的对应关系 二叉树中各结点：二叉树中各结点：左孩子左孩子 -该结点的第一个孩子该结点的第一个孩子右孩子右孩子 -该结点的第一个右兄弟该
37、结点的第一个右兄弟注：由一棵树转换得到的二叉树必无右子树注：由一棵树转换得到的二叉树必无右子树（思考：为什么？）（思考：为什么？）2245.4.2 5.4.2 树与二叉树的转换树与二叉树的转换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释2255.4.2 5.4.2 树与二叉树的转换树与二叉树的转换树根结点 X X 的第一个孩子结点 X X 紧邻的右兄弟二叉树根结点 X X 的左孩子结点 X X 的右孩子树转换成二叉树树转换成二叉树2265.4.2 5.4.2 树与二叉树的转换树与二叉树的转换I IA AC CB BD DH HG
38、 GF FE EF FI IA AB BD DH HG GC CE E树转换成二叉树树转换成二叉树2275.4.2 5.4.2 树与二叉树的转换树与二叉树的转换 2285.4.2 5.4.2 树与二叉树的转换树与二叉树的转换 森林转换为二叉树森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉将各棵树分别转成二叉树；树；把每棵树的根结点用线把每棵树的根结点用线连起来；连起来；以第一棵树的根结点作以第一棵树的根结点作为二叉树的根结点，按顺为二叉树的根结点，按顺时针方向旋转。时针方向旋转。2295.4.2 5.4.2 树与
39、二叉树的转换树与二叉树的转换ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 森林转换为二叉树森林转换为二叉树2305.4.2 5.4.2 树与二叉树的转换树与二叉树的转换2315.4.2 5.4.2 树与二叉树的转换树与二叉树的转换 如果如果B为空为空，则，则 对应的森林对应的森林F也为空。也为空。如果如果B非空非空，则，则 F中第一棵树中第一棵树T1的根为的根为root；T1的根的子树森林的根的子树森林 T11,T12,T1m 是由是由 root 的左子树的左子树 LB 转换而来，转换而来，F 中除了中除了 T1 之外之外其余的树组成的森林其余的树组成的森林
40、 T2,T3,Tn 是由是由 root 的右子树的右子树 RB 转换而成的森林。转换而成的森林。二叉树转换为森林的规则二叉树转换为森林的规则232二叉树转换成森林二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.4.2 5.4.2 树与二叉树的转换树与二叉树的转换2335.4.3 5.
41、4.3 树与森林的遍历树与森林的遍历常用方法常用方法（前）先根（序）遍历（前）先根（序）遍历：先访问树的根结：先访问树的根结点，然后依次先根遍历根的每棵子树点，然后依次先根遍历根的每棵子树后根（序）遍历后根（序）遍历：先依次后根遍历每棵子：先依次后根遍历每棵子树，然后访问根结点树，然后访问根结点按层次遍历按层次遍历：先访问第一层上的结点，然：先访问第一层上的结点，然后依次遍历第二层，后依次遍历第二层，第第n n层的结点层的结点2345.4.3 5.4.3 树与森林的遍历树与森林的遍历 一、一、前序遍历前序遍历若树非空，则若树非空，则1、访问根结点、访问根结点2、依次前序遍历树的各子树、依次前序
42、遍历树的各子树ABCDEFGHIJ遍历序列：A，B，E，F，C，G，D，H，I，J2355.4.3 5.4.3 树与森林的遍历树与森林的遍历ABCDEFGHIJ遍历序列：E，F，B，G，C，H，I，J，D，A2365.4.3 5.4.3 树与森林的遍历树与森林的遍历ABCDEFGHIJ遍历序列：A，B，C，D，E，F，G，H，I，J2375.4.3 5.4.3 树与森林的遍历树与森林的遍历ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO按广
43、度按广度按深度按深度2385.4.3 5.4.3 树与森林的遍历树与森林的遍历 二、森林二、森林 森林的遍历即多棵树的遍历，单棵树的遍历与树的遍历相同，逐棵树进行遍历。239先序遍历森林 若森林非空 先访问第一棵树的根结点，再先序遍历第一棵树根的子森林，再先序遍历除去第一棵树后剩余 的子森林。转换成二叉树后与二叉树的先序遍历相同5.4.3 5.4.3 树与森林的遍历树与森林的遍历2405.4.3 5.4.3 树与森林的遍历树与森林的遍历后序遍历森林 若森林非空 后序遍历第一棵树根的子森林 访问第一棵树的根 后序遍历去掉第一棵树后剩余的子森林 转换成二叉树后与二叉树的中序遍历相同2415.4.3
44、 5.4.3 树与森林的遍历树与森林的遍历先序遍历ABCDEFGH IJA B C D E F G H I J后序遍历B C D A F E H J I G 森林的遍历森林的遍历242先序遍历ABCDEFGHIJ中序遍历BCDAFEHJIG5.4.3 5.4.3 树与森林的遍历树与森林的遍历ABCDEFGH IJ 森林转换成的二叉树的遍历森林转换成的二叉树的遍历2435.5 5.5 哈夫曼树及应用哈夫曼树及应用 定义定义 路径：从树中一个结点到另一个结点之间的分支路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径构成这两个结点间的路径 路径长度：路径上的分支数路径长度：路径上的分
45、支数 树的路径长度：从树根到每一个结点的路径长度树的路径长度：从树根到每一个结点的路径长度之和之和 树的带权路径长度：树中所有带权结点的路径长树的带权路径长度：树中所有带权结点的路径长度之和度之和结点到根的路径长度权值其中：记作：kknkkklwlwwpl1哈夫曼树哈夫曼树(Huffman)带权路径长度最短的树带权路径长度最短的树2445.5.1 5.5.1 哈夫曼树哈夫曼树 Huffman树树设有设有n个权值个权值w1,w2,wn，构造一棵，构造一棵有有n个叶子结点的二叉树，每个叶子的权值为个叶子结点的二叉树，每个叶子的权值为wi,则则wpl最最小的二叉树叫小的二叉树叫Huffman树树。构
46、造构造HuffmanHuffman树的方法树的方法HuffmanHuffman算法算法 构造Huffman树步骤 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树2455.5.1 5.5.1 哈夫曼树哈夫曼树例例 有有4个结点，权值分别为个结点，权值分别为7，5，2，4，构造有，构造有4个叶子结点的二个叶子结点的二叉树叉树abcd7524WPL=7
47、*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35abcd7524nkKKLWWPL1要使二叉树要使二叉树WPL小小,就须在构造就须在构造树时树时,将权值大的结点靠近根将权值大的结点靠近根.2465.5.1 5.5.1 哈夫曼树哈夫曼树例例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118构造构造HuffmanHuffman树的方法树的方法HuffmanHuffman算法算法2475.5.1 5.5.1 哈夫曼树哈夫曼树例例 w=5,29,7,8,14,23,3,115142
48、9 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422914871529581002485.5.2 5.5.2 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码 在进行数据通讯时，涉及数据编码问题。所谓数据编在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。码就是数据与二进制字符串的转换。例如：邮局发电报例如：邮局发电报 例例 要传输的原文为要传输的原文为ABACC
49、DA等长编码等长编码 A：00 B：01 C：10 D：11发送方：将发送方：将ABACCDA 转换成转换成 00010010101100接收方：将接收方：将 00010010101100 还原为还原为 ABACCDA不等长编码不等长编码 A：0 B：00 C：1 D：01发送方：将发送方：将ABACCDA 转换成转换成 000011010接收方：接收方：000011010 转换成转换成 A的编码是B的前缀AAAACCDAAAAACCDABBCCDABBCCDA原文 电文（二进制字符串）原文发送方发送方接收方接收方249设设 A：0 B：110 C：10 D：111发送方发送方：将：将 ABA
50、CCDA 转换成转换成 0110010101110 总长度是总长度是13所得的译码是唯一的所得的译码是唯一的前缀编码前缀编码：任何字符编码不是其它字符编码的前缀任何字符编码不是其它字符编码的前缀5.5.2 5.5.2 哈夫曼编码哈夫曼编码2505.5.2 5.5.2 哈夫曼编码哈夫曼编码思想：根据字符出现频率编码，使电文总长最思想：根据字符出现频率编码，使电文总长最短短编码：根据字符出现频率构造编码：根据字符出现频率构造Huffman树，然树，然后将树中结点引向其左孩子的分支标后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标引向其右孩子的分支标“1”；每个字符的编；每个字符的编码即
