在Java中遍歷和過濾樹

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


}

來源

2015-05-04 ps0604

這聽起來像你的家庭作業;-) – NaN

它可能，但它是一個問題，我試圖解決在工作中，我有一個屏幕文件夾，一個搜索按鈕，我需要過濾樹。 – ps0604

你不應該從樹葉開始。那麼你的樹結構的重點是什麼？您可以從根節點遍歷樹，並根據需要輸出路徑。例如，您可能想要檢查後續遍歷。 – Joffrey

假設你有一個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是否在結果集中，這有助於您重新設置使用樹。

來源

2015-05-04 09:58:40

結果必須是一棵樹，只顯示過濾的葉子 – ps0604

@pgschr只有一種方法從根到樹中的任何節點，所以數組列表就足夠了，除非有多個匹配？那麼是否有不止一場比賽？ –

沒錯，但最終的結果需要是一個帶過濾葉子的樹。每個假期都有一個根節點的途徑，所以最終的結果應該是從葉子到根節點的所有路徑，以滿足搜索標準 – ps0604

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

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

來源

2015-05-04 09:58:16 Aakash

在Java中遍歷和過濾樹

回答

相關問題