Java算法：比较树是否存在子树

Question

我将为您提供一种算法，用于比较两个树，并检查其中一个树是否为另一个树的子树。

首先，我提供了自己的树实现，其结构如下：

public class PlatformTree {
   private HwNode root;

   .......
}

public class HwNode {
  private HwNode parent;
  private ElementType elementType;
  private Hardware hw;
  private List<Node> children = new ArrayList<Node>();

  public Node(Node parent, ElementType elementType, Hardware hw) {
     ...
  }

  public void addChild(Node child) {
     children.add(child);
  }

  ....

以下图片可以让您了解情况：

树1

树2

如图所示，我想要检查树1的所有子树是否包含在树2中。这些树的根节点仅是虚拟元素，用于访问子树。

我总是检查树1的子树是否包含在树2中。类型为Tree1的节点始终具有一个后继节点（Microcontroller.Memory），而类型为Tree2的节点可以具有多个后继节点（Microcontroller.Memory/Memory/Memory）。

ElementType确定节点是否相等。

比较方法应返回True，如果所有子树都包含在另一棵树中，则返回False。我试图提供一个算法，但我仍然有一些递归调用的问题。到目前为止，我已经做了以下工作：

类TreePlatform:

public boolean containsSubTree(PlatformTree tree1) {
        Boolean b = true;

        // check all subtrees of Tree1
        if (tree1.getRoot() != null && getRoot() != null) {
            for (HwNode subRootNode : tree1.getRoot().getChildren()) {
                b = getRoot().containsSubTree(subRootNode);
            }
        } else {
            return false;
        }
        return b;
    }

Class HwNode

public boolean containsSubTree(HwNode abstractNode) {
    for (HwNode subRootNode : getChildren()) {
        if (hasSubTree(subRootNode, abstractNode)) {
            return true;
        }
    }
    return false;
}

private boolean hasSubTree(HwNode subRootNode, HwNode abstractNode) {
    if (subRootNode.getElementType() != abstractNode.getElementType()) {
        return false;
    }
    if (!abstractNode.getChildren().isEmpty()) {
        if (!subRootNode.getChildren().isEmpty()) {
            HwNode abstractSubNode = abstractNode.getChildren().get(0);
            for (HwNode subNode : subRootNode.getChildren()) {
                if (!hasSubTree(subNode, abstractSubNode)) {
                    return false;
                }
            }
        } else {
            return false;
        }
    } else if (subRootNode.getChildren().isEmpty()) {
        return true;
    }
    return true;
}

我对我的算法还不满意，但目前卡住了，不知道如何解决。有什么想法可以将两个树进行比较吗？

- ph09

---

你的问题是什么？请简明扼要地说明需要的内容。 - Prateek

我需要一个符合我的要求的可行算法。 - ph09

图同构是计算机科学中的一个独特问题。幸运的是，对于树来说比一般问题要容易：http://en.m.wikipedia.org/wiki/Graph_isomorphism_problem#CITEREFAhoHopcroftUllman1974。 - Adam Gent

Answer 1

好的，这个问题是关于在另一个树中查找一个树的问题。如果树有顺序，那么这是一个标准的面试问题，但是你的树没有顺序，这使得问题变得更加复杂。同样地，如果我们正在寻找树的“同余”而不是“包含”，并且如果我们可以使用Adam Gent在OP的评论中提到的Kelly's Theorem并计算子树，则会更加容易。

为了清晰起见，我将称两棵树为“模式树”和“目标树”。我们要测试模式树是否是目标树的子树。

你的方法是（虽然我可能理解错了），模式树中的节点P等价于目标树中的节点T，如果P的每个子节点都等于T中的一个节点。问题在于，如果P有两个相同的子树怎么办？它将与仅具有一个子树的节点T匹配！

现在这不是致命的缺陷：如果我们认为已经找到了匹配，我们可以通过删除T的子树，然后在以后发现我们错误时进行大量回溯来适应这种方法。不过，这有点容易导致组合爆炸。

更好的方法是从下往上递归，而不是从上往下。我的意思是：

- 检查模式树的所有叶子是否出现在目标树中。 - 如果是，则构建一个字典D，将模式树的叶子映射到目标树中匹配的叶子列表（可能有多个！）。 - 检查模式树的所有高度为1的子树是否出现在目标树中。 - 要做到这一点，假设我们有一个来自模式树的高度为1的节点Q，其叶子为X和Y。 - 使用字典获取与X和Y匹配的目标树中的叶子列表。过滤这些列表，以使目标树中的任何叶子最多只出现一次（这处理了X等于Y的情况） - 看看在目标树中与X匹配的某个叶子是否与与Y匹配的叶子具有共同的父节点。 - 如果是，太好了！如果此父项与Q相同类型，则匹配！找到所有这样的父项-我们需要它们进行下一步操作。 - 如果模式树的所有高度为1的子树确实出现在目标树中，则构建一个新字典，将它们映射到目标树中匹配的高度为1的树列表。 - 重复，使用高度为1的字典构建高度为2的树字典。 - 重复，构建高度为3的树字典-你懂的。最终，您将到达模式树的根，完成操作。

这个算法的时间复杂度为二次方，虽然不是很好，但通常的谷歌搜索并没有揭示更好的算法（主要是因为二叉树/有序树变体已经充斥了搜索空间）。如果有人知道更好的算法，我会很高兴听到。使用凯利定理针对所有子树进行计算的话，Naively的时间复杂度为立方级别，但是通过一些记忆化技巧，可能会降至二次方。

- Andy Jones