Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
14 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
340.00 kB
Просмотров:
68
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Программирование Деревья](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img0.jpg)
Содержание слайда: Программирование
Деревья
№2 слайд![](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img1.jpg)
№3 слайд![Деревья -- структуры данных,](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img2.jpg)
Содержание слайда: Деревья --
структуры данных, определяемые с помощью рекурсии.
Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом T — это:
либо пустая структура;
либо узел типа T, с которым связано конечное число древовидных структур, называемых поддеревьями (subtree).
Если с узлом связаны только два поддерева, то дерево называется бинарным.
№4 слайд![](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img3.jpg)
№5 слайд![Терминология Из ботаники](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img4.jpg)
Содержание слайда: Терминология (1)
Из ботаники взяты такие определения:
узел (node) — это точка, где может возникнуть ветвь.
корень (root) — "верхний" узел дерева.;
ветвь (brunch) — отрезок, описывающий связь между двумя узлами;
лист (leaf) — узел, из которого не выходят ветви, т. е. не имеющий поддеревьев.
№6 слайд![Терминология Термины, взятые](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img5.jpg)
Содержание слайда: Терминология (2)
Термины, взятые из генеалогии, описывают отношения:
родительским (parent) называется узел, который находится непосредственно над другим узлом;
дочерним (child) называется узел, который находится непосредственно под другим узлом; дочерний узел также называют сыном (что не меняет "родственности" отношений);
предки данного узла — это все узлы на пути вверх от данного узла до корня;
потомки — все узлы, расположенные ниже данного;
сестринские (братские) — узлы, у которых один и тот же родитель.
№7 слайд![Терминология Список терминов,](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img6.jpg)
Содержание слайда: Терминология (3)
Список терминов, возникших в программировании:
внутренний узел (internal node) — узел, не являющийся листом;
порядок узла (node degree) — количество его дочерних узлов;
глубина (depth) узла — количество его предков плюс единица;
глубина (высота) дерева — максимальная глубина всех узлов;
длина пути к узлу — количество ветвей, которые нужно пройти, чтобы продвинуться от корня к данному узлу;
длина пути дерева — сумма длин путей всех его узлов. Она также называется длиной внутреннего пути.
№8 слайд![Основные операции с бинарными](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img7.jpg)
Содержание слайда: Основные операции с бинарными деревьями
При работе программы дерево может модифицироваться: добавляются или удаляются узлы, меняются информационные части узлов. То есть дерево является динамической структурой.
Поэтому узел дерева определяется как переменная с фиксированной структурой, содержащей информационную часть и две ссылки, указывающие на левое и правое поддеревья данного узла.
Ссылка на пустое дерево равна null.
№9 слайд![Описание узла дерева см.](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img8.jpg)
Содержание слайда: Описание узла дерева
см. TreeLevel
№10 слайд![Алгоритмы обхода дерева](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img9.jpg)
Содержание слайда: Алгоритмы обхода дерева
№11 слайд![Обход сверху вниз PreOrder](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img10.jpg)
Содержание слайда: Обход_сверху_вниз (PreOrder):
Обход_сверху_вниз (PreOrder):
обработать корень;
Обход_сверху_вниз левого поддерева;
Обход_сверху_вниз правого поддерева.
№12 слайд![Упорядоченное дерево](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img11.jpg)
Содержание слайда: Упорядоченное дерево
Упорядоченным называется дерево, в котором для каждого узла N значение левого дочернего узла меньше, чем значение в N, а значение правого дочернего узла больше значения в N.
Если в дереве могут содержаться одинаковые значения, то программист должен сам определить, влево или вправо помещать значение, равное значению в родительском узле, т. е. соответствующее строгое неравенство заменить на нестрогое.
№13 слайд![Сбалансированное дерево](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img12.jpg)
Содержание слайда: Сбалансированное дерево
Дерево называется идеально сбалансированным, если для каждого его узла количества узлов в левом и в правом его поддеревьях различаются не более чем на 1.
Разумеется, идеально сбалансированное дерево имеет минимальную высоту по сравнению со всеми другими деревьями с тем же числом узлов..
Чтобы построить такое дерево, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это сделать просто, если распределять узлы поровну слева и справа от каждого узла.
№14 слайд![Построение сбалансированного](/documents_6/b5ce2e712ed92d4f672b5aa8b27d2da4/img13.jpg)
Содержание слайда: Построение сбалансированного дерева
Алгоритм равномерного распределения при известном числе узлов N лучше всего выбрать рекурсивным:
Взять один узел в качестве корня.
Построить левое поддерево с числом узлов nLeft = N / 2 тем же способом.
Построить правое поддерево с числом узлов nRight = N – nLeft - 1 тем же способом.
см. TreeLevel