数据结构第六章第五节.ppt
6.7 回溯法和树的遍历,回溯的一般描述 回溯法的基本框架 应用举例,6.7.1 回溯的一般描述,回溯法(Backtracking),“通用的解题法”,基本原理：以“深度优先”的方式系统地“搜索”一个问题的一组解或所有解,适用场合适合于求解组合数较大的问题,问题的解必须能用一个n元组表示 X=(x1,x2,xn),xi Si,(i=1,2,n)mi=|Si|,(i=1,2,n),求出使得规范函数 P(x1,x2,xn)取极大值（或极小值或满足规范函数的约束条件）的所有向量,应用条件,（1）xi 0 即 Si=所有非负实数（2）xi=0 或 xi=1 即 Si=0,1（3）li xi ui 即 Si=a,li a ui,显式约束可以与所求解的问题的实例I有关，也可以无关。满足显示约束的所有元组确定问题的一个“可能的”解空间,显式约束：限定每个x只能从一个给定的集合上取值,隐式约束：规定I的解空间中那些实际上满足规范函数的元组。隐式约束描述了xi必须“彼此相关”的情况,约束条件,例 八皇后问题,(i+1,j+1),(i+1,j),(i+1,j-1),(i,j+1),(i,j),(i,j-1),(i-1,j+1),(i-1,j),(i-1,j-1),N皇后问题,八皇后问题,X=(x1,x2,x8),（2）显式约束条件：,（1）问题解表达式：,Si=1,2,3,4,5,6,7,8,1 i 8,（3）隐式约束条件：,(xixj)&(abs(xi-xj)abs(i-j)1 i,j 8,（4）解空间：,88,8！,X=(4,6,8,2,7,6,3,5),?,x1=1,x2=2,x2=4,x2=3,3,4,4,3,x2=1,x2=4,x2=3,3,4,x1=2,2,4,4,2,2,3,3,2,4,3,4,1,3,1,1,4,1,3,x2=1,x2=4,x2=2,2,4,x1=3,1,4,1,3,4,2,4,1,3,1,x2=1,x2=3,x2=2,2,3,x1=4,1,3,1,2,3,2,3,1,2,1,4皇后问题的状态空间树,1,并查集的树表示,int BACKTRACK(n)/这是对回溯法控制流程的抽象描述。每个解都在x1.n中生成，一个解一/经确定就立即印出。在x1,xk已选定的情况下，T(x1,xk-1)给出/xk所有可能的取值。限界函数B(x1,xk)判断哪些元素xk满足隐式约/束条件 k=1;while(k0)if 还剩有未检验过的xk,使得 xkT(x1,xk)and B(x1,xk)=TRUE if(x1,xk)是一条已抵达答案结点的路径 print(x1,xk);else k=k+1;/考虑下一个集合/if else k=k-1;/回溯到先前的集合/while/BACKTRACK,并查集的树表示,void RBACKTRACK(k)/这是对回溯法控制流程的抽象地递归描述。进入算法时，解/向量X1.n的前k-1个分量x1,xk-1已赋值 for 满足下式的每个xk xkT(x1,xk)and B(x1,xk)=TRUE if(x1,xk)是一条已抵达答案结点的路径 print(x1,xk);else RBACKTRACK(k+1);/for/BACKTRACK,置行计数i=1;放置第一个棋子，将棋子位置压入堆栈；while(i=4)i+;在i行的适当位置放置一个棋子，检查位置的合法性；if 位置合法，then 将棋子位置压入堆栈；else while(栈不空)删除栈顶元素；i-;在第i行重试下一个合法位置；if 找到一个合法位置，then 将新位置压入堆栈;break；/while(栈不空)/else/while(i=4),四皇后,四皇后,void place(int i,int n)/进入本函数时，在nxn棋盘前i-1行已放置了互不攻击的i-1个棋子/现从第i行起继续为后续棋子选择合适位置/当(in)时，求得一个合法布局，输出之 if(in)输出棋盘的当前布局；/n为4时，即为4皇后问题 else for(j=1;j=n;+j)在第i行第j列放置一个棋子；if(当前布局合法)place(i+1,n);移走第i行第j列的棋子；/place,四皇后,void place(int i,int n)/进入本函数时，在nxn棋盘前i-1行已放置了互不攻击的i-1个棋子/现从第i行起继续为后续棋子选择合适位置/当(in)时，求得一个合法布局，输出之 if(in)输出棋盘的当前布局；/n为4时，即为4皇后问题 else for(j=1;j=n;+j)在第i行第j列放置一个棋子；if(当前布局合法)place(i+1,n);移走第i行第j列的棋子；/place,应用举例,1.求出n位二进制数的所有编码,2.求含n个元素的幂集,A=1,2,3,(A)=1,2,3,1,2,1,3,1,2,3,2,3,3.假设有n个不同的正数，请找出这些数中所有使得某和数为M的所有组合,n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31,X=(1,2,4)和(3,4),1.求出n位二进制数的所有编码,void BinCoding(int b,int k)/n位二进数的编码放在数组b0.n-1中/假设前面k位的编码已完成，/现在对k+1位进行编码 if(k=n)printf(“%d”,b);/编码结束,输出 else bk=1;BinCoding(b,k+1);bk=0;BinCoding(b,k+1);/BinCoding,主调用 BinCoding(a,0),x1=1,x1=0,1,0,1,0,1,0,x2=1,0,x3=1,0,1,0,2.求含n个元素的幂集,1,2,3,1,2,1,3,1,2,3,2,3,1,2,1,1,2,取1,舍1,A=1,2,3,取2,舍2,取2,舍2,取3,舍3,取3,舍3,取3,舍3,取3,舍3,void Powerset(int i,int n)/求含n个元素的集合A的幂集p(A)./进入函数时已对A中前 i-1 个元素作了取舍处理/现从第i个元素起进行取舍处理。若in,则求得幂集的一个元素，/并输出之，初始调用：PowerSet(1,n)if(in)输出幂集的一个元素else 取第i个元素；PowerSet(i+1,n);舍第i个元素；PowerSet(i+1,n);/PowerSet,void GetPowerset(int i,List A,List/GetPowerSet,取11,n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31,舍11,取13,舍13,取13,舍13,取24,舍24,取24,舍24,取24,舍24,取24,舍24,取7,舍7,取7,舍7,取7,取7,取7,舍7,舍7,舍7,3.和数问题（背包问题）,void Knapsack(int weight,int num,int k)/对前面k-1个数字进行取舍的结果放在num0.k-1中/假设前面k个数字的取舍已完成，/现在对k+1个数字进行取舍 if(weight=M)output(num,k);/输出结果 else if(weightM)|(k=n)return;else numk=1;Knapsack(weight+wk,num,k+1);numk=0;Knapsack(weight,num,k+1);/Knapsack,int w=11,13,24,7;int M=31;int num4;,void output(int num,int count)int i;for(i=0;icount;i+)if(numi)printf(%d,wi);printf(n);,void main()Knapsack(num,0,0);printf(wait to exit);,11,13,7,24,11,7,24,13,11,7,13,24,11,24,13,7,24,7,24,7,13,24,11,24,13,24,11,24,和数问题的状态空间树,n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31,int w=11,13,24,7;int M=31;int num4;int visit4=0,0,0,0;void Knapsack1(int num,int weight,int k)if(weight=M)output1(num,k);else if(weightM)|(k=4)return;elsefor(i=0;i4;i+)if(!visiti)visiti=TRUE;numk=wi;Knapsack1(num,weight+wi,k+1);visiti=FALSE;/for/else,6.5 树与等价问题,等价关系与等价类 并查集 路径压缩 应用举例,6.5.1 等价关系与等价类,一般地，一个集合S中的所有对象可以通过等价关系划分为m个互不相交的子集S1,S2,Sm,即对于S中的任何两个元素x和y(x,yS),如果x和y是等价的（xy）,则x和y被划分在同一个子集Si中（i=1,2,m）.这些子集被成为等价类,利用等价关系把集合S划分为若干等价类的算法分为两步:,（1）首先把S中的每一个对象看成是一个等价类；（2）依次处理各个等价对（xy）；若xSi,ySj,且SiSj,则把集合Si,Sj合并成一个集合,6.5.1 等价关系与等价类,例：给定集合S=a,b,c,d,e,f,g,h,i,j,以及如下等价对 ab,gd,ij,cb,ac,hi,fe,fd，试划分等价类。,初始,a,b,c,d,e,f,g,h,i,j,ab,a,b,c,d,e,f,g,h,i,j,gd,a,b,c,d,g,e,f,h,i,j,ij,a,b,c,d,g,e,f,h,i,j,cb,a,b,c,d,g,e,f,h,i,j,S=a,b,c,d,e,f,g,h,i,j,ab,gd,ij,cb,ac,hi,fe,fd,ac,a,b,c,d,g,e,f,h,i,j,hi,a,b,c,d,g,e,f,h,i,j,fe,a,b,c,d,g,e,f,h,i,j,fd,a,b,c,d,g,e,f,h,i,j,S1,S2,S3,划分等价类的过程,并查集的ADT定义,数据对象:,数据关系:,ADT MFSet,若设S是MFSet型的集合，则它由n(n0)个子集Si(i=1,2,n)构成，每个子集的成员都属于同一数据对象,栈的抽象数据类型,基本操作:(1)InitMFSet(/归并操作。将Si和Sj中的一个并入另一个中 ADT MFSet,并查集的树表示,S1=a,b,c,S2=d,g,e,f,S3=h,i,j,a,b,c,d,e,f,g,h,i,j,S1,S2,S3,并查集的树表示,S1=a,b,c,S2=d,g,e,f,S3=h,i,j,a,b,c,d,e,f,g,h,i,j,S1,S2,S3,a,b,c,d,e,f,g,h,i,j,S1S2,S3,合并操作,d,e,f,a,b,c,h,i,j,S1S2,S3,g,合并操作,typedef PTree MFSet,#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data;int parent;/双亲位置域PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;/结点数PTree;,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,j=1,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,j=0,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,j=3,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Index(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,j=3,int find_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置 i=Index(S,x)；/确定x所在的位置，如果不存在，返回-1;if(i=-1)return 1;/元素x不属于任一子集 for(j=i;S.nodesj.parent 0;j=S.nodesj.parent;return j;/find_mfset,d,e,f,a,b,c,S,g,并查集的树表示,d,e,f,g,S2,a,b,c,S1,i=0,j=3,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,并查集的树表示,d,e,f,g,S2,a,b,c,S1,i=0,j=3,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,并查集的树表示,d,e,f,g,S2,a,b,c,S1,i=0,j=3,-7,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,并查集的树表示,d,e,f,g,S2,a,b,c,S1,i=0,j=3,3,-7,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,并查集的树表示,i=0,j=3,3,-7,3,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,d,e,f,a,b,c,S1S2,g,并查集的树表示,i=0,j=3,3,-7,3,int union_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;S.nodesj.parent=S.nodesi.parent+S.nodesj.parent S.nodesi.parent=j;return OK;/merge_mfset,d,e,f,a,b,c,S1S2,g,并查集的树表示,d0,S1,S2,S3,Sn-2,d1,d2,dn-2,Sn-1,dn-1,并查集的树表示,d0,S1,S2,S3,Sn-2,d1,d2,dn-2,Sn-1,dn-1,合并原则：大“吃”小,并查集的树表示,int weightedunion_mfset(MFSet S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个/子集Si和Sj的根结点，求并集SiSj if(iS.n|jS.n)return ERROR;if(S.nodesi.parent S.nodesj.parent)S.nodesj.parent+=S.nodesi.parent;S.nodesi.parent=j;else S.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i;return OK;/mix_mfset,d,e,f,a,b,c,S1S2,g,i=0,j=3,A,B,C,D,E,F,G,H,j,i,路径压缩,基本思想：从结点往根回溯，将结点的所有祖先(树根及其孩子除外)都变为根的孩子,A,B,C,D,E,F,G,H,j,i,A,B,C,D,E,F,G,H,j,i,路径压缩,E,G,基本思想：从结点往根回溯，将结点的所有祖先(树根及其孩子除外)都变为根的孩子,并查集的树表示,A,B,C,D,E,F,G,H,j,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,A,B,C,D,E,F,G,H,j,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,j=7,A,B,C,D,E,F,G,H,j,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=4,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=2,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,j=7,A,B,C,D,E,F,G,H,j,i,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,j=7,A,B,C,D,E,F,G,H,j,i,k,0,k=4,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,j,0,j=4,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,j,0,j=4,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,j,0,j=4,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,j,0,j=4,k=2,k,0,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,0,j=2,j,0,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,A,B,C,D,E,F,G,H,i,0,j=2,j,0,并查集的树表示,int collapsefind_mfset(MFSet S,TElemType x)/找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S,x)；/确定x所在的位置，如果不存在，返回-1;if(j=-1)return 1;/元素x不属于任一子集 for(i=j;S.nodesi.parent 0;i=S.nodesi.parent;while(i!=S.nodesj.parent)k=S.nodesj.parent;setsj.parent=i;j=k;return i;/collapsefind_mfset,i=0,0,j=2,0,A,B,C,D,E,F,G,H,j,i,例：犯罪团伙 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（=10000,罪犯数量），第二行：m（=100000，关系数量）以下若干行：每行两个数：I 和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。输出：一个整数，犯罪团伙的数量。,输入：118 1 24 53 41 35 67 105 108 9,输出：3,测试数据说明：1 s共10个测试数据：（1）5个数据：n=n=9000,100000=m=90000;,6.8 树的计数,具有n个结点的不同形态的树有多少棵？,二叉树的计数 树的计数,二叉树的计数,二叉树 T 相似于 T:二者均为空树或二者均不为空树，且它们的左右子树分别相似。,二叉树 T 等价于 T:二者不仅相似，而且对应结点上的对应元素均相同,具有n个结点、互不相似的二叉树的数目bn?,n=2,n=3,方法一：生成函数法,假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK.请画出该树,E B A D C F H G I K J,A B C D E F G H I J K,先序,中序,方法二：二叉树构造法,定理：任何n个不同结点的二叉树，都可由它的中序序列和先序序列唯一地确定,a1 a2 ai ai+1 an,b1b2 bi-1 bi bi+1 bn,先序序列,中序序列,用第二数学归纳法证明,i-1,i-1,先序：1 2 3 4 5 6 7 8,中序：3 2 4 6 5 1 7 8,先序：1 2 3 4 5 6 7 8,中序：2 3 1 4 7 6 8 5,不同形态的二叉树的数目是先序序列均为12n的二叉数的中序序列的数目,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,(a)1(+)2(+)3(+)3(-)2(-)1(-),3,2,1,(e)1(+)1(-)2(+)2(-)3(+)3(-),1,2,3,(d)1(+)1(-)2(+)3(+)3(-)2(-),1,3,2,(c)1(+)2(+)2(-)1(-)3(+)3(-),2,1,3,(b)1(+)2(+)2(-)3(+)3(-)1(-),2,3,1,(a),(b),(c),(d),(e),不同形态的二叉树的数目是先序序列均为12n的二叉数的中序序列的数目，该中序序列的数目恰为数列12n按不同顺序进栈和出栈所能得到的排列的数目。,树的计数,一棵树可转化成唯一的一棵没有右子树的二叉树，反之亦然。,树的计数,一棵树可转化成唯一的一棵没有右子树的二叉树，反之亦然。,具有n个结点有不同形态的树(有序树)的数目tn和具有n-1个结点互不相似的二叉树的数目相同,第6章 树和二叉树,6.1 学习目的和要求,目的：介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、树和森林与二叉树的转换，赫夫曼树及赫夫曼编码等内容,重点：掌握二叉树的遍历算法及有关应用,难点：使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题,要求：熟悉所介绍的基本内容,第一章 绪论,6.2 知识体系,6.2.1 知识体系结构,树和二叉树,树的概念,二叉树,二叉树的性质,二叉树的概念,线索二叉树（先序线索，中序线索，后序线索）,树和森林,二叉树的存储方式,二叉树的遍历（先序，中序，后序，层序，）,树的存储方式,树、森林与二叉树的相互转换,树和森林的遍历,赫夫曼树,第一章 绪论,6.2.2 知识点与考核要求,1 树的概念 领会,（1）树的逻辑结构特征,（2）树的不同表示方法,2 二叉树 简单应用,（1）二叉树的递归定义以
