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

Нажмите для полного просмотра!
Основные операции с бинарными деревьями, слайд №1Основные операции с бинарными деревьями, слайд №2Основные операции с бинарными деревьями, слайд №3Основные операции с бинарными деревьями, слайд №4Основные операции с бинарными деревьями, слайд №5Основные операции с бинарными деревьями, слайд №6Основные операции с бинарными деревьями, слайд №7Основные операции с бинарными деревьями, слайд №8Основные операции с бинарными деревьями, слайд №9Основные операции с бинарными деревьями, слайд №10Основные операции с бинарными деревьями, слайд №11Основные операции с бинарными деревьями, слайд №12Основные операции с бинарными деревьями, слайд №13Основные операции с бинарными деревьями, слайд №14Основные операции с бинарными деревьями, слайд №15Основные операции с бинарными деревьями, слайд №16Основные операции с бинарными деревьями, слайд №17Основные операции с бинарными деревьями, слайд №18Основные операции с бинарными деревьями, слайд №19Основные операции с бинарными деревьями, слайд №20Основные операции с бинарными деревьями, слайд №21Основные операции с бинарными деревьями, слайд №22Основные операции с бинарными деревьями, слайд №23Основные операции с бинарными деревьями, слайд №24Основные операции с бинарными деревьями, слайд №25Основные операции с бинарными деревьями, слайд №26Основные операции с бинарными деревьями, слайд №27Основные операции с бинарными деревьями, слайд №28Основные операции с бинарными деревьями, слайд №29

Содержание

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

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


Слайд 1


Основные операции с бинарными деревьями, слайд №1
Описание слайда:

Слайд 2





существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем;
существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем;
каждый элемент связан с несколькими элементами следующего уровня иерархии. Эти элементы могут быть в свою очередь деревьями (поддеревьями);
каждый элемент промежуточного уровня порожден только одним элементом более высокого уровня.
Описание слайда:
существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем; существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем; каждый элемент связан с несколькими элементами следующего уровня иерархии. Эти элементы могут быть в свою очередь деревьями (поддеревьями); каждый элемент промежуточного уровня порожден только одним элементом более высокого уровня.

Слайд 3





Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.
Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.
Таким образом, дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня – потомками.
Описание слайда:
Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами. Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами. Таким образом, дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня – потомками.

Слайд 4





Узлы располагаются по уровням. 
Узлы располагаются по уровням. 
Корень – нулевой уровень и т.д. 
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.
Число непосредственных потомков внутреннего узла называется его степенью. 
Максимальная степень всех узлов есть степень дерева.
Описание слайда:
Узлы располагаются по уровням. Узлы располагаются по уровням. Корень – нулевой уровень и т.д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой. Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.

Слайд 5





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

Слайд 6





пройти все узлы в определенном порядке, 
пройти все узлы в определенном порядке, 
найти узел с заданным свойством, 
определить отца данного узла, 
определить сыновей данного узла, 
удалить определенный узел (поддерево), 
добавить новый узел
 и т.д.
Описание слайда:
пройти все узлы в определенном порядке, пройти все узлы в определенном порядке, найти узел с заданным свойством, определить отца данного узла, определить сыновей данного узла, удалить определенный узел (поддерево), добавить новый узел и т.д.

Слайд 7


Основные операции с бинарными деревьями, слайд №7
Описание слайда:

Слайд 8


Основные операции с бинарными деревьями, слайд №8
Описание слайда:

Слайд 9





Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. 
Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. 
Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой  - с левым. Листья имеют пустые указатели потомков.
Описание слайда:
Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой - с левым. Листья имеют пустые указатели потомков.

Слайд 10





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

Слайд 11





Разработать программу создания и редактирования бинарного дерева:
Разработать программу создания и редактирования бинарного дерева:
Добавление узлов
Удаление узлов
Задание текущего узла
Отображение на экране дерева
Описание слайда:
Разработать программу создания и редактирования бинарного дерева: Разработать программу создания и редактирования бинарного дерева: Добавление узлов Удаление узлов Задание текущего узла Отображение на экране дерева

