Attraversando attraverso tutti i nodi di un albero binario in Java

Question

Diciamo che ho una semplice classe nodo di albero binario, in questo modo:

public class BinaryTreeNode { 
    public String identifier = ""; 
    public BinaryTreeNode parent = null; 
    public BinaryTreeNode left = null; 
    public BinaryTreeNode right = null; 

    public BinaryTreeNode(BinaryTreeNode parent, String identifier) 
    { 
     this.parent = parent; //passing null makes this the root node 
     this.identifier = identifier; 
    } 

    public boolean IsRoot() { 
     return parent == null; 
    } 
} 

Come vorrei aggiungere un metodo che è in grado di attraversare ricorsivamente attraverso qualsiasi albero di dimensioni , visitando ogni nodo esistente da sinistra a destra, senza rivisitando un nodo che è già stato attraversato?

Sarebbe questo lavoro ?:

public void traverseFrom(BinaryTreeNode rootNode) 
{ 
    /* insert code dealing with this node here */ 

    if(rootNode.left != null) 
     rootNode.left.traverseFrom(rootNode.left); 

    if(rootNode.right != null) 
     rootNode.traverseFrom(rootNode.right); 
} 

Answer 1

Ci sono 3 tipi di albero binario di attraversamento che si possono ottenere:

esempio:

prendere in considerazione questa seguente albero binario:

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) 
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right) 
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) 

codice di esempio:

sinistra a destra attraversamento del albero binario, anzi Per Traversal di albero binario:

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

Answer 2

codeMan è giusto. L'attraversamento visiterà ogni nodo a sinistra. Una volta che raggiunge l'ultimo nodo a sinistra, inizia a risalire lungo i nodi di destra. Questa è una traversata di ricerca in profondità (DFS). In quanto tale, ogni nodo viene visitato solo una volta e l'algoritmo viene eseguito in tempo O (n). Buona programmazione.