poj 2567 zzu10395 nyoj1254 Code the Tree(Prufer数列)

本文主要是介绍poj 2567 zzu10395 nyoj1254 Code the Tree(Prufer数列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description:

A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, …, n is given. The “Prufer” code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the new obtained tree, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n-1 numbers is called the Prufer code of the tree.
Your task is, given a tree, to compute its Prufer code. The tree is denoted by a word of the language specified by the following grammar:

T ::= “(” N S “)”

S ::= ” ” T S | empty

N ::= number

That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample input. To generate further sample input, you may use your solution to Problem 2568.
Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an “unrooted tree”.

Input

The input contains several test cases. Each test case specifies a tree as described above on one line of the input file. Input is terminated by EOF. You may assume that 1<=n<=50

Output

For each test case generate a single line containing the Prufer code of the specified tree. Separate numbers by a single space. Do not print any spaces at the end of the line.

Sample Input

(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))

Sample Output

5 2 5 2 6 2 8
2 3

做这道题真是一波三折。。起初用Vector邻接表 wa了自己就想当然的想了一组数据(1(1)(2)) vecotr邻接表肯定是wa了。所以就用指针做了。后来才发现 vector邻接表是这组数据错了(5(1(3(6)))) ，测试数组给的并没有重复的数字还是没有好好理解好题意。
指针做的比较难懂，我最下面也把vector邻接表做的贴上吧

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
struct node
{int num,index;node *next[55],*pre;node(){for(int i=0;i<55;i++)next[i]=NULL;num=index=0;pre=NULL;}
};
node *MIN;//存贮最小的叶子节点的指针 
int zuixiao;
void freenode(node *node)
{node=NULL;delete(node);
}
//深搜查找最小的叶子 
void dfs(node *root)
{if(root->index==0&&zuixiao>root->num){zuixiao=root->num;MIN=root;return ;}for(int i=1;i<=root->index;i++){dfs(root->next[i]);}
}
int main(){
//  freopen("in.txt","r",stdin);char str[250];while(gets(str)!=NULL){node *root=new node();root->num=-1;int len=strlen(str);bool isnum=false;int sum=0;int cnt=-1;for(int i=0;i<len;i++){isnum=false;sum=0;while(str[i]>='0'&&str[i]<='9'){isnum=true;sum=sum*10+str[i++]-'0';}if(isnum){root->index++,cnt++;;root->next[root->index]=new node();root->next[root->index]->pre=root;root->next[root->index]->num=sum;root=root->next[root->index];}if(str[i]==')'&&root->pre){root=root->pre;}}bool first=true;node *FA;while(cnt--){zuixiao=0x3fffffff;//这一点Wa了我一整天啊 一整天  //如果根节点下面只有一个子树，那么这个根节点也可能成为叶子节点 if(root->next[1]->index==1){zuixiao=root->next[1]->num;MIN=root->next[1];}dfs(root);FA=MIN->pre;if(FA==root){FA=root->next[1]=MIN->next[1];MIN->next[1]->pre=root; }else{for(int i=1;i<=FA->index;i++){//(5(1(3(6))))if(FA->next[i]==MIN){FA->next[i]=FA->next[FA->index];freenode(FA->next[FA->index]);FA->index--;break;}}}if(first)printf("%d",FA->num),first=false;elseprintf(" %d",FA->num);freenode(FA);freenode(MIN);}printf("\n");   freenode(root);}
}

#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
vector<int>link[250];
stack<int>s;
int fa,zuixiao,x;
void dfs(int child,int father){for(int i=0;i<link[child].size();i++){int j=link[child][i];if(link[j].size()==0&&child!=200){if(zuixiao>j){zuixiao=j;fa=child;}}elsedfs(j,child);}
}
int main(){char str[500];while(gets(str)!=NULL){memset(link,0,sizeof(link));while(!s.empty()) s.pop();int len=strlen(str);bool isnum=false;int sum=0;int cnt=-1;s.push(200);for(int i=0;i<len;i++){isnum=false;sum=0;while(str[i]>='0'&&str[i]<='9'){isnum=true;sum=sum*10+str[i]-'0';i++;}if(isnum){cnt++;link[s.top()].push_back(sum);s.push(sum);}if(str[i]==')')s.pop();}bool first=true;while(cnt--){zuixiao=0x3fffffff;if(link[link[200][0]].size()==1)zuixiao=link[200][0];dfs(200,200);if(zuixiao==link[200][0]){fa=link[zuixiao][0];link[200].clear();link[200].push_back(fa);}else{for(int i=0;i<link[fa].size();i++){if(link[fa][i]==zuixiao)link[fa].erase(link[fa].begin()+i);}}if(first)printf("%d",fa),first=false;elseprintf(" %d",fa);}printf("\n");}
}