数据结构电子课件教案-第6章-树与回溯法.ppt

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,JA是根，其余结点可以划分为3个互不相交的集合：T1=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树、森林的存储结构,双亲表示法通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。用一组连续的内存单元存储树的结点，每个结点包含两个域：一个数据域，一个“指针域”，用于指示其双亲结点在数组中的位置,双亲表示法孩子链表表示法左孩子-右兄弟存储表示法,5,typedefstructPTNodeElemdata;intparent;/双亲位置域PTNode;,A,B,C,D,E,F,G,r=0n=6,#defineMAX_TREE_SIZE100,dataparent,6,孩子链表表示法通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。与双亲表示法相反，孩子表示法适合实现涉及孩子的操作。还可以将双亲表示与孩子表示法结合：带双亲的孩子链表。,7,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G4,r=0n=6,datafirstchild,123,45,6,-1000224,8,structCTNodeintchild;CTNode*next;*ChildPtr;,structElemdata;ChildPtrfirstchild;/孩子链的头指针CTBox;,structCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,孩子节点结构,双亲节点结构,树结构,9,孩子兄弟（左孩子右兄弟）表示法孩子兄弟表示法用二叉链表作为树的存贮结构,classCSNodepublic:Elemdata;CSNode*firstchild;CSNode*nextsibling;,10,A,C,ABCEDFG,root,ABCEDFG,11,此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表,(a),(b),由此可将树与二叉树对应起来,树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。,12,3树、森林与二叉树的转换,13,3树、森林与二叉树的转换,14,4树和森林的遍历,树的遍历两种方法深度优先先（根）序遍历若树不空，则先访问根结点，然后依次先序遍历各棵子树。后（根）序遍历(中序遍历)若树不空，则先依次后序遍历各棵子树，然后访问根结点宽度优先（层次遍历）若树不空，则自上而下自左至右访问树中每个结点。,15,ABCDEFGHIJK,先根遍历时顶点的访问次序：,ABEFCDGHIJK,后根遍历时顶点的访问次序,EFBCIJKHGDA,层次遍历时顶点的访问次序,ABCDEFGHIJK,二叉树的先序遍历,二叉树的中序遍历,16,.树与问题求解,问题1：n皇后问题问题2：子集和问题问题3：分书问题问题4：稳定婚配问题,17,.树与问题求解,树作为问题求解过程的一种形象化表示方法状态空间树的节点表示问题求解过程中的一个状态状态转移：一个节点处理完毕后，转入处理其下一个节点，称为状态转移，每一步转移称为一个算子。状态生成：根据节点x的当前值，使用所有可用算子生成其所有可行的子节点，也称为节点生成，或节点扩展。问题求解过程：对状态树进行遍历的过程深度优先遍历宽度优先遍历,18,用状态空间进行问题求解要素解的表示（一般可以用多元组表示）初始状态可用的算子终止条件,下面我们用例子来说明,19,例1：n皇后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。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(i-k),22,终止条件：从根节点开始，深度优先搜索，每搜索到一个叶节点，就得到一个解，找出所有的叶节点即终止,23,intmain()intq;queen(1,8);coutcount=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所放的列号intct=0;/ct表示满足要求的皇后的摆法的个数voidoutput(intx,intn)for(inti=1;i=n;i+)cout(i,xi)t;coutendl;return;,26,/在第i行第j列