Jak uzyskać wszystkie węzły liści drzewa?

Question

Załóżmy, że mam węzeł w drzewie, w jaki sposób mogę uzyskać wszystkie węzły liści, których przodkiem jest ten węzeł? Zdefiniowałem TreeNode w następujący sposób:

public class TreeNode<T> 
{ 
    /** all children of the node */ 
    private List<TreeNode<T>> children = new ArrayList<TreeNode<T>>(); 
    /** the parent of the node, if the node is root, parent = null */ 
    private TreeNode<T> parent = null; 
    /** the stored data of the node */ 
    private T data = null; 

    /** the method I want to implement */ 
    public Set<TreeNode<T>> getAllLeafNodes() 
    { 
     Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>(); 
     return leafNodes; 
    } 
} 

Answer 1

Użyj rekursji.

• jeśli sam węzeł jest liściem, zwrócić go
• inaczej, powrót wszystkich liści węzłów swoich dzieci

Coś takiego (nie testowane):

public Set<TreeNode<T>> getAllLeafNodes() { 
    Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>(); 
    if (this.children.isEmpty()) { 
     leafNodes.add(this); 
    } else { 
     for (TreeNode<T> child : this.children) { 
      leafNodes.addAll(child.getAllLeafNodes()); 
     } 
    } 
    return leafNodes; 
}