Level-Order-Durchquerung eines Binärbaums ohne Rekursion? ⇐ C++

[Guest]

Ich versuche, eine Durchquerung eines Binärbaums in Ebenenreihenfolge in C++ zu implementieren, ohne Rekursion zu verwenden. Das Ziel besteht darin, den Baum Ebene für Ebene zu durchlaufen, beginnend bei der Wurzel, und die Knoten in der richtigen Reihenfolge zu drucken.
Ich habe gelesen, dass dies mithilfe einer Warteschlange möglich ist, aber Ich habe Probleme mit ein paar Details:
Wie initialisiere und verwende ich eine std::queue, um die Knoten für die Durchquerung zu speichern?
Wie stelle ich die Knoten richtig in die Warteschlange? linke und rechte Kinder eines Knotens?
Wie stelle ich sicher, dass die Schleife stoppt, nachdem alle Knoten verarbeitet wurden?
Gibt es Randfälle, die ich behandeln muss, z. B. einen leeren Baum oder einen Baum mit nur einem Knoten?

Code: Select all

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Hier ist eine Grundstruktur meines Binärbaums:
Ich habe Code geschrieben, aber er scheint nicht richtig zu funktionieren, und ich Wenn ich versuche, auf untergeordnete Knoten zuzugreifen, treten immer wieder Segmentierungsfehler auf. Kann jemand den richtigen Ansatz zur Implementierung dieser Durchquerung erklären und mir helfen zu verstehen, was möglicherweise schief läuft?
Ich habe versucht, die Durchquerung der Ebenenreihenfolge mithilfe einer std::queue in C++ zu implementieren. Meine Idee war, den Wurzelknoten in die Warteschlange einzureihen, dann wiederholt den vorderen Knoten aus der Warteschlange zu nehmen, seinen Wert zu verarbeiten und seine linken und rechten untergeordneten Knoten (falls vorhanden) in die Warteschlange einzureihen.
Das habe ich versucht:< /p>

Code: Select all

#include 
#include 

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void levelOrderTraversal(TreeNode* root) {
std::queue q;
q.push(root);

while (!q.empty()) {
TreeNode* current = q.front();
q.pop();

std::cout val left != nullptr) {
q.push(current->left);
}
if (current->right != nullptr) {
q.push(current->right);
}
}
}

Ich habe erwartet, dass dieser Code die Ebenenreihenfolge des Baums ausgibt.
Ich bin jedoch auf einige Probleme gestoßen:Segmentierungsfehler: Das Programm stürzt ab, wenn der Baum leer ist oder wenn versucht wird, auf current->left oder current->right für einen Knoten zuzugreifen, der nicht existiert.
Falsche Ausgabe: In einigen Fällen In einigen Fällen ist die Durchlaufreihenfolge nicht so erwartet, und ich bin mir nicht sicher, ob meine Warteschlangenoperationen korrekt sind.
Ich bin nicht sicher, wie ich diese Probleme effektiv lösen soll. Wie sollte ich meinen Code ändern, um Randfälle wie einen leeren Baum zu behandeln oder sicherzustellen, dass die Durchlaufreihenfolge korrekt ist? Für jede Anleitung wäre ich sehr dankbar!