java - 用于相互比较树木的树木结构

我正在寻找一棵最适合我的用例的树。树应包含硬件类型的元素，其中包括变量ElementType：

enum ElementType{
    Microcontroller;
    Core;
    Memory;
    Sensor;
    Pin;
    Network;
}

节点应以Hardware元素的ElementType命名：



建立好几棵树（如上面的树）后，我想将它们相互比较，并检查一棵树是否属于另一棵树。例如。上面的树应该与后面的树进行比较，因此它应该还给我，第一棵树是第二棵树的一部分。应该通过树的节点名（ElementType）比较这些树，因为每个树之间的基础对象都不同：



Java中是否有任何适合我需求的树结构？

最佳答案

据我所知，没有一个结构，但是很容易实现

public class Tree {
   private Node root;

   public boolean containsSubTree(Tree other) {
      return root.containsSubTree(other.root);
   }
}

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

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

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

  protected boolean equalsIgnoreParent(Node other) {
     if (elementType != other.elementType) return false;
     if (children.size() != other.children.size()) return false;
     for (int i = 0; i < children.size(); ++ i) {
        // recursive step
        if (!children.get(i).equalsIgnoreParent(other.children.get(i)) {
           return false;
        }
     }
     return true;
  }

  public boolean containsSubTree(Node other) {
     if (equalsIgnoreParent(other)) return true;
     for (Node child : children) {
        // recursive step
        if (child.containsSubTree(other)) return true;
     }
     return false;
  }
}

然后只需调用tree1.containsSubTree（tree2）进行检查。

如果要忽略子项的顺序，则可能会将子项存储为SortedSet，这将需要适当的Comparator。

我的解决方案是使用recursion实现的，这可能会导致call stack变深。我敢肯定，它可以在没有递归的情况下实现。。。。

关于java - 用于相互比较树木的树木结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20140019/