算法分析与设计课件：习题选讲第七章前5题.ppt

《算法分析与设计课件：习题选讲第七章前5题.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计课件：习题选讲第七章前5题.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第七七章章n1426 电话号码前缀检索电话号码前缀检索n1310 二叉查找树，前序中序后序遍历二叉查找树，前序中序后序遍历n1210 二叉树二叉树，知道前序、后序求可能的方法数，知道前序、后序求可能的方法数n1090 最小生成树最小生成树n1156 二叉树的前序遍历二叉树的前序遍历2011-10-2011426 电话号码前缀检索电话号码前缀检索n题目大意题目大意：n给出给出N个电话号码（个电话号码（N=10000）,每个电每个电话号码的长度不大于话号码的长度不大于10，当存在一个电话，当存在一个电话号码是另外一个电话号码的前缀时，则会号码是另外一个电话号码的前缀时，则会发生冲突。如果不存在冲

2、突输出发生冲突。如果不存在冲突输出YES，否，否则输出则输出NO2011-10-2021426 电话号码前缀检索电话号码前缀检索n解题思路解题思路：n1.把把n个电话号码放进一个个电话号码放进一个set内内n2.枚举每个电话号码的前缀，查询是否存枚举每个电话号码的前缀，查询是否存在于在于set里里2011-10-2031426 电话号码前缀检索电话号码前缀检索nint n;nstring c11000;nset ss;nbool isConsistent()nnss.clear();nfor(int i=0;i n;i+)ss.insert(ci);nfor(int i=0;i n;i+)ns

3、tring st=;nfor(int j=0;j ci.size()-1;j+)nst+=cij;nif(ss.count(st)return false;nnnreturn true;n2011-10-2041310 二叉查找树二叉查找树n题目大意题目大意：n给出给出N个数，按照顺序建立一棵二叉查找树，个数，按照顺序建立一棵二叉查找树，然后输出该树的前序遍历，中序遍历，后然后输出该树的前序遍历，中序遍历，后序遍历。序遍历。2011-10-2051310 二叉查找树二叉查找树nstruct Node nint val;nint left,right;nNode(int val=0):val(v

4、al),left(0),right(0);n p300000;2011-10-2061310 二叉查找树二叉查找树nvoid Add(int root,int val)nn while(true)n if(proot.val val)n if(proot.right)root=proot.right;n else n proot.right=+tot；ptot=Node(val);return;n n else n if(proot.left)root=proot.left;n else n proot.left=+tot;ptot=Node(val);return;n n n 2011-10

5、-2071310 二叉查找树二叉查找树ninline void Preorder(int root)nnif(!root)return;nprintf(%d,proot.val);nPreorder(proot.left);nPreorder(proot.right);nninline void Inorder(int root)nnif(!root)return;nInorder(proot.left);nprintf(%d,proot.val);nInorder(proot.right);nninline void Postorder(int root)nnif(!root)return;

6、nPostorder(proot.left);nPostorder(proot.right);nprintf(%d,proot.val);n2011-10-2081210 二叉树二叉树n题目大意题目大意：n给出一棵二叉树前序遍历和后序遍历的顺给出一棵二叉树前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。树满足这样的遍历顺序。2011-10-2091210 二叉树二叉树n解题思路解题思路：n1.1.前序遍历第一个元素是根，后序遍历最后一个元素是前序遍历第一个元素是根，后序遍历最后一个元素是根根 n2.2.前序遍历第二个元素是某子

7、树的根，但左右不确定前序遍历第二个元素是某子树的根，但左右不确定 n3.3.在后序遍历中找到前序遍历的第二个元素，那么以这在后序遍历中找到前序遍历的第二个元素，那么以这个元素为基准，可以划分新的左右子树个元素为基准，可以划分新的左右子树 n4.4.当前序遍历的第二个元素出现在后序遍历的倒数第二当前序遍历的第二个元素出现在后序遍历的倒数第二位，以后序遍历倒数第三位起向左数都是子树的元素，但位，以后序遍历倒数第三位起向左数都是子树的元素，但是左右不确定，因此有是左右不确定，因此有2 2种情况种情况 2011-10-20101210 二叉树二叉树long long calc(string pre,s

8、tring post)long long ans=1;int len=pre.size();for(int i=0;i len-1;i+)int current=len-1;while(prei!=postcurrent)current-;if(current&prei+1=postcurrent-1)ans*=2;return ans;2011-10-20111090 最小生成树最小生成树n题目大意：给出题目大意：给出N=500个节点的无向图，个节点的无向图，每两个点之间都有一条无向边。问该无向每两个点之间都有一条无向边。问该无向图的最小生成树中，最长的一条边的长度。图的最小生成树中，最长的

9、一条边的长度。2011-10-20121090 最小生成树最小生成树n解题思路：解题思路：n 求最小生成树的算法中，有求最小生成树的算法中，有Prim算法和算法和kruskal算法。算法。Prim算法复杂度算法复杂度N2（N为点数）为点数）,Kruskal算法算法MlogM（M为边数）为边数）n 因此，对于稠密图而言，因此，对于稠密图而言，Prim算法的复杂度算法的复杂度更高效率。更高效率。2011-10-20131090 最小生成树最小生成树nint solve()nnfor(int i=0;i n;i+)ui=false,disti=e0i;nint ans=0,p;nfor(int i=

10、0;i n;i+)np=-1;nfor(int j=0;j distj)p=j;nnup=true;ans=max(ans,distp);nfor(int j=0;j n;j+)nif(uj|distj=epj)continue;ndistj=epj;nnnreturn ans;n2011-10-20141156 二叉树的前序遍历二叉树的前序遍历n题目大意：给定一棵题目大意：给定一棵N个节点的二叉树，输个节点的二叉树，输出其前序遍历的顺序出其前序遍历的顺序n解题思路：解题思路：n1.按照题目要求把二叉树读入按照题目要求把二叉树读入n2.以前序遍历顺序输出（可参考以前序遍历顺序输出（可参考131

11、0）2011-10-20151156 二叉树的前序遍历二叉树的前序遍历nvoid Read_Tree()nnmemset(is_root,0,sizeof(is_root);nchar c;nint l,r,m;nfor(int i=0;i m c l r;nis_rootm=!is_rootm;nis_rootl=!is_rootl;nis_rootr=!is_rootr;npm.Left=l;pm.Right=r;pm.ch=c;nnfor(int i=1;i=1000;i+)if(is_rooti)root=i;n2011-10-20161156 二叉树的前序遍历二叉树的前序遍历nvoid Preorder(int root)nnif(!root)return;ncout proot.ch;nPreorder(proot.Left);nPreorder(proot.Right);n2011-10-2017谢谢！谢谢！2011-10-2018