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

ДЕРЕВО - СТРУКТУРА, КОТОРАЯ ХАРАКТЕРИЗУЕТСЯ СЛЕДУЮЩИМИ СВОЙСТВАМИ:

существует единственный элемент, на который

Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е.

Узлы располагаются по уровням.
Корень – нулевой уровень и т.д.
Максимальный

В бинарном дереве из каждой вершины выходит не более двух дуг.

ОСНОВНЫЕ ОПЕРАЦИИ НАД ДЕРЕВЬЯМИ:

пройти все узлы в определенном порядке,
найти узел

ПОЛНОЕ И НЕПОЛНОЕ БИНАРНЫЕ ДЕРЕВЬЯ

СТРОГО И НЕ СТРОГО БИНАРНЫЕ ДЕРЕВЬЯ

ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ :

Списочное представление бинарных деревьев основано на элементах, соответствующих

ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ :

В виде массива проще всего представляется полное бинарное

ПРИМЕР:

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

program bin_tree_edit;
type node=record
                name: string;
                left, right: pointer;
       end;
var
        n:integer;
        pnt_s,current_s,root:

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

{Вывод списка всех узлов дерева}
procedure node_list (pnt_s:pointer);
var
          pnt_n:^node;
begin
pnt_n:=pnt_s; writeln(pnt_n^.name);
if pnt_n^.left <>

{Удаление узла и всех его потомков в дереве}
procedure node_dispose (pnt_s:pointer);
var
           pnt_n:^node;
begin
if

{основная программа}
begin
new(current);root:=current;
current^.name:='root';
current^.left:=nil;
current^.right:=nil;
repeat
            writeln('текущий узел -',current^.name);
            writeln('1 – присвоить имя левому потомку');
           

            if n=1 then
            begin {Создание левого потомка}
                     if current^.left= nil

           if n=2 then
             begin {Создание правого потомка}
                       if current^.right= nil then

             if n=3 then
             begin {Поиск узла}
                     writeln('name ?');
                     readln;
                     read(s);
                    

             if n=4 then
             begin {Вывод списка узлов}
                    pnt_s:=root;
                    node_list(pnt_s);
             end;

             if n=5 then
             begin {Удаление поддерева}
                       writeln('l,r ?');
                       readln;
                       read(s);
                      

ТЕСТЫ:

Вопрос 1. Какие из указанных ниже структур данных относятся к встроенным:
1)

ТЕСТЫ:

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

ТЕСТЫ:

Вопрос 3. Описание
Var
    i, j : integer;
    x : real;
    s:

ТЕСТЫ:

Вопрос 4. Упорядоченная совокупность элементов некоторого типа, адресуемых при помощи одного

ТЕСТЫ:

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

ТЕСТЫ:

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

ТЕСТЫ:

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