Exemple de partage de code sur la traversée non récursive d'arbres binaires

Qu'est-ce que le parcours non récursif d'un arbre binaire ? Le parcours non récursif des arbres binaires utilise également des idées récursives.Prenons l'exemple du parcours de précommande : recherchez d'abord le nœud dans le coin inférieur gauche, puis affichez-le, puis effectuez l'opération suivante sur le sous-arbre droit de ce nœud.

Parcours en précommande :

 public void pre_iteration(Node p) {if (p == null) return;
        Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) {
                System.out.println(p.val);
                stack.push(p);
                p = p.left;
            }if (!stack.isEmpty()) {
                p = stack.pop();
                p = p.right;
            }
        }
    }

Parcours dans l'ordre :

public void in_iteration(Node p) {if (p == null) return;
        Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) {
                stack.push(p);
                p = p.left;
            }if (!stack.isEmpty()) {
                p = stack.pop();
                System.out.println(p.val);
                p = p.right;
            }
        }
    }

Parcours après commande : (stack2 Il est utilisé pour enregistrer si le sous-arbre droit du nœud actuel a été parcouru)

public static void post_iteration(Node p) {if (p == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Boolean> stack2 = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) {
                stack.push(p);
                stack2.push(false);
                p = p.left;
            }while (!stack.isEmpty() && stack2.peek()) {
                System.out.println(stack.pop().val);
                stack2.pop();
            }if (!stack.isEmpty()) {
                p = stack.peek().right;
                stack2.pop();
                stack2.push(true);
            }
        }
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!