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

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

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

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

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

java traversal binary-tree tree-traversal
person RectangleEquals    schedule 09.03.2013    source источник
comment
это очень похоже на правильный ответ ниже.   -  person Peter Wooster    schedule 09.03.2013
comment
@PeterWooster - верно, за исключением того, что я вызываю метод обхода из каждого узла, в результате чего рекурсия происходит рекурсивно для каждого узла, а не только из корня   -  person RectangleEquals    schedule 09.03.2013

Ответы (2)


arrow_upward
36
arrow_downward

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

пример:

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

введите здесь описание изображения

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);
    }
}
person codeMan    schedule 09.03.2013
comment
+1, Рекурсия всегда подходит для деревьев. Интересный ответ - сделать это без рекурсии. - person Peter Wooster; 09.03.2013
comment
@Peter Wooster Итеративное решение немного сложнее понять, особенно новичкам, поэтому я подумал, зачем усложнять. - person codeMan; 09.03.2013
comment
Согласен, я писал что-то подобное на ассемблере несколько лет назад, там конечно использовался стек. - person Peter Wooster; 09.03.2013
comment
Я знал, что был близок, но также и то, что что-то было немного не так. Спасибо, что наполнили меня, и +1 за образование - person RectangleEquals; 09.03.2013
comment
@ Питер Вустер, ты сделал это на ассемблере ?? УВАЖАТЬ!! - person codeMan; 09.03.2013

arrow_upward
8
arrow_downward

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

person RouteMapper    schedule 09.03.2013