N元樹等於

Question

我做了這個結構來表示的N叉樹：

public class MyTree { 
    public int data; 
    LinkedList<MyTree> children; 


    public MyTree(int data) { 
     this.data = data; 
     this.children = new LinkedList<>(); 
    } 

    public void addChild(MyTree child) { 
     this.children.addFirst(child); 
    } 

    public boolean equals(MyTree root) { } 
} 

我也做了一些其他的方法，但它們不是這種方法的核心，所以我不顯示它給你。但是，讓我們談談等於的方法： 如何檢查兩棵樹在結構和值上是否相等？我的意思是他們是平等的只有：

8    
/| \20 
9 10  
| 
20 
| 
30 
/| \ 
40 50 70 


    8    
/|\20 
9 10  
| 
20 
| 
30 
/| \ 
40 50 70 

所以我的想法是在同一時間（一個與this.tree和一個與輸入的樹）做兩個遞歸，當機能的研究探索的第一個節點比較它與第一第二樹等（他們必須尊重相同的順序和價值！）是這樣的：

public boolean equals(MyTree t) { 

    boolean result = true; 
    if (this == null && t == null) { 
     return false; 
    } 
    if (this == null || t == null) { 
     return false; 
    } 
    if (this.getValue() != t.getValue()) { 
     return false; 
    } 
    if (this.getChildren().size() != t.getChildren().size()) { 
     return false; 
    } 

    if (this.getChildren().size() == t.getChildren().size()) { 
     for (int i = 0; i < getChildren().size(); i++) { 
      MyTree object = t.getChildren().get(i); 
      MyTree object1 = this.getChildren().get(i); 
      result = object1.equals(object); 
      if (result == false) { 
       return false; 
      } 
     } 
    } 

    return result; 
} 

但我不知道如何在同一時間兩棵探索，我例如，做了一個dfs預訂，但在這種方法中，你必須同時探索兩棵樹。你能給我一個算法來同時探索兩棵樹嗎？ 我的測試：

 MyTree t1 = new MyTree(8); 
     t1.addChild(new MyTree(9)); 
     t1.addChild(new MyTree(10)); 
     MyTree t2 = new MyTree(20); 
     t2.addChild(new MyTree(40)); 
     t2.addChild(new MyTree(30)); 
     MyTree t3 = new MyTree(25); 
     t3.addChild(new MyTree(80)); 
     t3.addChild(new MyTree(70)); 
     t3.addChild(new MyTree(95)); 
     t2.addChild(t3); 
     t1.addChild(t2); 

     MyTree t4 = new MyTree(8); 
     t4.addChild(new MyTree(9)); 
     t4.addChild(new MyTree(10)); 
     MyTree t5 = new MyTree(20); 
     t5.addChild(new MyTree(40)); 
     t5.addChild(new MyTree(30)); 
     MyTree t6 = new MyTree(25); 
     t6.addChild(new MyTree(80)); 
     t6.addChild(new MyTree(70)); 
     t6.addChild(new MyTree(95)); 
     t5.addChild(t6); 
     t4.addChild(t5); 
     System.out.print(t1.equals(t4)); 

Answer 1

遞歸將是如下：樹僅相當於如果相應的數據等於，孩子大小是平等的，每個孩子都等於

public class MyTree { 
public int data; 
LinkedList<MyTree> children; 


public MyTree(int data) { 
    this.data = data; 
    this.children = new LinkedList<>(); 
} 

public void addChild(MyTree child) { 
    this.children.addFirst(child); 
} 

public boolean equals(MyTree root) { 
    if (root == null || root.children.size() != children.size() || data != root.data) return false; 

    Iterator<MyTree> myTreeIterator = children.iterator(); 
    Iterator<MyTree> rootTreeIterator = root.children.iterator(); 
    while (myTreeIterator.hasNext() && rootTreeIterator.hasNext()) { 
     if (!myTreeIterator.next().equals(rootTreeIterator.next())) return false; 
    } 
    return true; 
} 
} 

UPD：@Gene建議

public class MyTree { 
public int data; 
LinkedList<MyTree> children; 


public MyTree(int data) { 
    this.data = data; 
    this.children = new LinkedList<>(); 
} 

public void addChild(MyTree child) { 
    this.children.addFirst(child); 
} 

@Override 
public boolean equals(Object o) { 
    return this == o || !(o == null || getClass() != o.getClass()) && equals((MyTree) o); 
} 

public boolean equals(MyTree root) { 
    return !(root == null || data != root.data) && children.equals(root.children); 
} 
}