Презентация Основные операции с бинарными деревьями

Смотреть слайды в полном размере
Презентация Основные операции с бинарными деревьями


Вашему вниманию предлагается презентация «Основные операции с бинарными деревьями», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 29 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 1.83 MB

Просмотреть и скачать

Pic.1
Основные операции с бинарными деревьями, слайд 1
Pic.2
существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называ
существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем; существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем; каждый элемент связан с несколькими элементами следующего уровня иерархии. Эти элементы могут быть в свою очередь деревьями (поддеревьями); каждый элемент промежуточного уровня порожден только одним элементом более высокого уровня.
Pic.3
Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т. е. конечными) и
Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т. е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами. Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т. е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами. Таким образом, дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня – потомками.
Pic.4
Узлы располагаются по уровням. Узлы располагаются по уровням. Корень – нулевой уровень и т. д. Макси
Узлы располагаются по уровням. Узлы располагаются по уровням. Корень – нулевой уровень и т. д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой. Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.
Pic.5
В бинарном дереве из каждой вершины выходит не более двух дуг. В бинарном дереве из каждой вершины в
В бинарном дереве из каждой вершины выходит не более двух дуг. В бинарном дереве из каждой вершины выходит не более двух дуг. В сильноветвящемся дереве количество дуг может быть произвольным.
Pic.6
пройти все узлы в определенном порядке, пройти все узлы в определенном порядке, найти узел с заданны
пройти все узлы в определенном порядке, пройти все узлы в определенном порядке, найти узел с заданным свойством, определить отца данного узла, определить сыновей данного узла, удалить определенный узел (поддерево), добавить новый узел и т. д.
Pic.7
Основные операции с бинарными деревьями, слайд 7
Pic.8
Основные операции с бинарными деревьями, слайд 8
Pic.9
Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Списо
Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой - с левым. Листья имеют пустые указатели потомков.
Pic.10
В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго оп
В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве. В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве.
Pic.11
Разработать программу создания и редактирования бинарного дерева: Разработать программу создания и р
Разработать программу создания и редактирования бинарного дерева: Разработать программу создания и редактирования бинарного дерева: Добавление узлов Удаление узлов Задание текущего узла Отображение на экране дерева
Pic.12
program bin_tree_edit; program bin_tree_edit; type node=record name: string; left, right: pointer; e
program bin_tree_edit; program bin_tree_edit; type node=record name: string; left, right: pointer; end; var n:integer; pnt_s,current_s,root: pointer; pnt,current:^node; s: string;
Pic.13
{Поиск узла по содержимому} {Поиск узла по содержимому} procedure node_search (pnt_s:pointer; var cu
{Поиск узла по содержимому} {Поиск узла по содержимому} procedure node_search (pnt_s:pointer; var current_s:pointer); var pnt_n:^node; begin pnt_n:=pnt_s; writeln(pnt_n^. name); if not (pnt_n^. name=s) then begin if pnt_n^. left <> nil then node_search (pnt_n^. left,current_s); if pnt_n^. right <> nil then node_search (pnt_n^. right,current_s); end else current_s:=pnt_n; End;
Pic.14
{Вывод списка всех узлов дерева} {Вывод списка всех узлов дерева} procedure node_list (pnt_s:pointer
{Вывод списка всех узлов дерева} {Вывод списка всех узлов дерева} procedure node_list (pnt_s:pointer); var pnt_n:^node; begin pnt_n:=pnt_s; writeln(pnt_n^. name); if pnt_n^. left <> nil then node_list (pnt_n^. left); if pnt_n^. right <> nil then node_list (pnt_n^. right); end; procedure node_dispose (pnt_s:pointer);
Pic.15
{Удаление узла и всех его потомков в дереве} {Удаление узла и всех его потомков в дереве} procedure
{Удаление узла и всех его потомков в дереве} {Удаление узла и всех его потомков в дереве} procedure node_dispose (pnt_s:pointer); var pnt_n:^node; begin if pnt_s <> nil then begin pnt_n:=pnt_s; writeln(pnt_n^. name); if pnt_n^. left <> nil then node_dispose (pnt_n^. left); if pnt_n^. right <> nil then node_dispose (pnt_n^. right); dispose(pnt_n); end End;
Pic.16
{основная программа} {основная программа} begin new(current);root:=current; current^. name:='ro
{основная программа} {основная программа} begin new(current);root:=current; current^. name:='root'; current^. left:=nil; current^. right:=nil; repeat writeln('текущий узел -',current^. name); writeln('1 – присвоить имя левому потомку'); writeln('2 – присвоить имя правому потомку'); writeln('3 – сделать узел текущим'); writeln('4 – вывести список всех узлов'); writeln('5 – удалить потомков текущего узла'); read(n);
Pic.17
if n=1 then if n=1 then begin {Создание левого потомка} if current^. left= nil then new(pnt) else pn
if n=1 then if n=1 then begin {Создание левого потомка} if current^. left= nil then new(pnt) else pnt:= current^. left; writeln('left ?'); readln; read(s); pnt^. name:=s; pnt^. left:=nil; pnt^. right:=nil; current^. left:= pnt; end;
Pic.18
if n=2 then if n=2 then begin {Создание правого потомка} if current^. right= nil then new(pnt) else
if n=2 then if n=2 then begin {Создание правого потомка} if current^. right= nil then new(pnt) else pnt:= current^. right; writeln('right ?'); readln; read(s); pnt^. name:=s; pnt^. left:=nil; pnt^. right:=nil; current^. right:= pnt; end;
Pic.19
if n=3 then if n=3 then begin {Поиск узла} writeln('name ?'); readln; read(s); current_s:=
if n=3 then if n=3 then begin {Поиск узла} writeln('name ?'); readln; read(s); current_s:=nil; pnt_s:=root; node_search (pnt_s, current_s); if current_s <> nil then current:=current_s; end;
Pic.20
if n=4 then if n=4 then begin {Вывод списка узлов} pnt_s:=root; node_list(pnt_s); end;
if n=4 then if n=4 then begin {Вывод списка узлов} pnt_s:=root; node_list(pnt_s); end;
Pic.21
if n=5 then if n=5 then begin {Удаление поддерева} writeln('l,r ?'); readln; read(s); if (
if n=5 then if n=5 then begin {Удаление поддерева} writeln('l,r ?'); readln; read(s); if (s='l') then begin {Удаление левого поддерева} pnt_s:=current^. left; current^. left:=nil; node_dispose(pnt_s); end else begin {Удаление правого поддерева} pnt_s:=current^. right; current^. right:=nil; node_dispose(pnt_s); end; end; until n=0 end.
Pic.22
Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным: Вопрос 1. Какие из указанн
Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным: Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным: 1) списки; 2) целый тип; 3) дерево; 4) стек.
Pic.23
Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины: Вопрос 2. Какая и
Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины: Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины: 1) дерево; 2) множество; 3) стек; 4) массив.
Pic.24
Вопрос 3. Описание Вопрос 3. Описание Var i, j : integer; x : real; s: string; объявляет переменные.
Вопрос 3. Описание Вопрос 3. Описание Var i, j : integer; x : real; s: string; объявляет переменные. Переменная s будет является переменной типа: целый; действительный; строка; Массив.
Pic.25
Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нес
Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется: Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется: 1) массив; 2) дерево; 3) стек; 4) список.
Pic.26
Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется: Вопрос 5. Структу
Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется: Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется: 1) массив; 2) дерево; 3) стек; 4) запись.
Pic.27
Вопрос 6. Структуру данных стек можно организовать с помощью: Вопрос 6. Структуру данных стек можно
Вопрос 6. Структуру данных стек можно организовать с помощью: Вопрос 6. Структуру данных стек можно организовать с помощью: 1) массивов; 2) деревьев; 3) записей; 4) графов.
Pic.28
Вопрос 7. Частным случаем графа является: Вопрос 7. Частным случаем графа является: стек; очередь; д
Вопрос 7. Частным случаем графа является: Вопрос 7. Частным случаем графа является: стек; очередь; дерево; матрица.
Pic.29
Вопрос 8. В бинарном дереве из каждой вершины выходит: Вопрос 8. В бинарном дереве из каждой вершины
Вопрос 8. В бинарном дереве из каждой вершины выходит: Вопрос 8. В бинарном дереве из каждой вершины выходит: произвольное количество дуг; не более двух дуг; не более трех дуг; четное количество дуг.


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!