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