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

cjaizss

原帖由 cugb_cat 于 2008-2-29 00:02 发表

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

恩，这种表示法确实是可以的，如果把我的引导规则以brothers为起始符号（现在是tree为起始符号），也可以表示森林，诱导的语言和这个二叉树表示完全一致。

cjaizss

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

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

只是二叉树表示多叉树的一种方法，这种方法保留父子关系，兄弟的顺序关系（哥哥与弟弟），如果引入空节点（特殊节点），还可以表示排行。这与我举的那个表示语言是一致的，那个语言也可以引入单个的逗号，也可以表示排行。

dragonfont

看了两位版主的留意，看得有点糊涂了。

这与二叉树什么的没关系
树的表示规则可以这样：
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

这个是表示规则，但是用计算机怎么表示呢？
比如一个父节点有n个子节点，那么设计节点结构的时候要设计n个指向子节点的指针？？

dxcnjupt

单纯从楼主的题目来看......

遍历所有规则
1若有新出现的字母
为每个新出现的字母分配
tn = new tree-node
tn->letter=字母
tn->left = null; tn->right = null
2无论有没有新出现的字母
找到后一个字母和前一个字母的tree-node项first-node, second-node
if second-node->left == null
     second-node->left = first-node
else if second-node->right == null
     second-node->right = first-node
else
     error

题目既没有要求验证正确性，也没有要求效率...........

cugb_cat

原帖由 dragonfont 于 2008-2-29 10:15 发表
看了两位版主的留意，看得有点糊涂了。

这与二叉树什么的没关系
树的表示规则可以这样：
tree,node,brothers为非终止符号
tree->node(brothers)
tree->node
brothers->tree
brothers->brothers,tree
...

      a
    / | \
   b  c  d
可以表示成：
      a
     /
    b
     \
      c
       \
        d
这不就成了二叉树了？

cjaizss

tree->node(brothers)
tree->node
brothers->tree
brothers->brothers,tree
node->[a-zA-Z]+
如果用以上所诱导的语言表达输出：
我们先分析一下这个语言，比方
a(b,c(d,e))
abcde是树的前序遍历的结果，而左括号，右括号，逗号对应着遍历的栈操作中的动作（这个具体自己去想吧）
第一种算法：先构造一棵链接的树，然后通过链接的树生成这个语言，输出：很简单明了，但是土；
第二种算法：根本不需要这棵链接的树，一直利用这个语言来表达树，这才是王道。
关键在于树如何生成呢？其实这里是森林的生成
因为构造树的时候并非是按照某种遍历，而是随机的在树的任何部位加上一根树枝，离散的树枝那么一开始就会有森林的出现。

feiyang21687

提供一个解决方法：
数据结构：
<code>
class Node {
private:
    char elem;
    vector<Node> children;
}
</code>

构造方法：
1. 初始化一个map<char, Node>（char代表当前遇到的根, Node代表根的孩子）。
2. 解决一个Tuple（元组，例如（b,f），先找父亲是否在map中，若不在执行3，不在执行4。
3. 取出根的孩子，把元组的孩子添加进来，执行5。
4. 用这个元组初始化一个Node对象，把根添加到map中去。
5. 是否还有其余元组，若有则返回执行1，否则退出。

这样最后通过map即可获得这棵树。当然这时候得找出树根，为了方便，可以在构造过程中跟踪判断根。或者判断那个节点的孩子数最多就行了。不过还是第一种比较好点。