|
Tree Grafting
Description
Trees have many applications in computer science. Perhaps the most commonly used trees are rooted binary trees, but there are other types of rooted trees that may be useful as well. One example is ordered trees, in which the subtrees for any given node are
ordered. The number of children of each node is variable, and there is no limit on the number. Formally, an ordered tree consists of a finite set of nodes T such that
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:
This is illustrated by the following:
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 |
首先,贴上多叉树转二叉树的方法:
方法非常简单,"左儿子,右兄弟"
就是将一个节点的第一个儿子放在左儿子的位置,下一个的儿子,即左儿子的第一个兄弟,
放在左儿子的右儿子位置上,再下一个兄弟接着放在右儿子的右儿子.
由题目给出的字符串,可以轻松求出多叉树.但是题目问的是转为二叉树的高度......
由于多叉树转二叉树的方法是"左儿子右兄弟",因此 二叉树中X节点的高=二叉树中X的父节点的高+X是第几个儿子-1
形成了一个递归定义. 可以用递归算法解决.
PS:在 "数据结构编程实验"这本书上看到的题目,本来没思路想学习标程,可是标程用到了很多C语言中我没有用过的IO函数.最后硬着头皮自己想.居然AC了,而且代码很精简,,看来自己不是笨的无可救药啊,不能放弃治疗
#include <iostream>
using namespace std;
string s;
int i,n=0,height1,height2;
void work(int level1,int level2,int son){
int tempson=0;
while (s[i]==‘d‘){
i++; tempson++;
work(level1+1,level2+tempson,tempson);
}
height1=level1>height1?level1:height1;
height2=level2>height2?level2:height2;
i++;
}
int main()
{
while (cin>>s && s!="#"){
i=height1=height2=0;
work(0,0,1);
cout<<"Tree "<<++n<<": "<<height1<<" => "<<height2<<endl;
}
return 0;
}kdwycz的网站： http://kdwycz.com/
kdwyz的刷题空间：http://blog.csdn.net/kdwycz
POJ 3437 Tree Grafting 多叉树转二叉树
原文：http://blog.csdn.net/kdwycz/article/details/19674385