На следующем рисунке показаны уровни в дереве
порядок обхода дерева 1, 2, 3, 4, 5
Нам дан корневой узел, и мы должны напечатать обход его уровня. Если мы внимательно изучим шаги, которые сначала нам нужно сделать, это напечатать корневой узел (т.е. 1 в примере), а затем мы должны отслеживать его дочерние узлы. Теперь нам нужно вывести 2 и 3 и отслеживать их дочерние узлы. Понятно, что мы не можем просто использовать временный узел для отслеживания значений на каждой итерации. И нам также нужно отслеживать порядок: 2, затем 3, затем 4 и так далее.
Поэтому мы собираемся использовать здесь структуру данных очереди. После печати узла мы поставим его дочерние элементы в очередь. Мы будем повторять ту же процедуру, пока очередь не станет пустой. Давайте посмотрим на это более четко с кодом и иллюстрацией.
Код:
void levelOrder (корень узла) {
Queue‹Node› queue=new LinkedList‹›();
очередь.добавить(корень);
пока(!queue.isEmpty()){
Узел tempnode = queue.remove();
System.out.print(tempnode.data+" ");
если(tempnode.left!=null)
очередь.добавить(tempnode.left);
если(tempnode.right!=null)
очередь.добавить(tempnode.right);
}
}
Иллюстрация:
очередь.добавить(корень)
Удалите из очереди первый элемент в очереди, распечатайте его и поставьте в очередь его левый и правый дочерние элементы.
Удалите из очереди 2 , распечатайте его и поставьте в очередь его левый и правый дочерние элементы. Здесь ничего не вставлено, так как левый и правый дочерние узлы пусты на 2
Удалите из очереди 3, напечатайте и вставьте его левый и правый дочерние элементы, т.е. 4 и 5.
Удалить из очереди 4, распечатать
Удалить из очереди 5, распечатать
