年江苏省数据总结深入.pdfVIP

年江苏省数据总结深入 1、对一般二叉树，仅根据一个先序、中序、后序遍历， 不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相 等的结点，根据此性质，可将任一遍历序列转为另一遍历序列 （即任一遍历序列 均可确定一棵二叉树）。 void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2) //将满二叉树的先序序列转为后序序列，l1,h1,l2,h2 是序列初始和最后结点的下 标。 {if(h1gt;=l1) {post[h2]=pre[l1]; //根结点 half=(h1-l1)/2; //左或右子树的结点数 PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost 32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指 针pre，初始为空。第一个叶子结点由指针head 指向，遍历到叶子结点时，就 将它前驱的rchild 指针指向它，最后叶子结点的rchild 为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt) //中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt-gt;lchild); //中序遍历左子树 if(bt-gt;lchild==nullamp;amp; bt-gt;rchild==null)//叶子结点 if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre-gt;rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt-gt;rchild); //中序遍历左子树 pre-gt;rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为O(n),辅助变量使用head 和pre,栈空间复杂度O(n) 2、在有向图G 中，如果r 到G 中的每个结点都有路径可达，则称结点r 为G 的 根结点。编写一个算法完成下列功能： （1）．建立有向图G 的邻接表存储结构； （2）．判断有向图G 是否有根，若有，则打印出所有根结点的值。 3、设T 是一棵满二叉树，编写一个将T 的先序遍历序列转换为后序遍历序列的 递归算法。 4、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs() 前，已访问完有向图的全部顶点 （设为n 个），则有向图有根，v 为根结点。将n 个顶点从1 到n 编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有 向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局 变量。建立有向图g 的邻接表存储结构参见上面第2 题，这里只给出判断有向图 是否有根的算法。 int num=0， visited[]=0 //num 记访问顶点个数,访问数组visited 初始化。 const n=用户定义的顶点数; AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v) {visited [v]=1; num++; //访问的顶点数＋1 if (nu m==n) {printf( “%d 是有向图的根。\n”,v); num=0;}//if p=g[v].firstarc; while (p) {if (visied[p-gt;adjvex]==0) dfs (p-gt;adjvex); p=p-gt;next;}//while visited[v]=0; num--; //恢复顶点v }//dfs void JudgeRoot() //判断有向图是否有根，有根则输出之。 {static int i ; for (i=1;ilt;=n;i++ )//从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根时，输出顶点在邻接表中的序