一道面试题，想不到好的算法，大家一起看看

dragonfont

题目：
f b, b c, a c, e b, d a, g a

two letters are tuples with each tuple separated by commas. The first letter in each tuple is a node and the second letter is the parent of the node. Please write a function that takes the string as input, and outputs a representation of the tree that the nodes form.

dragonfont

没有说树是什么树，如果是二叉树还好处理一些，否则太麻烦了。

cugb_cat

可以都按二叉树来做。

cjaizss

这与二叉树什么的没关系
树的表示规则可以这样：
tree,node,brothers为非终止符号
tree->node(brothers)
tree->node
brothers->tree
brothers->brothers,tree
node->[a-zA-Z]+
比如
a(b,c,d(e,f))
就表示
a有三个子——a,c,d
d有两个子——e,f

[ 本帖最后由 cjaizss 于 2008-2-28 23:56 编辑 ]

cjaizss

在这个规则诱导的语言下，题目的树应该是
c(b(f,e),a(d,g))

[ 本帖最后由 cjaizss 于 2008-2-28 23:59 编辑 ]

Edengundam

原帖由 cjaizss 于 2008-2-28 23:35 发表
在这个规则诱导的语言下，题目的树应该是
f(b(c(a(d,g)),e))

看错了?
b is the parent of f

f b,...

cjaizss

原帖由 Edengundam 于 2008-2-28 23:52 发表



看错了?
b is the parent of f

f b,...

呵呵，已修改

cugb_cat

原帖由 cjaizss 于 2008-2-28 23:30 发表
这与二叉树什么的没关系
树的表示规则可以这样：
tree,node,brothers为非终止符号
tree->node(brothers)
tree->node
brothers->tree
brothers->brothers,tree
node->[a-zA-Z]+
比如
a(b,c,d(e,f))
就 ...

其实还是二叉树，所有的树结构，包括森林都是可以用左孩子右兄弟的二叉树来表示。这样其实还是可以看作一棵二叉树。

dragonfont

"其实还是二叉树，所有的树结构，包括森林都是可以用左孩子右兄弟的二叉树来表示。这样其实还是可以看作一棵二叉树。"

如果节点度大于2就不是二叉树了吧？

cugb_cat

原帖由 dragonfont 于 2008-2-29 00:07 发表
"其实还是二叉树，所有的树结构，包括森林都是可以用左孩子右兄弟的二叉树来表示。这样其实还是可以看作一棵二叉树。"

如果节点度大于2就不是二叉树了吧？

节点度？什么概念？节点的子节点的个数吗？如果是这个概念，那左孩子右兄弟就是解决这个问题的，乍看起来，有点不像问题描述的关系，但这棵二叉树如何解释就是另外一回事了。