java等价子树

Question

我有两棵树。树节点定义为

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. 
};

对于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多个节点

---

我现在做的是为类节点添加了一个新字段

class Cache{
   Map<String, Set<String>> map = new LinkedHashMap<String, Set<Str>>();
}

map的键是Node id，而值是这个nodeid的节点可以到达的ref集。缓存在节点初始化时启动

在IseEquivalent比较阶段，检查两个根的参考集之间是否存在重叠。如果没有，则返回false

我认为这有助于减少比较空间的数量

Answer 1

我不确定1) Both subtree leaves are leaves of original tree.要求，因为它似乎与how to identify equivalent substree for two given tree.冲突。否则，下面的递归方法应该能够覆盖其他两个条件。可以实现haveSameOriginalTree(r1, r2)方法来满足我无法理解的第一个条件r1和r2是需要检查等价性的两个子树的根

bool areEquivalent(Node r1, Node r2)
{
    if(r1.children == null && r2.children == null)
    {
        return (haveSameOriginalTree(r1, r2) && (r1.ref == r2.ref));
    }
    if((r1.children == null && r2.children != null) || (r1.children != null && r2.children == null))
    {
        return false;
    }
    // if here then both must be non-leaf nodes
    if(r1.type != r2.type)
    {
        return false;
    }
    if(r1.children.getCount() != r2.children.getCount()) // not sure of correct syntax for Java Sets
    {
        return false;
    }
    for(int i=0; i<r1.children.getCount(); i++)
    {
        if(!areEquivalent(r1.children[i], r2.children[i])) // again please correct the syntax for Sets
        {
            return false;
        }
    }

    return true;
}

让我知道你的想法

更新

下面是上述解决方案的迭代版本。它使用的堆栈数据结构是在堆上分配的，而不是在函数的调用堆栈上推送的，因此与递归没有太大区别，但仍然更好。此外，由于我们只保存对Node的引用（而不是复制整个对象），如果我们已经将原始树加载到内存中，这不应该是额外的内存开销

bool areEquivalent(Node r1, Node r2)
{
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node n1, n2;

    s1.Push(r1);
    s2.Push(r2);
    while(true) // Need a better check
    {
        if(s1.getCount() != s2.getCount())
        {
            return false;
        }
        if(s1.getCount() == 0) // if both stacks are empty then we've traversed both trees without failure.
        {
            return true;
        }
        n1 = s1.Pop();
        n2 = s2.Pop();
        if(!areEquivalentNodes(n1, n2))
        {
            return false;
        }
        foreach(Node child in n1.children)
        {
            s1.Push(child);
        }
        foreach(Node child in n2.children)
        {
            s2.Push(child);
        }
    }
}

// only checks the two nodes are equivalent. their childrens' equivalence will be handled by other calls to this method.
bool areEquivalentNodes(Node n1, Node n2)
{
    if(n1.children.getCount() != n2.children.getCount())
    {
        return false;
    }
    if(n1.children.getCount() == 0) // if both are leaf nodes...
    {
        if(n1.ref != n2.ref)
        {
            return false;
        }
    }
    else // both are non-leaf
    {
        if(n1.type != n2.type)
        {
            return false;
        }
        // the condition that children of non-leaf nodes be equivalent will be covered by subsequent calls this method...
    }

    return true;
}

请注意，这两种解决方案都需要children两个相同顺序的等效节点。如果children没有排序，那么我们需要在调用上述代码之前对它们进行排序

让我知道这是否更好