树

您所在的位置：网站首页 › 搜索转换方法 › 树

树

2024-06-21 13:29| 来源: 网络整理| 查看: 265

总时间限制: 5000ms

内存限制: 65536kB

描述

我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：

0 0 / | \ / 1 2 3 ===> 1 / \ \ 4 5 2 / \ 4 3 \ 5

现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。

输入

输入包括多行，最后一行以一个#表示结束。每行是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。你可以认为每棵树的结点数至少为2，并且不超过10000。

输出

对于每棵树，按如下格式输出转换前和转换后树的高度： Tree t: h1 => h2 其中t是树的编号（从1开始），h1是转换前树的高度，h2是转换后树的高度。

样例输入

dudduduudu ddddduuuuu dddduduuuu dddduuduuu #

样例输出

Tree 1: 2 => 4 Tree 2: 5 => 5 Tree 3: 4 => 5 Tree 4: 4 => 4 #include #include #include #include using namespace std; const int MAX_NODE = 100005; char s[MAX_NODE*2]; int main() { int cnt = 0; while (cin.getline(s, MAX_NODE*2)) { if (s[0] == '#') break; int n = strlen(s); int d = 0; int tree_dep = 0, btree_dep = 0; /* general tree */ for (int i = 0; i < n; ++i) { int add = s[i] == 'd' ? 1 : -1; d += add; tree_dep = max(d, tree_dep); } /* binary tree */ stack fa; d = 0; for (int i = 0; i < n; ++i) { if (s[i] == 'd') { fa.push(d); d += 1; } else { if (s[i+1] == 'd') d += 1, ++i; else { d = fa.top(); fa.pop(); } } btree_dep = max(d, btree_dep); } /* print result */ printf("Tree %d: %d => %d\n", ++cnt, tree_dep, btree_dep); } system("pause"); return 0; }

【分析】

先考虑如果是二叉树，如何计算深度？

初始时dep=0，d的时候++dep，u的时候--dep，dep的最大值即为深度

那么如果是把一般的树当做二叉树呢？

d的时候走向left_child，++dep；ud的时候走向right_sibling，++dep；u(u)的时候返回父节点，dep要减小

dep减小多少呢？注意不是--了，而应该用栈存储返回到的深度

【本文地址】

树

树

今日新闻

推荐新闻