Обход бинарного дерева поиска по уровням
Обход бинарного дерева поиска по уровням, то есть обход уровень за уровнем, сохранение узлов каждого уровня в очереди, затем выполнение операций dequeue (извлечение узлов) и enqueue (сохранение узлов следующего уровня) для достижения цели обхода.
С помощью введения очереди для поддержки обхода по уровням:
-
Если корневой узел пуст, обходить нечего;
-
Если корневой узел не пуст:
-
Сначала поместить корневой узел в очередь;
-
Пока очередь не пуста:
- Извлечь из очереди первый узел и обойти его;
- Если у первого узла очереди есть левый потомок, поместить левого потомка в очередь;
- Если у первого узла очереди есть правый потомок, поместить правого потомка в очередь;
-
Далее шаги демонстрируются последовательно:
(1)Сначала взять корневой узел и поместить его в очередь

(2)Извлеките 29, поставьте в очередь левый и правый дочерние узлы

(3)Передний узел 17 извлекается из очереди, а его дочерние узлы 14 и 23 ставятся в очередь.

(4)31 извлекается из очереди, а его дочерние узлы 30 и 43 ставятся в очередь.

(5)Наконец, извлеките все из очереди

// Обход двоичного дерева поиска в порядке уровней
public void levelOrder(){
// Мы используем LinkedList в качестве очереди
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
...
Пример кода на Java
Загрузка пакета исходного кода:Скачать
src/example/binary/LevelTraverse.java код файла:
import java.util.LinkedList;
/**
* Обход по уровням
*/
public class LevelTraverse<Key extends Comparable<Key>, Value>{
// Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
}
private Node root; // Корневой узел
private int count; // Количество узлов в дереве
// Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
public LevelTraverse() {
root = null;
count = 0;
}
// Вернуть количество узлов в бинарном дереве поиска
public int size() {
return count;
}
// Вернуть, является ли бинарное дерево поиска пустым
public boolean isEmpty() {
return count == 0;
}
// Вставить новую пару данных (key, value) в бинарное дерево поиска
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Проверить, существует ли key в бинарном дереве поиска
public boolean contain⟦⟧Key(Key key){
return contain(root, key);
}
// Найти в бинарном дереве поиска значение, соответствующее key. Если значение не существует, вернуть null
public Value search(⟦⟧Key key){
return search( root , key );
}
// Прямой обход бинарного дерева поиска
public void preOrder(){
preOrder(root);
}
// Симметричный обход бинарного дерева поиска
public void inOrder(){
inOrder(root);
}
// Обратный обход бинарного дерева поиска
public void postOrder(){
postOrder(root);
}
// Обход двоичного дерева поиска в порядке уровней
public void levelOrder(){
// Мы используем LinkedList в качестве очереди
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
//********************
//* Вспомогательные функции для бинарного дерева поиска
//********************
// Вставка узла (key, value) в бинарное дерево поиска с корнем в node с использованием рекурсивного алгоритма
// Возвращает корень двоичного дерева поиска после вставки нового узла
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Проверяет, содержит ли двоичное дерево поиска с корнем в node узел со значением ключа key, используя рекурсивный алгоритм
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Найти значение, соответствующее key, в двоичном дереве поиска с корнем в node, рекурсивный алгоритм
// Вернуть NULL, если значение не существует
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Выполнить прямой обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Выполнить симметричный обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Выполнить обход в обратном порядке двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
}