用於比較樹之間的樹結構

我正在尋找一棵樹，最適合我的用例。樹應該包含類型硬件，的元件，其被包括可變的ElementType：用於比較樹之間的樹結構

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

的節點應該硬件元件的的ElementType之後被命名爲：

enter image description here

一旦我建立了幾棵樹（比如上面的那棵樹），我想將它們相互比較並檢查一棵樹是否是另一棵樹的一部分。例如。上面的樹應該與下面的樹進行比較，結果它應該讓我回來，第一棵樹是第二棵樹的一部分。樹木應通過其節點名稱（的ElementType）進行比較，因爲底層對象不同，每個樹中：

enter image description here

有什麼樹形的結構在Java中，這將適合我的要求是什麼？

來源

2013-11-22 ph09

這裏沒有，據我所知的結構，但它很容易實現

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。我敢肯定，它可以實施沒有遞歸....我只是不能打擾:)

來源

2013-11-22 08:26:14

Thx for this！我會稍後測試它，讓鄒知道:) – ph09

好吧，到目前爲止，具有樹結構的第一部分工作良好。但是比較算法不起作用。我試着用上面的例子，但是它給了我一個「錯誤」的回來，這是不對的，因爲第一棵樹的所有子樹都包含在第二棵樹中。在例子的「equalsIgnoreParent」方法中，將檢查子元素的大小，這是不正確的。我現在嘗試了幾個小時來提供我自己的解決方案，但這非常困難。 – ph09

啊，我顯然沒有完全理解你的問題。我的'''equalsIgnoreParent'''方法檢查兩個節點是否完全相同（忽略父節點）。你需要調整它以檢查是否所有'''other'''節點的元素都出現在''''this'''節點中（並且處於相同的深度）。這有點棘手，但可以完成。 –

我在我的其他答案得到了錯誤的想法。這是另一種嘗試：

public class Node { 
    // LinkedHashMap preserves order in which nodes were added 
    private Map<ElementType, Node> childMap = new LinkedHashMap<ElementType, Node>(); 
    private ElementType elementType; 

    public void addChild(Node node) { 
     if (childMap.containsKey(node.elementType)) { 
     throw new IllegalStateException("Duplicates not allowed"); 
     } 
     childMap.put(node.elementType, node); 
    } 

    public Collection<Node> getChildren() { 
     return childMap.values(); 
    } 

    /** 
    * Ensure all nodes in other are in this node. 
    * Ignore any extra elements in this that are not in other 
    */ 
    protected boolean isSameIgnoreExtras(Node other) { 
     if (this.elementType != other.elementType) return false; 
     if (this.childMap.size() < other.childMap.size()) return false; 

     for (Node otherChild : other.getChildren()) { 
     Node thisChild = childMap.get(otherChild.elementType); 
     if (thisChild == null) { 
      return false; 
     } 
     // recursive step 
     if (!thisChild.isSameIgnoreExtras(otherChild)) { 
      return false; 
     } 
     } 
     return true; 
    } 

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

來源

2013-11-25 10:52:11

用於比較樹之間的樹結構

回答

相關問題