Операции с двоичным деревом поиска: обход дерева

Как только двоичное дерево поиска создано, его элементы могут быть извлечены по порядку путем рекурсивного обхода левого поддерева корневого узла, доступа к самому узлу, а затем рекурсивного обхода правого поддерева узла, продолжая этот шаблон для каждого узла в дерево как рекурсивное обращение. Как и во всех двоичных деревьях, можно выполнить обход до или после обхода, но ни один из них, вероятно, не будет полезен для деревьев двоичного поиска. Упорядоченный обход двоичного дерева поиска всегда приводит к отсортированному списку элементов узлов (чисел, строк или других сопоставимых элементов).

Код для обхода по порядку в Python приведен ниже. Он будет вызывать обратный вызов (некоторая функция, которую программист желает вызвать по значению узла, например, вывод на экран) для каждого узла в дереве.

def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)

Обход требует времени O(n), так как он должен посещать каждый узел. Этот алгоритм также O(n), поэтому он асимптотически оптимален.

Обход также может быть реализован итеративно. Для определенных применений, например большой равный поиск, приближенный поиск, операция для одношагового (итеративного) обхода могут быть очень полезны. Это, конечно, реализуется без конструкции обратного вызова и принимает в среднем O(1) и O(log n) в худшем случае.

---

Читайте также:

• Структуры данных: двоичное дерево поиска
• Операции с двоичным деревом поиска: поиск
• Операции с двоичным деревом поиска: вставка
• Операции с двоичным деревом поиска: удаление