🗊Презентация Деревья - структуры данных

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Деревья - структуры данных, слайд №1Деревья - структуры данных, слайд №2Деревья - структуры данных, слайд №3Деревья - структуры данных, слайд №4Деревья - структуры данных, слайд №5Деревья - структуры данных, слайд №6Деревья - структуры данных, слайд №7Деревья - структуры данных, слайд №8Деревья - структуры данных, слайд №9Деревья - структуры данных, слайд №10Деревья - структуры данных, слайд №11Деревья - структуры данных, слайд №12Деревья - структуры данных, слайд №13Деревья - структуры данных, слайд №14
Скачать
Вы можете ознакомиться и скачать презентацию на тему Деревья - структуры данных. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Программирование Деревья
Описание слайда:
Программирование Деревья

Слайд 2


Деревья - структуры данных, слайд №2
Описание слайда:

Слайд 3


Деревья -- структуры данных, определяемые с помощью рекурсии. Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом T — это: либо пустая структура; либо узел типа T, с которым связано конечное число древовидных структур, называемых поддеревьями (subtree). Если с узлом связаны только два поддерева, то дерево называется бинарным.
Описание слайда:
Деревья -- структуры данных, определяемые с помощью рекурсии. Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом T — это: либо пустая структура; либо узел типа T, с которым связано конечное число древовидных структур, называемых поддеревьями (subtree). Если с узлом связаны только два поддерева, то дерево называется бинарным.

Слайд 4


Деревья - структуры данных, слайд №4
Описание слайда:

Слайд 5


Терминология (1) Из ботаники взяты такие определения: узел (node) — это точка, где может возникнуть ветвь. корень (root) — "верхний" узел дерева.; ветвь (brunch) — отрезок, описывающий связь между двумя узлами; лист (leaf) — узел, из которого не выходят ветви, т. е. не имеющий поддеревьев.
Описание слайда:
Терминология (1) Из ботаники взяты такие определения: узел (node) — это точка, где может возникнуть ветвь. корень (root) — "верхний" узел дерева.; ветвь (brunch) — отрезок, описывающий связь между двумя узлами; лист (leaf) — узел, из которого не выходят ветви, т. е. не имеющий поддеревьев.

Слайд 6


Терминология (2) Термины, взятые из генеалогии, описывают отношения: родительским (parent) называется узел, который находится непосредственно над другим узлом; дочерним (child) называется узел, который находится непосредственно под другим узлом; дочерний узел также называют сыном (что не меняет "родственности" отношений); предки данного узла — это все узлы на пути вверх от данного узла до корня; потомки — все узлы, расположенные ниже данного; сестринские (братские) — узлы, у которых один и тот же родитель.
Описание слайда:
Терминология (2) Термины, взятые из генеалогии, описывают отношения: родительским (parent) называется узел, который находится непосредственно над другим узлом; дочерним (child) называется узел, который находится непосредственно под другим узлом; дочерний узел также называют сыном (что не меняет "родственности" отношений); предки данного узла — это все узлы на пути вверх от данного узла до корня; потомки — все узлы, расположенные ниже данного; сестринские (братские) — узлы, у которых один и тот же родитель.

Слайд 7


Терминология (3) Список терминов, возникших в программировании: внутренний узел (internal node) — узел, не являющийся листом; порядок узла (node degree) — количество его дочерних узлов; глубина (depth) узла — количество его предков плюс единица; глубина (высота) дерева — максимальная глубина всех узлов; длина пути к узлу — количество ветвей, которые нужно пройти, чтобы продвинуться от корня к данному узлу; длина пути дерева — сумма длин путей всех его узлов. Она также называется длиной внутреннего пути.
Описание слайда:
Терминология (3) Список терминов, возникших в программировании: внутренний узел (internal node) — узел, не являющийся листом; порядок узла (node degree) — количество его дочерних узлов; глубина (depth) узла — количество его предков плюс единица; глубина (высота) дерева — максимальная глубина всех узлов; длина пути к узлу — количество ветвей, которые нужно пройти, чтобы продвинуться от корня к данному узлу; длина пути дерева — сумма длин путей всех его узлов. Она также называется длиной внутреннего пути.

