Heim > Java > javaLernprogramm > Beispielcode-Sharing zum nicht rekursiven Durchlaufen von Binärbäumen

Beispielcode-Sharing zum nicht rekursiven Durchlaufen von Binärbäumen

零下一度
Freigeben: 2017-07-18 17:56:53
Original
1710 Leute haben es durchsucht

Was ist die nichtrekursive Durchquerung eines Binärbaums? Beim nicht rekursiven Durchlaufen von Binärbäumen werden auch rekursive Ideen verwendet: Suchen Sie zuerst den Knoten in der unteren linken Ecke, geben Sie ihn dann aus und führen Sie dann die nächste Operation am rechten Teilbaum dieses Knotens aus.

Durchquerung vor der Bestellung:

 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;
            }
        }
    }
Nach dem Login kopieren

Durchquerung in der Reihenfolge:

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;
            }
        }
    }
Nach dem Login kopieren

Durchquerung nach der Bestellung : (stack2 Wird verwendet, um aufzuzeichnen, ob der rechte Teilbaum des aktuellen Knotens durchlaufen wurde)

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);
            }
        }
    }
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonBeispielcode-Sharing zum nicht rekursiven Durchlaufen von Binärbäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage