Parcourez l'arbre de recherche binaire pour trouver toutes les feuilles

Je suis assez nouveau dans les arbres, et je suis en train de créer une sorte de "feuille de itérateur". Je pense qu'il devrait mettre tous les nœuds qui n'ont pas de .left et .right valeur sur une pile, mais je ne suis pas sûr de savoir comment ou même si c'est la bonne chose à faire. J'ai essayé de chercher, mais tous les exemples que je viens sur commence par aller à l'extrême gauche de la feuille, et va p = node.parentet je suis d'éviter reliant le nœud parent.

Je ne comprends pas comment je peux repeatedlty commencer à partir de la racine et de passer à travers les vignes sans la visite de la même vigne.

MODIFIER

Je vois des gens suggère d'utiliser une méthode itérative pour résoudre ce problème, et je suis d'accord maintenant. Mais j'ai été frapper ma tête en essayant de trouver la solution pour un itérateur-classe-façon de le faire pendant un certain temps, et j'aimerais savoir si c'est possible, et comment!

source d'informationauteur Sti

  1. 14

    Utiliser la récursivité:

    public void visitNode(Node node) {
    if(node.left != null) {
        visitNode(node.left);
    }
    if(node.right != null) {
        visitNode(node.right);
    }
    if(node.left == null && node.right == null) {
        //OMG! leaf!
    }
}

    commencer par la fourniture de root:

    visitNode(root);

    Afin de traduire cela en un Iterator<Node> vous aurez à traduire la récursivité de la boucle, puis à la traversée de l'etat. Non-trivial, mais devrait vous donner beaucoup de plaisir.

  2. 3
    class Node {
    public Node left = null;
    public Node right = null;
    //data and other goodies
}
class Tree {
    public Node root = null;
    //add and remove methods, etc.
    public void visitAllLeaves(Node root) {
        //visit all leaves starting at the root
        java.util.Stack<Node> stack = new java.util.Stack<Node>();
        if (root == null) return; //check to make sure we're given a good node
        stack.push(root);
        while (!stack.empty()) {
            root = stack.pop();
            if (root.left == null && root.right == null) {
                //this is a leaf
                //do stuff here
            }
            if (root.left != null) {
                stack.push(root.left);
            }
            if (root.right != null) {
                stack.push(root.right);
            }
        }
    }
}

    Je ne sais pas si le code ci-dessus fonctionne, mais qui est quelque part le long des lignes de ce qui doit être fait. Une autre option est javax.swing.TreeModel (demi-blague).

  3. 0

    Ici est de savoir comment on pourrait mettre en œuvre un Itérateur qui ne renvoie des nœuds feuilles, c'est à dire les nœuds sans gauche ou à droite de la sous-arborescence.

    L'itérateur recherches pour les nœuds feuilles de l'arbre en faisant une recherche depth-first, se souvenant de l'état actuel de la recherche dans une pile et "pause" quand il a trouvé un nœud feuille (voir fetchNext() la méthode).

    La recherche est reprise lorsque le client "consomme" de la feuille de nœud par l'appel à next(). 

    class Node {
public Node left;
public Node right;
}
class LeaveIterator implements Iterator<Node> {
private final Stack<Node> stack = new Stack<>();
private Node nextNode = null;
public LeaveIterator(Node root) {
if (root != null) {
stack.push(root);
nextNode = fetchNext();
}
}
private void fetchNext() {
Node next = null;
while (!stack.isEmpty() && next == null) {
Node node = stack.pop();
if (node.left == null && node.right == null) {
next = node;
}
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return next;
}
public boolean hasNext() {
return nextNode != null;
}
public Node next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Node n = nextNode;
nextNode = fetchNext();
return n;
}
public void remove() {
throw new UnsupportedOperationException();
}
}