Слайд 8


Основные операции с бинарными деревьями При работе программы дерево может модифицироваться: добавляются или удаляются узлы, меняются информационные части узлов. То есть дерево является динамической структурой. Поэтому узел дерева определяется как переменная с фиксированной структурой, содержащей информационную часть и две ссылки, указывающие на левое и правое поддеревья данного узла. Ссылка на пустое дерево равна null.
Описание слайда:
Основные операции с бинарными деревьями При работе программы дерево может модифицироваться: добавляются или удаляются узлы, меняются информационные части узлов. То есть дерево является динамической структурой. Поэтому узел дерева определяется как переменная с фиксированной структурой, содержащей информационную часть и две ссылки, указывающие на левое и правое поддеревья данного узла. Ссылка на пустое дерево равна null.

Слайд 9


Описание узла дерева см. TreeLevel
Описание слайда:
Описание узла дерева см. TreeLevel

Слайд 10


Алгоритмы обхода дерева
Описание слайда:
Алгоритмы обхода дерева

Слайд 11


Обход_сверху_вниз (PreOrder): Обход_сверху_вниз (PreOrder): обработать корень; Обход_сверху_вниз левого поддерева; Обход_сверху_вниз правого поддерева.
Описание слайда:
Обход_сверху_вниз (PreOrder): Обход_сверху_вниз (PreOrder): обработать корень; Обход_сверху_вниз левого поддерева; Обход_сверху_вниз правого поддерева.

Слайд 12


Упорядоченное дерево Упорядоченным называется дерево, в котором для каждого узла N значение левого дочернего узла меньше, чем значение в N, а значение правого дочернего узла больше значения в N. Если в дереве могут содержаться одинаковые значения, то программист должен сам определить, влево или вправо помещать значение, равное значению в родительском узле, т. е. соответствующее строгое неравенство заменить на нестрогое.
Описание слайда:
Упорядоченное дерево Упорядоченным называется дерево, в котором для каждого узла N значение левого дочернего узла меньше, чем значение в N, а значение правого дочернего узла больше значения в N. Если в дереве могут содержаться одинаковые значения, то программист должен сам определить, влево или вправо помещать значение, равное значению в родительском узле, т. е. соответствующее строгое неравенство заменить на нестрогое.

Слайд 13


Сбалансированное дерево Дерево называется идеально сбалансированным, если для каждого его узла количества узлов в левом и в правом его поддеревьях различаются не более чем на 1. Разумеется, идеально сбалансированное дерево имеет минимальную высоту по сравнению со всеми другими деревьями с тем же числом узлов.. Чтобы построить такое дерево, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это сделать просто, если распределять узлы поровну слева и справа от каждого узла.
Описание слайда:
Сбалансированное дерево Дерево называется идеально сбалансированным, если для каждого его узла количества узлов в левом и в правом его поддеревьях различаются не более чем на 1. Разумеется, идеально сбалансированное дерево имеет минимальную высоту по сравнению со всеми другими деревьями с тем же числом узлов.. Чтобы построить такое дерево, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это сделать просто, если распределять узлы поровну слева и справа от каждого узла.

Слайд 14


Построение сбалансированного дерева Алгоритм равномерного распределения при известном числе узлов N лучше всего выбрать рекурсивным: Взять один узел в качестве корня. Построить левое поддерево с числом узлов nLeft = N / 2 тем же способом. Построить правое поддерево с числом узлов nRight = N – nLeft - 1 тем же способом. см. TreeLevel
Описание слайда:
Построение сбалансированного дерева Алгоритм равномерного распределения при известном числе узлов N лучше всего выбрать рекурсивным: Взять один узел в качестве корня. Построить левое поддерево с числом узлов nLeft = N / 2 тем же способом. Построить правое поддерево с числом узлов nRight = N – nLeft - 1 тем же способом. см. TreeLevel

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию