Деревья - структуры данных - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья - структуры данных. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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