如何遍歷一個N叉樹

Question

我的樹/節點類：

import java.util.ArrayList; 
import java.util.List; 

public class Node<T> { 
    private T data; 
    private List<Node<T>> children; 
    private Node<T> parent; 

    public Node(T data) { 
     this.data = data; 
     this.children = new ArrayList<Node<T>>(); 
    } 

    public Node(Node<T> node) { 
     this.data = (T) node.getData(); 
     children = new ArrayList<Node<T>>(); 
    } 

    public void addChild(Node<T> child) { 
     child.setParent(this); 
     children.add(child); 
    } 

    public T getData() { 
     return this.data; 
    } 

    public void setData(T data) { 
     this.data = data; 
    } 

    public Node<T> getParent() { 
     return this.parent; 
    } 

    public void setParent(Node<T> parent) { 
     this.parent = parent; 
    } 

    public List<Node<T>> getChildren() { 
     return this.children; 
    } 
} 

我知道如何遍歷二叉樹，但遍歷n元似乎更棘手。

我該如何去遍歷這棵樹。我在遍歷樹時需要一個計數器來對樹中的每個節點進行編號/計數。

然後在特定的計數下，我可以停止並返回該計數的節點（可能刪除該子樹或在該位置添加子樹）。

Answer 1

最簡單的方法是實施這樣一個訪問者模式：

public interface Visitor<T> { 
    // returns true if visiting should be cancelled at this point 
    boolean accept(Node<T> node); 
} 

public class Node<T> { 
    ... 

    // returns true if visiting was cancelled 
    public boolean visit(Visitor<T> visitor) { 
     if(visitor.accept(this)) 
      return true; 
     for(Node<T> child : children) { 
      if(child.visit(visitor)) 
       return true; 
     } 
     return false; 
    } 
} 

現在你可以使用這樣的：

treeRoot.visit(new Visitor<Type>() { 
    public boolean accept(Node<Type> node) { 
     System.out.println("Visiting node "+node); 
     return false; 
    } 
}); 

或者爲特定的任務：

class CountVisitor<T> implements Visitor<T> { 
    int limit; 
    Node<T> node; 

    public CountVisitor(int limit) { 
     this.limit = limit; 
    } 

    public boolean accept(Node<T> node) { 
     if(--limit == 0) { 
      this.node = node; 
      return true; 
     } 
     return false; 
    } 

    public Node<T> getNode() { 
     return node; 
    } 
} 

CountVisitor<T> visitor = new CountVisitor<>(10); 
if(treeRoot.visit(visitor)) { 
    System.out.println("Node#10 is "+visitor.getNode()); 
} else { 
    System.out.println("Tree has less than 10 nodes"); 
}