Перемещение по всем узлам двоичного дерева в Java

Скажем, у меня есть простой класс двоичного дерева node, например:

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

Как мне добавить метод, который может рекурсивно проходить через любое дерево размеров, просматривая каждый существующий node слева направо, не пересматривая node, который уже прошел?
< бр /" > Будет ли это работать?:

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

Ответ 1

Существует три типа обхода двоичного дерева, которые вы можете достичь:

Пример:

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

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)

Пример кода

перемещение слева направо в двоичном дереве, nay В порядке прохождения двоичного дерева:

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

Ответ 2

codeMan прав. Прохождение будет посещать каждый node слева. Как только он достигнет последнего node слева, он начнет обратный путь назад по правосторонним узлам. Это обход поиска по глубине (DFS). Таким образом, каждый node посещается только один раз, а алгоритм работает в O (n) времени. Счастливое кодирование.