首页 > 代码库 > POJ 3437 Tree Grafting(有序树转化为二叉树)
POJ 3437 Tree Grafting(有序树转化为二叉树)
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 1834 | Accepted: 795 |
Description
- there is one node designated as the root, denoted root(T);
- the remaining nodes are partitioned into subsets T1, T2, ..., Tm, each of which is also a tree (subtrees).
It is often more convenient to represent an ordered tree as a rooted binary tree, so that each node can be stored in the same amount of memory. The conversion is performed by the following steps:
- remove all edges from each node to its children;
- for each node, add an edge to its first child in T (if any) as the left child;
- for each node, add an edge to its next sibling in T (if any) as the right child.
This is illustrated by the following:
0 0 / | \ / 1 2 3 ===> 1 / \ 4 5 2 / 4 3 5
In most cases, the height of the tree (the number of edges in the longest root-to-leaf path) increases after the conversion. This is undesirable because the complexity of many algorithms on trees depends on its height.
You are asked to write a program that computes the height of the tree before and after the conversion.
Input
The input is given by a number of lines giving the directions taken in a depth-first traversal of the trees. There is one line for each tree. For example, the tree above would give dudduduudu, meaning 0 down to 1, 1 up to 0, 0 down to 2, etc. The input is terminated by a line whose first character is #. You may assume that each tree has at least 2 and no more than 10000 nodes.
Output
For each tree, print the heights of the tree before and after the conversion specified above. Use the format:
where t is the case number (starting from 1), h1 is the height of the tree before the conversion, and h2 is the height of the tree after the conversion.Tree t: h1 => h2
Sample Input
dudduduudu ddddduuuuu dddduduuuu dddduuduuu #
Sample Output
Tree 1: 2 => 4 Tree 2: 5 => 5 Tree 3: 4 => 5 Tree 4: 4 => 4
Source
#include <iostream> #define maxn 20005 using namespace std; char s[maxn]; int height1,height2; int i; void dfs(int a,int b) { int tempson=0; while(s[i]=='d') { i++; tempson++; //tempson 代表第几个 儿子 dfs(a+1,b+tempson); } i++; height1=a>height1?a:height1; height2=b>height2?b:height2; } int main() { int n=1; while(cin>>s) { if(s[0]=='#') break; i=0; height1=height2=0; dfs(0,0); cout<<"Tree "<<n <<": "<<height1<<" => "<<height2<<endl; n++; } return 0; }
这道题我一定会回来再做!