您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

求单支树集的共享树

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

求单支树集的共享树

发表于：2008-01-01 16:22:57 楼主

已知有一个树的集合，其中每个树都是单支树，树上的节点来自于一个节点集合，现给出一个虚拟节点根，树集合中的树为树枝，构造一颗以该节点为根的树，要求树中的节点数最少。（在构造过程中，单支树中的节点可以在树中调换位置，相同的节点可以共享，但不允许加入新的边，除了各树枝连到虚拟根节点的边外)
比如，2个树的集合
树1：1-2-3-4-5-6
树2：4-5-3-7-8
虚拟节点根0
那么构造的树就是
0-3-4-5-1-2-6
-7-8
3、4、5节点发生了共享，使得新树中的节点数只有1+3+3+2=9；而不是没共享的树的节点数1+6+5=12。
求一个算法解决这个问题

发表于：2008-01-01 20:12:261楼得分:0

再给个例子
1-4-5-6-7
1-2-3
1-2-9-4-5-6-7
1-2-8

依次选最大的共享，得到
1-2-3
-9-4-5-6-7
-8
-4-5-6-7
树中有3+5+1+4=13个节点
而问题的解是
1-4-5-6-7
-2-9
-2-3
-8
树中有5+2+2+1=10个节点

发表于：2008-01-01 20:14:402楼得分:0

再给个例子
1-4-5-6-7
1-2-3
1-2-9-4-5-6-7
1-2-8

依次选最大的共享，得到
1-2-3
-9-4-5-6-7
-8
-4-5-6-7
树中有3+5+1+4=13个节点
而问题的解是
1-4-5-6-7
¦ ¦
¦ -2-9
-2-3
¦
-8
树中有5+2+2+1=10个节点

下一篇：测试了好多数据都是对的，可是提交就是过不了（括号匹配问题)
上一篇：a*算法估价函数问题

其他资讯