Двоичные деревья

1. Двоичные деревья

Покатилов Антон

2. План презентации

• 1. Что такое узел?
• 2.Рекурсивный алгоритм двоичного дерева.
• 3.Итеративный алгоритм двоичного дерева.

3. Узел

Узел – динамическая переменная типа record,
содержащая поле для запоминания
информации и поля для двух указателей
адреса.

4. Деревья связанные с корнем, называется левым и правым поддеревом.

5. Считается, что корневой узел находится на нулевом уровне, а уровень узла, связанного с узлом i-уровня, равен (i+1).Узлы (i+1)-го уровня называются

потомками.

6.

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

7.

• Итеративный алгоритм создаёт узлы в
порядке их появления на уровнях:
• - создаётся корневой узел;
• -корневой узел заносится в очередь;
• -для каждого узла, удалённого из
очереди , создаётся левый или правый
потомок, если таковые существуют;
• -вновь созданные узлы заносятся в
очередь;
• -процесс создания А,В,С,D,E,F,G,H,I,J.

8.

• С помощью рекурсивного алгоритма
двоичные деревья создаются в
соответствии со следующими
правилами:
• -создаётся корневой узел;
• -строится левое поддерево;
• -строится правое поддерево.