Similar presentations:
Двоичные деревья
1. Двоичные деревья
Покатилов Антон2. План презентации
• 1. Что такое узел?• 2.Рекурсивный алгоритм двоичного дерева.
• 3.Итеративный алгоритм двоичного дерева.
3. Узел
Узел – динамическая переменная типа record,содержащая поле для запоминания
информации и поля для двух указателей
адреса.
4. Деревья связанные с корнем, называется левым и правым поддеревом.
5. Считается, что корневой узел находится на нулевом уровне, а уровень узла, связанного с узлом i-уровня, равен (i+1).Узлы (i+1)-го уровня называются
потомками.6.
• Дерево – это структура данных, состоящаяиз узлов и соединяющих их направленных
ребер (дуг), причем в каждый узел (кроме
корневого) ведет ровно одна дуга.
• Корень – это начальный узел дерева.
• Лист – это узел, из которого не выходит ни
одной дуги.
7.
• Итеративный алгоритм создаёт узлы впорядке их появления на уровнях:
• - создаётся корневой узел;
• -корневой узел заносится в очередь;
• -для каждого узла, удалённого из
очереди , создаётся левый или правый
потомок, если таковые существуют;
• -вновь созданные узлы заносятся в
очередь;
• -процесс создания А,В,С,D,E,F,G,H,I,J.
8.
• С помощью рекурсивного алгоритмадвоичные деревья создаются в
соответствии со следующими
правилами:
• -создаётся корневой узел;
• -строится левое поддерево;
• -строится правое поддерево.