Traverser tous les nœuds d'un arbre binaire en Java

Disons que j'ai un binaire simple nœud de l'arborescence de la classe, comme suit:

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

Comment pourrais-je ajouter une méthode qui est capable de parcourir récursivement par le biais de n'importe quelle taille de l'arbre, la visite de chaque nœud existant de gauche à droite, sans revisiter un nœud qui a déjà été parcouru?

Serait-il?:

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

source d'informationauteur RectangleEquals

  1. 31

    Il existe 3 types de Binary tree traversal que vous pouvez réaliser :

    exemple:

    considérer cet arbre Binaire :

    Traverser tous les nœuds d'un arbre binaire en Java

    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)

    exemple de code:

    de gauche à droite de la traversée de l'arbre Binaire, non Dans l'ordre de la Traversée de l'arbre binaire :

    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. 8

    codeMan est droit. Le parcours permettra de visiter tous les nœuds sur la gauche. Une fois qu'il atteint le dernier nœud sur la gauche, il commence à travailler son chemin de retour le long de la côté droit les nœuds. C'est un depth-first search (DFS) de la traversée. En tant que tel, chaque nœud est visité qu'une seule fois, et l'algorithme s'exécute en temps O(n) fois. Heureux de codage.