Verfahrgeschwindigkeit durch alle Knoten eines binären Baumes in Java

Question

Lassen Sie sich sagen, dass ich eine einfache binäre Baum Knotenklasse habe, etwa so:

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

Wie würde ich eine Methode hinzufügen, die in der Lage ist rekursiv durch jede Größe Baum durchquert , jeden vorhandenen Knoten von links nach rechts zu besuchen, ohne einen bereits durchlaufenen Knoten erneut zu besuchen?

Würde diese Arbeit ?:

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

Es gibt 3 Arten von Binary Tree Traversal, die Sie erreichen können:

Beispiel:

betrachten dies folgende Binärbaum:

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) 

Codebeispiel:

nach rechts Durchlauf des binären Baum links, ja Um Traversal von binären Baum:

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 ist richtig. Das Traversal wird jeden Knoten auf der linken Seite besuchen. Sobald es den letzten Knoten auf der linken Seite erreicht, beginnt es sich entlang der rechten Knoten zurück zu arbeiten. Dies ist eine Tiefensuche (DFS). Daher wird jeder Knoten nur einmal besucht, und der Algorithmus läuft in O (n) -Zeit. Glückliche Kodierung.