Une partie est que je dois mettre en œuvre une méthode non récursive d'une traversée d'inondation d'un arbre binaire. Je suis un peu coincé. Voici ce que j'ai jusqu'à présent:
A
/ \
B C
/ \ / \
D E F G
/ \
H I
/ \
J K
3 Réponses :
Suivre votre code, la boucle tandis que pour la partie Essayez ce code exemple: Stackoverflow Réponse: https://stackoverflow.com/a/12718147/1178781 < / a> getleft () passe à gauche de l'arborescence, puis sortez. v est maintenant nœud j , qui n'a pas d'enfant droit, donc la boucle suivante tandis que la boucle ne fonctionne pas.
Merci beaucoup, les commentaires m'ont aidé à comprendre comment cela fonctionne encore plus :)
Vous pouvez simplifier grandement le ci-dessus avec une boucle unique tandis que:
Stack<Node> stack = new Stack<>();
Node current = root;
while(current != null || !stack.isEmpty()){
if(current != null){
stack.push(current);
current = current.left;
} else if(!stack.isEmpty()) {
current = stack.pop();
process(current);
current = current.right;
}
}
Une autre implémentation de traversée binaire plus simple:
import java.util.Stack;
public class BinaryTree {
public static void main(String args[])
{
Node root = Node.createDummyTree();
Node tnode; //= root;
Stack<Node> stack = new Stack<Node>();
if (root != null)
{
stack.push(root);
}
while (!stack.isEmpty())
{
tnode = stack.pop();
if (tnode != null)
{
System.out.println(tnode.value);
if(tnode.rightNode != null)
{
stack.push(tnode.rightNode);
}
if (tnode.leftNode != null)
{
stack.push(tnode.leftNode);
}
}
}
}
}
class Node {
public Node leftNode;
public Node rightNode;
public String value;
Node(String value)
{
this.value = value;
}
/**
* Construct a dummy binary Tree
* A
* / \
* B C
* / \ / \
* D E F G
* / \ / \ / \ / \
* H I J K L M N O
* @return
*/
public static Node createDummyTree(){
Node root = new Node("A");
root.leftNode = new Node("B");
root.rightNode = new Node("C");
Node tnode = root.leftNode;
tnode.leftNode = new Node("D");
tnode.rightNode = new Node("E");
Node tempNode = tnode.rightNode; //remember "E"
tnode = tnode.leftNode;
tnode.leftNode = new Node ("H");
tnode.rightNode = new Node ("I");
tnode = tempNode;
tnode.leftNode = new Node ("J");
tnode.rightNode = new Node ("K");
tnode = root.rightNode;
tnode.leftNode = new Node("F");
tnode.rightNode = new Node("G");
tempNode = tnode.rightNode; // rememebr "G"
tnode = tnode.leftNode;
tnode.leftNode = new Node("L");
tnode.rightNode = new Node("M");
tnode = tempNode;
tnode.leftNode = new Node("N");
tnode.rightNode = new Node("O");
return root;
}
}
Il s'agit d'une traversée de pré-commande mais OP fait référence à une traversée en ordre.