Обход двоичного дерева по уровням без рекурсии? ⇐ C++

[Anonymous]

Я пытаюсь реализовать обход двоичного дерева на C++ без использования рекурсии. Цель состоит в том, чтобы пройти уровень за уровнем дерева, начиная с корня, и распечатать узлы в правильном порядке.
Я читал, что это можно сделать с помощью очереди, но Я затрудняюсь с некоторыми деталями:
Как мне инициализировать и использовать std::queue для хранения узлов для обхода?
Как правильно поставить в очередь левый и правый дочерние элементы узла?
Как мне гарантировать, что цикл остановится после обработки всех узлов?
Есть ли какие-либо крайние случаи, которые мне нужно обработать, например пустое дерево или дерево только с одним узлом?

Код: Выделить всё

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

Вот базовая структура моего двоичного дерева:
Я написал некоторый код, но, похоже, он работает неправильно, и я продолжаю сталкиваться с ошибками сегментации, когда пытаюсь получить доступ к дочерним узлам. Может ли кто-нибудь объяснить правильный подход к реализации этого обхода и помочь мне понять, что может пойти не так?
Я попробовал реализовать обход по уровням с помощью std::queue в C++. Моя идея заключалась в том, чтобы поставить в очередь корневой узел, затем несколько раз исключить из очереди передний узел, обработать его значение и поставить в очередь его левого и правого дочерних узлов (если они существуют).
Вот что я попробовал:< /p>

Код: Выделить всё

#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);
}
}
}

Я ожидал, что этот код напечатает обход дерева по уровням.
Однако я столкнулся с некоторыми проблемами:Ошибка сегментации: программа аварийно завершает работу, когда дерево пусто или при попытке доступа к текущему->левому или текущему->правому узлу, который не существует.
Неправильный вывод: в некоторых случаях порядок обхода не такой, как ожидаемо, и я не уверен, что мои операции с очередью корректны.
Я не уверен, как эффективно справиться с этими проблемами. Как мне изменить свой код для обработки краевых случаев, таких как пустое дерево, или обеспечить правильный порядок обхода? Будем очень признательны за любые рекомендации!

Подробнее здесь: https://stackoverflow.com/questions/793 ... -recursion