《数据结构电子课件教案第6章树与回溯法》由会员分享，可在线阅读，更多相关《数据结构电子课件教案第6章树与回溯法（26页珍藏版）》请在金锄头文库上搜索。
1、1,树和森林,树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，这里介绍的树是比二叉树更为一般的树结构,1 树和森林的定义 2 树、森林的存储结构 3 树、森林与二叉树的转换 4 树和森林的遍历 5 树与问题求解,2,1 树和森林的定义,树：树是n(n0)个结点的有限集D，若D为空集，则为空树，否则： 在D中存在唯一的称为根的节点T 当n1时，其余节点可分为m个互不相交的有限集T1，T2，Tm，其中每一个子集本身又是棵树，并称其为根T的子树。,T=A, B, C, D, E, F, G, H, I, J A是根，其余结点可以划分为3个互不相交的集合：T
2、1=B, E, F , T2=C, D , T3=D, H, I, J 这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如 对于 T1，B是根，其余结点可以划分为2个互不相交的集合：T11=E，T12=F，T11,T12 是B的子树。,3,森林：森林是m(n0)棵互不相交的树的集合,树T是由一个根节点和n棵树（ T1，T2，Tm ）组成的森林构成，森林中的每棵树都是树T的子树,树与森林的转换 树转换成森林：去掉根节点与其所有子树的连线去掉，就形成森林 森林转换成树：在森林的头上加一个虚拟的根节点即可,4,2 树、森林的存储结构,双亲表示法 通过保存每个结点的双亲结点的位置，表示树中结点
3、之间的结构关系。 用一组连续的内存单元存储树的结点，每个结点包含两个域：一个数据域，一个“指针域”，用于指示其双亲结点在数组中的位置,双亲表示法 孩子链表表示法 左孩子-右兄弟存储表示法,5,typedef struct PTNode Elem data;int parent; / 双亲位置域 PTNode;,A,B,C,D,E,F,G,r=0 n=6,#define MAX_TREE_SIZE 100,data parent,6,孩子链表表示法 通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。 与双亲表示法相反，孩子表示法适合实现涉及孩子的操作。还可以将双亲表示与孩子表示法结合
4、：带双亲的孩子链表。,7,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4,r=0 n=6,data firstchild,1 2 3,4 5,6,-1 0 0 0 2 2 4,8,struct CTNode int child;CTNode *next; *ChildPtr;,struct Elem data;ChildPtr firstchild; / 孩子链的头指针 CTBox;,struct CTBox nodesMAX_TREE_SIZE;int n, r; / 结点数和根结点的位置 CTree;,孩子节点结构,双亲节点
5、结构,树结构,9,孩子兄弟（左孩子右兄弟）表示法 孩子兄弟表示法用二叉链表作为树的存贮结构,class CSNode public:Elem data;CSNode *firstchild;CSNode *nextsibling; ;,10,A,C,A BCE DFG,root,A BCE DFG,11,此二叉链表既是树(a) 的孩子兄弟表示又是二叉树(b)的二叉链表,(a),(b),由此可将 树与二叉树 对应起来,树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。,12,3 树、森林与二叉树的转换,13,3 树、森林与二叉树的转换,14,4 树和森林
6、的遍历,树的遍历两种方法 深度优先 先（根）序遍历 若树不空，则先访问根结点，然后依次先序遍历各棵子树。 后（根）序遍历(中序遍历) 若树不空，则先依次后序遍历各棵子树，然后访问根结点 宽度优先（层次遍历） 若树不空，则自上而下自左至右访问树中每个结点。,15,AB C DE F GHI J K,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序,E F B C I J K H G D A,层次遍历时顶点的访问次序,A B C D E F G H I J K,二叉树的先序遍历,二叉树的中序遍历,16,.树与问题求解,问题1：n皇后问题 问题2：子集
7、和问题 问题3：分书问题 问题4：稳定婚配问题,17,.树与问题求解,树作为问题求解过程的一种形象化表示方法状态空间 树的节点表示问题求解过程中的一个状态 状态转移：一个节点处理完毕后，转入处理其下一个节点，称为状态转移，每一步转移称为一个算子。 状态生成：根据节点x的当前值，使用所有可用算子生成其所有可行的子节点，也称为节点生成，或节点扩展。 问题求解过程：对状态树进行遍历的过程 深度优先遍历 宽度优先遍历,18,用状态空间进行问题求解要素 解的表示（一般可以用多元组表示） 初始状态 可用的算子 终止条件,下面我们用例子来说明,19,例1：n皇后问题,在nn格的棋盘上放置彼此不受攻击的n个皇
8、后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,问：有多少种放置方法？,20,21,解的表示:皇后位置 最直观的表示方法: 二维数组L(i,j) 最有效的表示方法： 用一位数组Xi表示，Xi表示第i行的皇后放在第Xi列,算子放置皇后，将第i个皇后放在第j个位置，表示为xi=j 约束条件：不在同一行：每一行只放一个皇后就可不在同一列：XiXk, k=1,2,3,i-1不在正对角线: Xi-iXk-k 不在反对角线: Xi+iXk+k最后两个条件综合：abs(Xi-Xk)abs
9、(i-k),22,终止条件： 从根节点开始，深度优先搜索，每搜索到一个叶节点，就得到一个解，找出所有的叶节点即终止,23,int main() int q;queen(1,8);cout“count=“ctn) /已经到达叶子节点 output(x,n); ct+; return; for (j=1;j=n;j+)if (place(i,j,x)=1) /当前层放置成功queen(i+1,n);elsexi=0; /放置不成功 ,25,#include #include /数组x表示皇后所放的位置，具体来说xi表示皇后i所放的列号 int ct=0; /ct 表示满足要求的皇后的摆法的个数 void output(int x,int n) for (int i=1;i=n;i+)cout“(“i“,“ xi“)“t“; coutendl; return ; ,26,/在第i行第j列放置一个皇后，然后检查放置是否满足约束 int place(int i,int j,int x) int k=1;xi=j; /放置皇后for(k=1;ki;k+) /检查皇后放置是否满足要求if( (xk=xi) | (abs(xk-xi)=abs(k-i) )return 0;return 1; ,
