Лекция №7 Создание и обход бинарного дерева

Пример. Использование бинарного дерева для сортировки данных

Допустим дана последовательность чисел, например:

• 15 10 20 12 8 17 25 5 9

Вывести числа в порядке возрастания:

• 5 8 9 10 12 15 17 20 25

Построим бинарное дерево: первое число будет корнем дерева. Если второе число < 1-го, то оно станет корнем левого поддерева, а если > 1-го, то станет корнем правого поддерева. Каждое следующее число будет добавляться либо в левое поддерево, либо в правое.

Алгоритм:

1. Создание бинарного дерева в виде регулярной сети.

2. Обход дерева слева направо и вывод меток его вершин (чисел).

3. Удаление дерева (освобождение памяти).