CH6_5.ppt

6.7 回溯法和树的遍历 6.7.1 回溯的一般描述 回溯法(Backtracking) 问题的解必须能用一个n元组表示 X=(x1,x2,…,xn), xi ? Si , (i=1,2,…n) mi=| Si | , (i=1,2,…n) （1） xi ? 0 即 Si={所有非负实数} （2） xi=0 或 xi=1 即 Si={0, 1} （3）li ? xi ? ui 即 Si={a, li ? a ? ui } 例 八皇后问题 X=(x1,x2,…,x8) 并查集的树表示 并查集的树表示 应用举例 A={1,2,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 B){ //线性表A表示集合A, 线性表B表示幂集p(A)的一个元素 //局部变量k为进入函数时表B的当前长度。 //第一次调用本函数时，B为空表，i=1 if(iListLengt(A)) Output(B) //输出当前B值，即p(A)的一个元素 else{ GetElem(A, i, x); k=ListLength(B); ListInsert(B, k+1, x); GetPowerSet(i+1, A, B); ListDelete(B, k+1, x); GetPowerSet(i+1, A, B); } }//GetPowerSet 6.5 树与等价问题 6.5.1 等价关系与等价类 6.5.1 等价关系与等价类 并查集的ADT定义 栈的抽象数据类型 基本操作: (1) InitMFSet(S, n, x1, x2, …, xn) //构造一个由n个子集(每个子集只含单个成员xi )构成的集合 (2) Find(S, x); //查找，确定S中x所属子集Si (3) Union(S, i, j); //归并操作。将Si和Sj中的一个并入另一个中 }ADT MFSet 并查集的树表示 并查集的树表示 #define MAX_TREE_SIZE 100 typedef struct PTNode{ TElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }PTree; 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 并查集的树表示 6.8 树的计数 具有n个结点的不同形态的树有多少棵？ 二叉树的计数 树的计数 树的计数 第6章 树和二叉树 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 第一章 绪论 j i H G F E D C B A 7 7 4 4 2 2 2 0 0 -7 9 8 7 6 5 4 3 2 1 0 int collapsefind_mfset(MFSet S, TElemType x){ //找集合S中元素x所在子集的根的位置,同时进行路径压缩 j=Locate(S, x)； //确定x所在的位置，如果不存在，返回-1; if(j==-