обход через все узлы бинарного дерева в Java

Question

Допустим, у меня есть простой двоичный класс дерева узлов, например, так:

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

Как добавить метод, который способен рекурсивно пройти через любой размер дерево , посещая каждый существующий узел слева направо, без, пересматривая узел, который уже прошел?

Будет ли это работать ?:

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

Есть 3 типа Binary обхода дерева, которые можно достичь:

пример:

считают это следующее бинарное дерево:

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) 

пример кода:

слева направо обхода бинарного дерева, нет в порядке обхода бинарного дерева:

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 прав. Обход посетит каждый узел слева. Как только он достигает последнего узла слева, он начинает работать обратно по правосторонним узлам. Это обход поиска по глубине (DFS). Таким образом, каждый узел посещается только один раз, и алгоритм работает в O (n) времени. Счастливое кодирование.