Бинарные деревья

Данные:

Адрес корня дерева.

Допустимые операции:

Создать дерево из 1 листа (элемент, без поддеревьев);

Добавить лист/вершину/корень дерева (часто в соответствии с определенным на дереве порядком);

Удалить лист/вершину/фрагмент дерева;

Проверка на отсутствие элементов;

Очистить дерево (удалить все элементы);

Узнать значение информационной части текущего узла дерева.

Для работы с элементами дерева используется обход дерева в глубину, в ширину, симметричный... Например, дерево с последнего в этом файле рисунка можно обойти следующими путями:

10, 5, 1, 7, 6, 9, 10, 13 (начиная с корня в глубину слева направо)

10, 5, 10, 1, 7, 13, 6, 9 (начиная с корня по ярусам)

1, 6, 9, 7, 5, 13, 10, 10 (с самого левого листа, узлы после листьев)

1, 5, 6, 7, 9, 10, 10, 13 (с самого левого листа проходя через узлы)

и т.д.

Дерево может быть построено, начиная с любого листа, в зависимости от нужд задачи. Например, при синтаксическом разборе выражения строится дерево, показанное ниже.

На последнем рисунке приведен пример построения дерево с упорядоченными по возрастанию листьями. Любой лист, лежащий на дереве левее (и ниже) выбранного, меньше выбранного. А лист, лежащий выше и правее, больше или равен выбранному.

Синтаксический разбор выражения

Упорядоченные по возрастанию узлы и листья