我有两棵树。树节点定义为
class Node{
String treeId;
String type; //Each node has type which has fixed value. For example, its color: RED, BLANK, GREEN
Set<Node> children;
String ref; //The ref is a string and allowed value are "0", "1",..."10". The value is null if it is not leaf.
};
对于叶子,子集是空的。
我想知道是否有一些现有的有效工作完成了如何识别两个给定树的等效子树。等效定义为:
1) Both subtree leaves are setsets leaves of original tree.
2) Both subtrees leaves have same ref value.
3) for non-leaves node, the equivalent refers to both node have same type and equivalent children.
谢谢。如果有一些Java库解决这个问题会更好。
输入应该是两个树根,而输出是等效子树的根节点。树的高度为 100~ 并且它有超过 500 个节点。
我现在所做的是为类 Node.js 添加了一个新字段。
class Cache{
Map<String, Set<String>> map = new LinkedHashMap<String, Set<Str>>();
}
map 的 key 是 Node id 而 value 是这个 nodeid 的这个节点可以到达的 ref 集。初始化 Node 时启动的 Cache。
在 isEquivalent 比较阶段,检查两个根的 ref 集之间是否存在重叠。如果没有,则返回 false。
我认为这可以帮助减少比较空间的数量。