Лабораторная работа № 10. Алгоритмы обработки бинарных деревьев

Теоретическая часть

Бинарное дерево

Дерево - это совокупность элементов (узлов) и отношений, образующих иерархическую структуру узлов.

Один из узлов дерева называется корнем - узел без родительских узлов. Если узел не имеет дочерних узлов, он называется листом. Дерево называется бинарным, если каждый узел содержит не больше двух дочерних узлов.

Элементы дерева

Алгоритмы обхода бинарного дерева

Рассмотрим порядок обхода узлов дерева на следующем примере:

Рисунок 1

Симметричный обход. Левое поддерево -> корень -> правое поддерево: D, B, E, A, C.

СоветВизуализация (нажмите, чтобы открыть)

Чтобы визуализировать симметричный обход дерева, изобразим под ним прямую и спроецируем на неё узлы. Обход будет совершаться в порядке появления проекций узлов слева направо.

Симметричный обход

Обратный обход. Левое поддерево -> правое поддерево -> корень: D, E, B, C, A.

СоветВизуализация (нажмите, чтобы открыть)

Чтобы визуализировать обратный обход дерева, можно представить, что вы по-очереди слева направо срываете узлы, которые не имеют потомков (листья).

Обратный обход

Абстрактный тип данных Node

Класс Node предназначен для описания узла дерева. Чтобы создавать объекты класса Node необходимо импортировать класс из файла ds.py:

# импорт класса Node из файла ds.py
from ds import Node

В Таблице 1 перечислены методы и свойства класса Node.

Таблица 1: Методы класса Node

Метод/свойство	Назначение	Пример
Node(value)	Конструктор. Создаёт новый узел со значением value	n1 = Node('1') n2 = Node('3')
Node(value, left, right)	Конструктор. Создаёт новый узел со значением value, левым (left) и правым (right) дочерними узлами.	n3 = Node('+', n1, n2)
is_leaf()	Проверяет, является ли узел листом. Возвращает логическое значение.	t = n1.is_leaf()
value	Свойство для получения и изменения значения, хранимого в узле.	b = n1.value n1.value = '2'
left	Свойство для получения и изменения ссылки на левый дочерний элемент узла.	l = n1.left n1.left = n2
right	Свойство для получения и изменения ссылки на левый дочерний элемент узла.	r = n1.right n1.right = n2

Опишем граф изображённый на Рисунке 1:

# импорт класса Node
from ds import Node

d = Node('D') # создание узла со значением 'D'
e = Node('E')
b = Node('B', d, e)

c = Node('C')
a = Node('A')
a.left = b
a.right = c

print(d.is_leaf()) # является ли узел d листом

Выполнение кода проиллюстрировано на следующем изображении (щелчок, чтобы увеличить):

Иллюстрация работы кода

Задания для самостоятельной работы

УведомлениеВнимание

Задания обозначенные значком 📝 выполняются на распечатках или в тетради, обозначенные 💻 - на компьютере в среде программирования.

📝 Задание 1. Обход узлов бинарного дерева

Запишите название узла, являющегося корнем дерева и список узлов-листьев. Перечислите порядок обхода узлов бинарного дерева из вашего варианта при симметричном и обратном порядке обхода.

Вариант 1

2

3

4

5

6

7

8

9

10

11

12

13

14

💻 Задание 2. Использование типа данных Node

Используйте интерфейс типа данных Node чтобы описать дерево из Задания 1.

Шаблон программы:

from ds import Node

# описание бинарного дерева

💻 Задание 3. Реализация симметричного обхода дерева (sam03.py)

Реализуйте функцию inorder(node) для симметричного обхода бинарного дерева начиная с узла node.

1

2

3

Рисунок 2

Шаблон программы:

from ds import Node

# опишите функцию inorder() после комментария


# дерево для проверки работы функции
d = Node('D')
e = Node('E')
b = Node('B', d, e)

c = Node('C')
a = Node('A', b, c)

inorder(a) # Вызов функции обхода дерева. Ответ: DBEAC

💻 Задание 4. Реализация обратного обхода дерева (sam04.py)

Реализуйте функцию postorder(node) для обратного обхода бинарного дерева начиная с узла node.

Рисунок 3

