Przejazd przez wszystkich węzłach binarnego drzewa w Javie

Question

Powiedzmy mam prosty binarny klasę węzła drzewa, tak jak poniżej:

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; 
    } 
} 

Jak bym dodać metodę, która jest w stanie rekurencyjnie przechodzić przez żadne drzewo size , odwiedzając każdy i każdy istniejący węzeł od lewej do prawej, bez ponownej rejestracji węzła, który już przeszedł?

to będzie działać ?:

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

Istnieją 3 rodzaje dwuskładnikowych przechodzenie drzewa, które można osiągnąć:

przykład:

uważają to drzewo binarne następujący:

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) 

przykład kodu

:

lewej do prawej przechodzenie binarnego drzewa, ba w kolejności Traversal drzewa binarnego:

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 ma rację. Przejście odwiedzi każdy węzeł po lewej stronie. Gdy dotrze do ostatniego węzła po lewej stronie, rozpoczyna pracę z powrotem wzdłuż węzłów po prawej stronie. Jest to przejście do pierwszego wyszukiwania (DFS). W związku z tym każdy węzeł jest odwiedzany tylko raz, a algorytm działa w czasie O (n). Szczęśliwe kodowanie.