Слайд 12





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;
Описание слайда:
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;

Слайд 13





{Поиск узла по содержимому}
{Поиск узла по содержимому}
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;
Описание слайда:
{Поиск узла по содержимому} {Поиск узла по содержимому} 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;

Слайд 14





{Вывод списка всех узлов дерева}
{Вывод списка всех узлов дерева}
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);
Описание слайда:
{Вывод списка всех узлов дерева} {Вывод списка всех узлов дерева} 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);

Слайд 15





{Удаление узла и всех его потомков в дереве}
{Удаление узла и всех его потомков в дереве}
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;
Описание слайда:
{Удаление узла и всех его потомков в дереве} {Удаление узла и всех его потомков в дереве} 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;

Слайд 16





{основная программа}
{основная программа}
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);
           
Описание слайда:
{основная программа} {основная программа} 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);            

Слайд 17





            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;
           
Описание слайда:
            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;            

Слайд 18





           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;
            
Описание слайда:
           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;             

Слайд 19





             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;            
Описание слайда:
             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;            

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

Слайд 21





             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.
Описание слайда:
             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.

Слайд 22





Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным:
Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным:
1) списки;
2) целый тип;
3) дерево;
4) стек.
Описание слайда:
Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным: Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным: 1) списки; 2) целый тип; 3) дерево; 4) стек.

Слайд 23





Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины:
Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины:
1) дерево;
2) множество;
3) стек;
4) массив.
Описание слайда:
Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины: Вопрос 2. Какая из ниже перечисленных структур данных отличается наличием вершины: 1) дерево; 2) множество; 3) стек; 4) массив.

Слайд 24





Вопрос 3. Описание
Вопрос 3. Описание
Var
    i, j : integer;
    x : real;
    s: string;
объявляет переменные. Переменная s будет является переменной типа:
целый;
действительный;
строка;
Массив.
Описание слайда:
Вопрос 3. Описание Вопрос 3. Описание Var     i, j : integer;     x : real;     s: string; объявляет переменные. Переменная s будет является переменной типа: целый; действительный; строка; Массив.

Слайд 25





Вопрос 4.  Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется:
Вопрос 4.  Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется:
1) массив;
2) дерево;
3) стек;
4) список.
Описание слайда:
Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется: Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов, называется: 1) массив; 2) дерево; 3) стек; 4) список.

Слайд 26





Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется:
Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется:
1) массив;
2) дерево;
3) стек;
4) запись.
Описание слайда:
Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется: Вопрос 5. Структура данных, объединяющая элементы данных разных типов, называется: 1) массив; 2) дерево; 3) стек; 4) запись.

Слайд 27





Вопрос 6. Структуру данных стек можно организовать с помощью:
Вопрос 6. Структуру данных стек можно организовать с помощью:
1) массивов;
2) деревьев;
3) записей;
4) графов.
Описание слайда:
Вопрос 6. Структуру данных стек можно организовать с помощью: Вопрос 6. Структуру данных стек можно организовать с помощью: 1) массивов; 2) деревьев; 3) записей; 4) графов.

Слайд 28





Вопрос 7. Частным случаем графа является:
Вопрос 7. Частным случаем графа является:
стек;
очередь;
дерево;
матрица.
Описание слайда:
Вопрос 7. Частным случаем графа является: Вопрос 7. Частным случаем графа является: стек; очередь; дерево; матрица.

Слайд 29





Вопрос 8. В бинарном дереве из каждой вершины выходит:
Вопрос 8. В бинарном дереве из каждой вершины выходит:
произвольное количество дуг;
не более двух дуг;
не более трех дуг;
четное количество дуг.
Описание слайда:
Вопрос 8. В бинарном дереве из каждой вершины выходит: Вопрос 8. В бинарном дереве из каждой вершины выходит: произвольное количество дуг; не более двух дуг; не более трех дуг; четное количество дуг.



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