算法分析与设计PPT02-数据结构和STL - ZOJ1097.ppt

1、2.12 ZOJ1097-CODE THE TREE树（即无环图）的顶点，用整数树（即无环图）的顶点，用整数1，2，n编号。编号。Prufer码是按码是按如下步骤构造的树：找到编号最小的叶结点（只有一条边与该顶点相如下步骤构造的树：找到编号最小的叶结点（只有一条边与该顶点相连）。将该叶结点，及其相连的那条边，从图中中删掉。同时，记下连）。将该叶结点，及其相连的那条边，从图中中删掉。同时，记下与它连接的那个结点的编号。重复上面的步骤，直到剩下最后一个结与它连接的那个结点的编号。重复上面的步骤，直到剩下最后一个结点（顺便说一下，这个数就是点（顺便说一下，这个数就是n）。写下来的）。写下来的n1个数

2、的序列，就是个数的序列，就是该树的该树的Prufer码。码。编程任务：根据输入的树，计算该树的编程任务：根据输入的树，计算该树的Prufer码。码。描述树的语法规则如下：描述树的语法规则如下：T:=(N S)S:=T S|emptyN:=number126358714图图24 样例数据样例数据1的树的树输入样例输入样例(2(6(7)(3)(5(1)(4)(8)(1(2(3)(6(1(4)(2(3)(5)输出样例输出样例5 2 5 2 6 2 82 32 1 6 2 6树的周围有括号。树的周围有括号。第一个数是根结点编号，第一个数是根结点编号，后面跟有任意个子树后面跟有任意个子树（也可能一个也没

3、有），（也可能一个也没有），中间有一个空格。中间有一个空格。（1）样例分析）样例分析对样例数据对样例数据1，就是题目中的图。首先找到编号最小的叶，就是题目中的图。首先找到编号最小的叶结点，编号是结点，编号是1；将该叶结点及所在边去掉，并记下与之；将该叶结点及所在边去掉，并记下与之相连的结点编号：相连的结点编号：5。接着找编号最小的叶结点，编号是接着找编号最小的叶结点，编号是3；将该叶结点及所在；将该叶结点及所在边去掉，并记下与之相连的结点编号：边去掉，并记下与之相连的结点编号：2。2263587142635874图图25 去掉第一个叶结点去掉第一个叶结点1 图图26 去掉第二个叶结点去掉第二个

4、叶结点3输入样例输入样例(2(6(7)(3)(5(1)(4)(8)输出样例输出样例5 2 5 2 6 2 8（2）数据结构）数据结构结点编号结点编号12345678相邻结点相邻结点53 5 6 8251 2 42 762326358714将每个结点的相邻结点建立对应关系将每个结点的相邻结点建立对应关系数据结构：数据结构：vectorset adj(1024,set();算法算法2.11 读取数据，实现结点的数据结构读取数据，实现结点的数据结构void parse(vectorset&adj,unsigned int p=0)unsigned int x;cin x;/读取结点编号读取结点编号/

5、p0时，表示时，表示p是前面读取的结点编号是前面读取的结点编号if(p)/结点的相邻是对称的结点的相邻是对称的adjp.insert(x);adjx.insert(p);while(true)char ch;cin ch;/读取括号读取括号if(ch=)break;/如果是如果是)，递归返回，递归返回parse(adj,x);/否则是否则是(，递归调用，递归调用return;4输入样例输入样例(2(6(7)(3)(5(1)(4)(8)(1(2(3)(6(1(4)(2(3)(5)结点编号结点编号12345678相邻结点相邻结点53 5 6 8251 2 42 762（3）实现）实现PRUFER编

6、码编码从表中看出，当某结点只有一个相邻结点时，它就是叶子从表中看出，当某结点只有一个相邻结点时，它就是叶子结点。将所有这些叶子结点放到一个优先队列中，选出结结点。将所有这些叶子结点放到一个优先队列中，选出结点编号最小的那个结点，输出其相邻结点的编号，就是该点编号最小的那个结点，输出其相邻结点的编号，就是该结点的结点的Prufer编码。编码。l 对于表对于表216的样例数据，初始状态的叶子结点如下：的样例数据，初始状态的叶子结点如下：1，3，4，7，85结点编号结点编号12345678相邻结点相邻结点53 5 6 8251 2 42 76226358714（3）实现）实现PRUFER编码编码将这

7、些结点放到优先队列中自动排序，就获得了编号最小将这些结点放到优先队列中自动排序，就获得了编号最小的叶子结点的叶子结点1，输出其相邻结点编号，输出其相邻结点编号5，同时将结点，同时将结点5相邻相邻结点中的结点结点中的结点1删除。如果结点删除。如果结点5只有一个结点，则进入优只有一个结点，则进入优先队列。先队列。优先队列：优先队列：priority_queue int,vector,greater leafs;其中其中greater是队列的排序因子。是队列的排序因子。6结点编号结点编号12345678相邻结点相邻结点53 5 6 8251 2 42 762算法算法2.12 统计结点的个数统计结点的

8、个数,并将叶子结点进入并将叶子结点进入堆栈堆栈/定义优先队列定义优先队列leafspriority_queue int,vector,greater leafs;int n=0;/结点的个数结点的个数/对每一个结点，判断其相邻结点的个数是否是对每一个结点，判断其相邻结点的个数是否是1（叶子结点）（叶子结点）for(unsigned int i=0;iadj.size();i+)if(adji.size()n+;/统计结点的个数统计结点的个数if(adji.size()=1)/是叶子结点是叶子结点leafs.push(i);/进入优先队列进入优先队列7算法算法2.13 处理优先队列，并输出处理优先队列，并输出结果结果/结点是结点是n个个for(int k=1;k 1)cout ;cout p;/对称的，在结点对称的，在结点p中删除其相邻结点中删除其相邻结点xadjp.erase(x);/如果结点如果结点p也成为叶子结点，则进入优先队列也成为叶子结点，则进入优先队列if(adjp.size()=1)leafs.push(p);cout endl;8输出样例输出样例5 2 5 2 6 2 82 32 1 6 2 6