Scorri l'albero di ricerca binario per trovare tutte le foglie

Question

Sono abbastanza nuovo per gli alberi e sto cercando di creare una specie di "foglia iteratore". Sto pensando che dovrebbe mettere tutti i nodi che non hanno un valore .left e .right in pila, ma non sono sicuro di come o anche se sia la cosa giusta da fare. Ho provato a cercarlo, ma ogni esempio che ho incontrato inizia con l'andare alla foglia più a sinistra, e andando a p = node.parent, e sto evitando il collegamento al genitore del nodo.

Non capisco come posso ripetere ripetutamente partire dalla radice e passare attraverso le viti senza visitare più volte le stesse viti.

EDIT

vedo la gente che suggerisce di usare un metodo ricorsivo per risolvere questo, e sono d'accordo ora. Ma ho sbattuto la testa cercando di trovare la soluzione per un iteratore di classe per farlo per un po ', e mi piacerebbe ancora sapere se è possibile, e come!

Answer 1

Uso ricorsione:

public void visitNode(Node node) { 
    if(node.left != null) { 
     visitNode(node.left); 
    } 
    if(node.right != null) { 
     visitNode(node.right); 
    } 
    if(node.left == null && node.right == null) { 
     //OMG! leaf! 
    } 
} 

avviarlo fornendo root:

visitNode(root); 

Al fine di tradurre questo in un Iterator<Node> dovrete tradurre ricorsione per ciclo e poi per l'attraversamento con lo stato . Non banale, ma dovrebbe darti un sacco di divertimento.

Answer 2

class Node { 
    public Node left = null; 
    public Node right = null; 
    // data and other goodies 
} 
class Tree { 
    public Node root = null; 
    // add and remove methods, etc. 
    public void visitAllLeaves(Node root) { 
     // visit all leaves starting at the root 
     java.util.Stack<Node> stack = new java.util.Stack<Node>(); 
     if (root == null) return; // check to make sure we're given a good node 
     stack.push(root); 
     while (!stack.empty()) { 
      root = stack.pop(); 
      if (root.left == null && root.right == null) { 
       // this is a leaf 
       // do stuff here 
      } 
      if (root.left != null) { 
       stack.push(root.left); 
      } 
      if (root.right != null) { 
       stack.push(root.right); 
      } 
     } 
    } 
} 

non sono sicuro se il codice precedente funziona, ma questo è da qualche parte lungo le linee di ciò che deve essere fatto. Un'altra opzione è javax.swing.TreeModel (half-joking).

Answer 3

Ecco come si potrebbe implementare un Iterator che restituirebbe solo i nodi foglia, ovvero nodi senza una sottostruttura sinistra o destra.

L'iteratore cerca i nodi foglia nell'albero eseguendo una ricerca in profondità, ricordando lo stato corrente della ricerca in uno stack e "fermandosi" quando ha trovato un nodo foglia (vedere metodo fetchNext()).

La ricerca viene ripristinata quando il client "consuma" il nodo foglia chiamando next().

class Node { 
    public Node left; 
    public Node right; 
} 

class LeaveIterator implements Iterator<Node> { 
    private final Stack<Node> stack = new Stack<>(); 
    private Node nextNode = null; 

    public LeaveIterator(Node root) { 
    if (root != null) { 
     stack.push(root); 
     nextNode = fetchNext(); 
    } 
    } 

    private void fetchNext() { 
    Node next = null; 
    while (!stack.isEmpty() && next == null) { 
     Node node = stack.pop(); 
     if (node.left == null && node.right == null) { 
     next = node; 
     } 
     if (node.right != null) { 
     stack.push(node.right); 
     } 
     if (node.left != null) { 
     stack.push(node.left); 
     } 
    } 
    return next; 
    } 

    public boolean hasNext() { 
    return nextNode != null; 
    } 

    public Node next() { 
    if (!hasNext()) { 
     throw new NoSuchElementException(); 
    } 
    Node n = nextNode; 
    nextNode = fetchNext(); 
    return n; 
    } 

    public void remove() { 
    throw new UnsupportedOperationException(); 
    } 
}