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

对于叶子，子集是空的。

我想知道是否有一些现有的有效工作完成了如何识别两个给定树的等效子树。等效定义为：

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。

我认为这可以帮助减少比较空间的数量。

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

让我知道你的想法。

更新

这是上述解决方案的迭代版本。它使用在堆上分配的堆栈数据结构，而不是在函数的调用堆栈上推送，因此与递归没有太大区别，但仍然更好。此外，由于我们只保存对 s 的引用（而不是复制整个对象），如果我们已经将原始树加载到内存中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没有排序，那么我们需要在调用上面的代码之前对它们进行排序。

让我知道这是否更好。