Шаблон программы:

from ds import Node

# опишите функцию postorder() после комментария


# дерево для проверки работы функции
d = Node('D')
e = Node('E')
b = Node('B', d, e)

c = Node('C')
a = Node('A', b, c)

postorder(a) # Вызов функции обхода дерева. Ответ: DEBCA

💻 Задание 5. Вычисление значения выражения (sam05.py)

Реализуем рекурсивную функцию для вычисления выражения, представленного с помощью бинарного дерева. Выражение может содержать сложение и вычитание.

1

2

Рисунок 4

Используйте следующий шаблон кода:

from ds import Node

# объявление функции t_eval(node)


# тестирование работы функции
# создание бинарного дерева для выражения 7 - 0.4 + 2.7
root = Node('+')
op1 = Node('-')
op1.left = Node(7)
op1.right = Node(0.4)
root.left = op1
root.right = Node(2.7)

res = t_eval(root) # вызов функции t_eval()
print(res) # -> 9.3

💻 Задание 6. Калькулятор

Модифицируйте код функции t_eval(node) из предыдущего задания и добавьте обработку оператора умножения и деления.

С помощью модифицированной функции посчитайте значение выражения для вашего варианта.

Вариант 1

\[ 4 * 2 + (11 - 3) \]

2

\[ (6+7) / (9-12) \]

3

\[ 3 / (6 - 11 * 2) \]

4

\[ (8 + 4) * 3 / 2 \]

5

\[ (21 - 4) * 2 / 4 \]

6

\[ 3 * (6 - 2) + 9 \]

7

\[ 15 / (10 + 3 - 8) \]

8

\[ 4 * 2 + (11 - 3) \]

9

\[ (6+7) / (9-12) \]

10

\[ 3 / (6 - 11 * 2) \]

11

\[ (8 + 4) * 3 / 2 \]

12

\[ (21 - 4) * 2 / 4 \]

13

\[ 3 * (6 - 2) + 9 \]

14

\[ 15 / (10 + 3 - 8) \]

💻 Задание 7. Обход дерева в ширину (sam07.py)

Ещё один метод обхода дерева - обход в ширину. При таком подходе вершины выводятся исходя из их глубины.

Обход в ширину

Для примера выше получим следующий порядок обхода узлов: A, B, C, D, E.

Реализуйте функцию btt(node) для обхода дерева в ширину, с корнем в узле node.

Используйте следующий шаблон кода:

from ds import Node, Queue

# после комментария опишите функцию


# дерево для проверки работы функции
d = Node('D')
e = Node('E')
b = Node('B', d, e)

c = Node('C')
a = Node('A', b, c)

# вызовы функции
btt(a) #-> ABCDE
btt(b) #-> BDE

---

Для реализации алгоритма необходимо использовать очередь - класс Queue.

---

В очередь добавляется узел root. Пока очередь не пуста выполняем следующие действия: извлекаем элемент из очереди и выводим его значение; если у извлечённого узла есть левый потомок, то добавляем его в очередь; если у извлечённого узла есть правый потомок, то добавляем его в очередь.

💻 Задание 8. Поиск узла (sam08.py)

Напишите функцию bt_search(root, value), которая ищет значение value в бинарном дереве с корнем root. Функция должна вернуть True если искомое значение есть в бинарном дереве и False если значение отсутствует.

Используйте следующий шаблон:

from ds import Node

# после комментария опишите функцию


# дерево для проверки работы функции
d = Node('D')
e = Node('E')
b = Node('B', d, e)

c = Node('C')
a = Node('A', b, c)

# вызовы функции
print(bt_search(a, 'D')) #-> True
print(bt_search(a, 'X')) #-> False
print(bt_search(a, 'B')) #-> True

---

Для решения можно использовать рекурсию.

---

Первый базовый случай рекурсии - если значение в узле node совпадает с тем, что нужно найти (value), функция возвращает истину.

---

Второй базовый случай рекурсии - если узел node является листом и значение в нём не совпадает с тем, что нужно найти, функция возвращает ложь.

---

Если ни один из базовых случаев не сработал - рекурсивно вызываем функцию для левого и правого потомков текущего узла node. Возвращаем результаты вызова функций разделённые логическим ИЛИ.