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