在Java中遍歷和過濾樹

Question

我在Java中有一個非二叉樹（請參閱下面的代碼），並給定一個輸入字符串，我需要按節點名稱過濾其節點。如果我找到一個節點，那麼整個父鏈應該出現在結果中，即使父名不匹配。

我想過從樹葉向上遍歷樹，但不知道該怎麼做。有任何想法嗎？

UPDATE

結果應該是一樣的樹，但與過濾樹葉，而不是葉名單。

Java代碼：

public class Tree<T> { 

    Node<T> root = null; 


    public Tree(Node <T> rootNode) { 
     root = rootNode; 
    } 


    public Node<T> searchFromRoot(int idToSearch) { 
     return recursiveSearch(idToSearch, root); 
    } 



    private Node<T> recursiveSearch(int idToSearch, Node<T> node){ 


     List <Node<T>>children = node.getChildren(); 

     Node<T> result = null; 

     for (Node<T> node2 : children) { 

      result = recursiveSearch(idToSearch, node2); 

      if (result != null) 
       break; 

     } 

     return result; 
    } 


    public Node<T> getRoot() { 
     return root; 
    } 



} 


public class Node<T> { 


    private List<Node<T>> children = new ArrayList<Node<T>>(); 

    private Node<T> parent = null; 

    private T data = null; 

    private int id = 0; 


    public static final int NODE_TYPE_FOLDER = 0; 

    private int nodeType = 0; 

    public Node(int id, int nodeType, T data) { 
     this.id = id; 
     this.nodeType = nodeType; 
     this.data = data; 
    } 

    public Node(T data, Node<T> parent) { 
     this.data = data; 
     this.parent = parent; 
    } 


    public boolean isLeaf() { 
     if (this.children.size() == 0) 
      return true; 
     else 
      return false; 
    } 



// getters and setters 

    public void addChild(int id, int nodeType, T data) { 
     Node<T> child = new Node<T>(id,nodeType,data); 
     child.setParent(this); 
     this.children.add(child); 
    } 

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


    public boolean isRoot() { 
     return (this.parent == null); 
    } 


} 

Answer 1

假設你有一個list包含了所有的葉子，你需要搜索name：

HashSet<String> result = new HashSet(); 
for(Node leaf: list) 
    search(false, name, leaf, result); 


public void search(boolean found, String name, Node node, HashSet<String> result){ 
    if(node == null) 
     return; 
    found = found ? found : node.getName().equals(name); 
    if(found) 
     result.add(node.getId()); 

    search(found, name, node.getParent(), result); 
} 

更新：

所以，而非ArrayList，我們可以只需存儲一個HashSet，其中包含所有已過濾節點的ID，因此您可以從根節點遍歷樹，並檢查節點的ID是否在結果集中，這有助於您重新設置使用樹。

Answer 2

你需要一個後序遍歷算法。它應該與您的方法recursiveSearch()幾乎相同。你可以谷歌算法。這很容易實現。

http://en.wikipedia.org/wiki/Tree_traversal#Post-order