Представление бинарных деревьев

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отношение старше-младше (левее-правее). Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

Пример

На рис. 9.11 приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев.

Таким образом, достаточно рассмотреть представление в компьютере бинарных деревьев.

Замечание

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

1. Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (t и r) с указателями на левый и правый узлы и еще одно поле r для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип N обычно определяется следующим образом:

Обозначим через n(p) объем памяти, занимаемой представлением бинарного дерева, где - число узлов. Наиболее часто используются следующие представления бинарных деревьев.

N = record i: info; l,r: ↑ N end record

Для этого представления n(p) = 3p

Контрольные вопросы

1. Что называется графом? Ориентированным графом? Примеры.

2. Что такое степень вершины?

3. Перечислите основные понятия, связанные с неориентированными графами.

4. Перечислите основные понятия, связанные с ориентированными графами.

5. Перечислите способы задания графов.

6. В чем состоит аналитический способ задания графа?

7. В чем состоит геометрический способ задания графа?

8. В чем состоит матричный способ задания графа?

9. Какая матрица называется матрицей смежности графа?

10. Какая матрица называется матрицей смежности графа?

11. Какая матрица называется матрицей инцидентности графа?

12. Что называется маршрутом, циклом и цепью графа?

13. Сформулируйте понятие связности графа. Какой граф называется связным?

14. Какие два графа называются изоморфными?

15. Сформулируйте алгоритм изоморфизма двух графов.

16. Перечислите операции над графами.

17. Дайте определение эйлерова графа.

18. Сформулируйте алгоритм построения эйлерова цикла.

19. Какой граф называется гамильтоновым?

Лекция № 9