Перечислите узлы которые являются потомками узла а
Перейти к содержимому

Перечислите узлы которые являются потомками узла а

  • автор:

Как называется узел дерева, у которого нет потомков?

nelle987

Узел дерева без потомков — лист, без предков — корневой узел.

Новые вопросы в Информатика

Повідомлення про бази даних

Складіть опитувальник з вашого улюбленого предмета. У вікні опитувальника під запитанням розмістіть кнопки «так» і «ні». Якщо користувач натисне прави … льну кнопку, то у відповідь має отримати вікно з повідомленням, яке пояснює відповідь на запитання. А якщо неправильну – тоді вікно із цим поясненням буде мати вигляд вікна showerror.​

Повідомлення про бази даних.

пожалуйста быстрее нужно сдать через 30 минут даю 97 балов лучший ответ и подписуюсь​

За допомогою функції int () створіть з рядка ціле число. Переконайтеся, що в результаті виходить саме ціле число!​

Перечислите узлы которые являются потомками узла а

Дерево — это нелинейная динамическая структура данных, представленных в виде иерархии элементов, называемых узлами . Схематично дерево можно изобразить так, как показано на рисунке ниже:

На самом верхнем уровне такой иерархии всегда имеется только один узел, называемый корнем дерева . У нас это узел A . Каждый узел, кроме корневого, связан только с одним узлом более высокого уровня, называемым узлом-предком . Например, для узла D предком является узел A , предок для узла G — это D и т.д. При этом каждый элемент дерева может быть связан с помощью ветвей ( ребер ) с одним или несколькими узлами более низкого уровня. Они для данного узла являются дочерними узлами ( узлами-потомками ). Так, для узла A потомками будут B , C и D , для узла B — E и F и т.д. Элементы, расположенные в конце ветвей и не имеющие дочерних узлов, называют листьями . На рисунке выше листьями являются узлы E , F , C , G , J и I .

От корня до любого узла всегда существует только один путь. Максимальная длина пути от корня до листьев называется высотой дерева . У нас максимально длинный путь образует цепочка узлов A , D , H и J , т.е. высота дерева равна 3 .

Любой узел дерева с его потомками также образует дерево, называемое поддеревом (относительно исходного дерева). Например, можно рассматривать поддерево, начинающееся с узла D (это узлы D , G , H , I , J ).

Число поддеревьев для данного узла образует степень узла . Для узлов A и D степень равна 3 , степень узла B равна 2 , узел H имеет степень 1 , а у листьев (узлы E , F , C , G , J и I ) степень равна 0 . Максимальное значение среди степеней всех узлов определяет степень дерева . Если максимальная степень узлов в каком-то дереве равна n , то его называют n -арным деревом . Наше дерево имеет степень 3 (из-за узлов A и D ), и его можно называть триарным .

Дерево степени 2 называется бинарным . Бинарные деревья наиболее просты с точки зрения сложности реализации алгоритмов работы с деревьями, поэтому именно бинарные деревья применяются там, где требуется динамическая структура типа дерево. Если формально требуется дерево степени большей, чем 2 , например, 5 -й степени, то, сформировав такое дерево, его можно преобразовать в бинарное, а далее работать как с бинарным деревом.

Как правило, в дереве всегда задают какой-либо принцип упорядоченности, например, по возрастанию какого-то параметра (ключа). То есть, для каждого узла ключи наследников располагаются слева направо по возрастанию. В бинарном дереве для каждого узла значение ключа левого наследника будет меньше значения ключа узла, в свою очередь значение ключа в узле меньше значения ключа в правом наследнике.

Типовые операции с двоичными деревьями

Для работы с двоичными деревьями используем две структуры:

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

2) Структура, определяющая узел дерева :

§ 43. Деревья

Как вы знаете из учебника 10 класса, дерево — это структура, отражающая иерархию (отношения подчинённости, многоуровне­вые связи). Напомним некоторые основные понятия, связанные с деревьями.

Дерево состоит из узлов и связей между ними (они называют­ся дугами). Самый первый узел, расположенный на верхнем уров­не (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — это промежуточные узлы.

Из двух связанных узлов тот, который находится на более вы­соком уровне, называется родителем, а другой — сыном. Ко­рень — это единственный узел, у которого нет родителя; у листьев нет сыновей.

Используются также понятия «предок» и «потомок». Пото­мок какого-то узла — это узел, в который можно перейти пострелкам от узла-предка. Соответствен­но, предок какого-то узла — это узел, из которого можно перейти по стрел­кам в данный узел.

В дереве на рис. 6.11 родитель узла Е — это узел В, а предки узла Е — это узлы А и В, для которых узел Е — по­ томок. Потомками узла А (корня дерева) являются все остальные узлы.

Высота дерева — это наибольшее расстояние (количество дуг) от корня до листа. Высота дерева, приведённого на рис. 6.11, равна 2.
Формально дерево можно определить следующим образом:

  1. пустая структура — это дерево;
  2. дерево — это корень и несколько связанных с ним отдельных
    (не связанных между собой) деревьев.

Чаще всего в информатике используются двоичные (или би­нарные) деревья, т. е. такие, в которых каждый узел имеет не бо­лее двух сыновей. Их также можно определить рекурсивно.

Деревья широко применяются в следующих задачах:

  • поиск в большом массиве не меняющихся данных;
  • сортировка данных;
  • вычисление арифметических выражений;
  • оптимальное кодирование данных (метод сжатия Хаффмана).

Известно, что для того, чтобы найти заданный элемент в не­упорядоченном массиве из N элементов, может понадобиться N сравнений. Теперь предположим, что элементы массива организо­ваны в виде специальным образом построенного дерева, например как показано на рис. 6.12.

Значения, связанные с узлами дерева, по которым выполняется поиск, называются ключами этих узлов (кроме ключа узел может содержать множество других данных). Перечислим важные свой­ства дерева, показанного на рис. 6.12:

  • слева от каждого узла находятся узлы, ключи которых
    меньше или равны ключу данного узла;
  • справа от каждого узла находятся узлы, ключи которых
    больше или равны ключу данного узла.

Дерево, обладающее такими свойствами, называется двоичным деревом поиска.

Например, пусть нужно найти узел, ключ которого равен 4. Начинаем поиск по дереву с корня. Ключ корня — 6 (больше за­данного), поэтому дальше нужно искать только в левом поддереве и т. д. Если при линейном поиске в массиве за одно сравнение от­секается 1 элемент, здесь — сразу примерно половина оставших­ся. Количество операций сравнения в этом случае пропорциональ­но \og2N, т. е. алгоритм имеет асимптотическую сложность O(logaJV). Конечно, нужно учитывать, что предварительно дерево должно быть построено. Поэтому такой алгоритм выгодно приме­нять в тех случаях, когда данные меняются редко, а поиск вы­полняется часто (например, в базах данных).

Обход двоичного дерева

Обойти дерево — это значит «посетить» все узлы по одному разу. Если перечислить узлы в порядке их посещения, мы пред­ставим данные в виде списка.

Существуют несколько способов обхода дерева:

• КЛП — «корень — левый — правый» (обход в прямом порядке):

посетить корень обойти левое поддерево обойти правое поддерево

• ЛКП — «левый — корень — правый» (симметричный обход):
обойти левое поддерево

обойти правое поддерево

• ЛПК — «левый — правый — корень» (обход в обратном по­
рядке):

обойти левое поддерево обойти правое поддерево посетить корень

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

Рассмотрим дерево, которое может быть составлено для вычис­ления арифметического выражения (1 + 4) * (9 — 5) (рис. 6.13).

Выражение вычисляется по такому дереву снизу вверх, т. е. посе­щение корня дерева — это последняя выполняемая операция.

Различные типы обхода дают последовательность узлов:

В первом случае мы получили префиксную форму записи арифме­тического выражения, во втором — привычную нам инфиксную форму (только без скобок), а в третьем — постфиксную форму. Напомним, что в префиксной и в постфиксной формах скобки не нужны.

Обход КЛП называется «обходом в глубину», потому что сна­чала мы идём вглубь дерева по левым поддеревьям, пока не дойдём до листа. Такой обход можно выполнить с помощью стека следующим образом:

записать в стек корень дерева

нц пока стек не пуст

выбрать узел V с вершины стека

посетить узел V

если у узла V есть правый сын то

добавить в стек правого сына V

все

если у узла V есть левый сын то

добавить в стек левого сына V

все

кц

На рисунке 6.14 показано изменение состояния стека при та­ком обходе дерева, изображенного на рис. 6.13. Под стеком запи­сана метка узла, который посещается (например, данные из этого узла выводятся на экран).

Существует ещё один способ обхода, который называют обхо­дом в ширину. Сначала посещают корень дерева, затем — всех его сыновей, затем — сыновей сыновей («внуков») и т. д., посте­пенно спускаясь на один уровень вниз. Обход в ширину для при­ведённого выше дерева даст такую последовательность посещения узлов:

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

записать в очередь корень дерева нц пока очередь не пуста

выбрать первый узел V из очереди

посетить узел V

если у узла V есть левый сын то добавить в очередь левого сына V

все

если у узла V есть правый сын то добавить в очередь правого сына V

все

кц

Вычисление арифметических выражений

Один из способов вычисления арифметических выражений основан на использовании дерева. Сначала выражение, записан­ное в линейном виде (в одну строку), нужно «разобрать» и постро­ить соответствующее ему дерево. Затем в результате прохода по этому дереву от листьев к корню вычисляется результат.

Для простоты будем рассматривать только арифметические выражения, содержащие числа и знаки четырёх арифметических операций: + — * /. Построим дерево для выражения

Нужно сначала найти последнюю операцию, просматривая выражение слева направо. Здесь последняя операция — это вто­рое вычитание, оно оказывается в корне дерева (рис. 6.15).

Как выполнить этот поиск в программе? Известно, что операции выполняются в порядке приоритета (старшинства): сначала опе­рации с более высоким приоритетом (слева направо), потом — с более низким (также слева направо). Отсюда следует важный вывод.

В корень дерева нужно поместить поспеднюю из операций с наименьшим приоритетом.

Теперь нужно построить таким же способом лез поддеревья (рис. 6.16).

Эта процедура рекурсивная, её можно записать в виде псевдокода:

найти последнюю выполняемую операцию

если операций нет то

все

поместить найденную операцию в корень дерева

построить левое поддерево

построить правое поддерево

Рекурсия заканчивается, когда в оставшейся части строки нет ни одной операции, значит, там находится число (это лист дерева).

Теперь вычислим выражение по дереву. Если в корне нахо­дится знак операции, её нужно применить к результатам вычис­ления поддеревьев:

nl:=значение левого поддерева

п2:=значение правого поддерева

Снова получился рекурсивный алгоритм.

Возможен особый случай (на нём заканчивается рекурсия), когда корень дерева содержит число (т. е. это лист). Это число и будет результатом вычисления выражения.

Использование связанных структур

Поскольку двоичное дерево — это нелинейная структура дан­ных, использовать динамический массив для размещения элемен­тов не очень удобно (хотя возможно). Вместо этого будем исполь­зовать связанные узлы. Каждый такой узел — это структура, со­держащая три области: область данных, ссылка на левое поддерево (указатель) и ссылка на правое поддерево (второй ука­затель). У листьев нет сыновей, в этом случае в указатели будем записывать значение nil (нулевой указатель). Дерево, состоящее из трёх таких узлов, показано на рис. 6.18.

В данном случае область данных узла будет содержать одно поле — символьную строку, в которую записывается знак опера­ции или число в символьном виде.

Введём два новых типа: TNode — узел дерева, и PNode — указатель (ссылку) на такой узел:

type
PNode = «TNode;

left, right: PNode

end;

Самый важный момент — выделение памяти под новую структуру. Предположим, что р — это переменная-указатель типа PNode. Для того чтобы выделить память под новую структуру и записать адрес выделенного блока в р, используется процедура

Как программа определяет, сколько памяти нужно выделить? Чтобы ответить на этот вопрос, вспомним, что указатель р указы-вает на структуру типа TNode, размер которой и определяет раз-мер выделяемого блока памяти.
Для освобождения памяти служит процедура Dispose (англ. dispose — ликвидировать):

Dispose(p);
В основной программе объявим одну переменную типа PNode — это будет ссылка на корень дерева:
var T: PNode;
Вычисление выражения сводится к двум вызовам функций:

T:=Tree(s);
writeIn(‘Результат: ‘, Calc (Т) ) ;

Здесь предполагается, что арифметическое выражение записано в символьной строке s, функция Tree строит в памяти дерево по этой строке, а функция Calc — вычисляет значение выражения по готовому дереву.

При построении дерева нужно выделять в памяти новый узел и искать последнюю выполняемую операцию — это будет делать функция LastOp. Она возвращает О, если ни одной операции не обнаружено, в этом случае создаётся лист — узел без потомков. Если операция найдена, её обозначение записывается в поле data, а в указатели записываются адреса поддеревьев, которые строятся рекурсивно для левой и правой частей выражения:

function Tree(s: string): PNode;

var k: integer;

New(Tree); (выделить память>

if k=0 then begin

end

else begin

Тгее Л .right:=Tree(Copy(s,k+1,Length(s)-k))

end

end;

Функция Calc тоже будет рекурсивной:
function Calc(Tree: PNode) : integer,
var nl, n2, res: integer;
begin
if Tree-4, left = nil then
Val(Tree».data, Calc, res) else begin
nl:=Calc(ТгееЛ.left);

case Tree^.data[1] of

else Calc:=MaxInt end

end;
Если ссылка, переданная функции, указывает на лист (нет левого поддерева), то значение выражения — это результат преобразова-ния числа из символьной формы в числовую (с помощью процеду¬ры Val). В противном случае вычисляются значения для левого и правого поддеревьев и к ним применяется операция, указанная в корне дерева. В случае ошибки (неизвестной операции) функ¬ция возвращает значение Maxlnt — максимальное целое число.
Осталось написать функцию LastOp, Нужно найти в символь-ной строке последнюю операцию с минимальным приоритетом. Для этого составим функцию, возвращающую приоритет опера¬ции (переданного ей символа):
function Priority(op: char): integer;

begin
case op of

‘+’,’-‘: Priority:=1;
‘*’,’/’: Priority:=2;
else Priority:=100
end
end;
Сложение и вычитание имеют приоритет 1, умножение и деле¬ние — приоритет 2, а все остальные символы (не операции) — приоритет 100 (условное значение).

Функция LastOp может выглядеть так:

function LastOp(s: string): integer;

var 1, minPrt: integer;

for i:=l to Length(s) do

end

end;

Обратите внимание, что в условном операторе указано нестрогое неравенство, чтобы найти именно последнюю операцию с наи­меньшим приоритетом. Начальное значение переменной minPrt можно выбрать любое между наибольшим приоритетом операций (2) и условным кодом не-операции (100). Тогда если найдена лю­бая операция, условный оператор срабатывает, а если в строке нет операций, условие всегда ложно и в переменной LastOp оста­ется начальное значение 0.

Хранение двоичного дерева в массиве

Двоичные деревья можно хранить в (динамическом) массиве почти так же, как и списки. Вопрос о том, как сохранить струк­туру (взаимосвязь узлов), решается следующим образом. Если нумерация элементов массива А начинается с 1, то сыновья эле­мента A[i] — это A[Z*i] и AJS4+1>. На рисунке 6.19 показан по­рядок расположения элементов в массиве для дерева, соответ­ствующего выражению

Алгоритм вычисления выражения остаётся прежним, изменяется только метод хранения данных. Обратите внимание, что некото­рые элементы остались пустыми, это значит, что их родитель — лист дерева.

Динамические структуры данных Деревья

ДеревьяДинамические структуры данных

  • Рабочий лист «Способности человека»

3 слайд 3
Деревья
Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга.
Корень – это начальный узел дерева.
Лист – это узел, из которого не выходит ни одной дуги.
корень
2
8
5
6
9
1
3
4
10
7
Какие структуры – не деревья?
4
1
3
2
5
2
4
6
1
3
5
3
2
1
3
2
1
4

4ДеревьяПредок узла x – это узел, из которого существует путь по стрелкам в у.

4 слайд 4
Деревья
Предок узла x – это узел, из которого существует путь по стрелкам в узел x.
Потомок узла x – это узел, в который существует путь по стрелкам из узла x.
Родитель узла x – это узел, из которого существует дуга непосредственно в узел x.
С помощью деревьев изображаются отношения
подчиненности (иерархия, «старший – младший»,
«родитель – ребенок»).
!
2
4
6
1
3
5
Сын узла x – это узел, в который существует дуга непосредственно из узла x.
Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x.
Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).

5Дерево – рекурсивная структура данныхРекурсивное определение: Пустая структу.

5 слайд 5
Дерево – рекурсивная структура данных
Рекурсивное определение:
Пустая структура – это дерево.
Дерево – это корень и несколько связанных с ним деревьев.
2
4
6
1
3
5
Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей.
Пустая структура – это двоичное дерево.
Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).

6Двоичные деревьяСтруктура узла:struct Node < int data; // полезн.

6 слайд 6
Двоичные деревья
Структура узла:
struct Node int data; // полезные данные
Node *left, *right; // ссылки на левого
// и правого сыновей
>;
typedef Node *PNode;
Применение:
поиск данных в специально построенных деревьях
(базы данных);
сортировка данных;
вычисление арифметических выражений;
кодирование (метод Хаффмана).

Двоичные деревьяМногие полезные структуры данных основаны на двоичном дереве.

7 слайд Двоичные деревья
Многие полезные структуры данных основаны на двоичном дереве:
Двоичное дерево поиска
Двоичная куча
АВЛ-дерево
Красно-чёрное дерево
Матричное дерево
Дерево Фибоначчи
Суффиксное дерево
7

8Двоичные деревья поиска164530761259859 Какая закономерность??Слева от кажд.

8 слайд 8
Двоичные деревья поиска
16
45
30
76
125
98
59
Какая закономерность?
?
Слева от каждого узла находятся узлы с меньшими ключами, а справа – с бóльшими.
Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры).
Как искать ключ, равный x:
если дерево пустое, ключ не найден;
если ключ узла равен x, то стоп.
если ключ узла меньше x, то искать x в левом поддереве;
если ключ узла больше x, то искать x в правом поддереве.
Сведение задачи к такой же задаче меньшей
размерности – это …?
?

9Двоичные деревья поискаДвоичное дерево поиска— это двоичное дерево, для кот.

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

10Двоичные деревья поиска164530761259859Поиск в массиве (N элементов):1645307.

10 слайд 10
Двоичные деревья поиска
16
45
30
76
125
98
59
Поиск в массиве (N элементов):
16
45
30
76
125
98
59
При каждом сравнении отбрасывается 1 элемент.
Число сравнений – N.
Поиск по дереву (N элементов):
При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log2N.
быстрый поиск
нужно заранее построить дерево;
желательно, чтобы дерево было минимальной высоты.

Несбалансированные двоичные деревья поиска (unbalanced) Это такие деревья, вы.

11 слайд Несбалансированные двоичные деревья поиска (unbalanced)

Это такие деревья, высота правого и левого поддеревьев которых отличаются более, чем на 1.
Дерево двоичного поиска становится несбалансированным, когда в него постоянно добавляются элементы большего или меньшего размера

Неполные двоичные деревья поиска (incomplete)Каждый узел дерева двоичного пои.

12 слайд Неполные двоичные деревья поиска (incomplete)
Каждый узел дерева двоичного поиска должен содержать не более 2 детей.
Но он может иметь 1 ребенка или не иметь детей.
Если в дереве есть такие хотя бы один такой узел, дерево называют неполным.
12

Основные операции в двоичном дереве поиска Базовый интерфейс двоичного дерева.

13 слайд Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:
Поиск узла, в котором хранится пара (key, value) с key = K.
Добавление в дерево пары (key, value) = (K, V).
Удаление узла, в котором хранится пара (key, value) с key = K.
13

Поиск элемента Дано: дерево Т и ключ K. Задача: проверить, есть ли узел с клю.

14 слайд Поиск элемента
Дано: дерево Т и ключ K.
Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.
Алгоритм:
Если дерево пусто, сообщить, что узел не найден, и остановиться.
Иначе сравнить K со значением ключа корневого узла X.
Если K=X, выдать ссылку на этот узел и остановиться.
Если K>X, рекурсивно искать ключ K в правом поддереве Т.
Если K

Добавление элемента Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V).

15 слайд Добавление элемента
Дано: дерево Т и пара (K,V).
Задача: добавить пару (K, V) в дерево Т.
Алгоритм:
Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
Иначе сравнить K с ключом корневого узла X.
Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
Если K

Удаление узла Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева.

16 слайд Удаление узла
Дано: дерево Т с корнем n и ключом K.
Задача: удалить из дерева Т узел с ключом K (если такой есть).
Алгоритм:
Если дерево T пусто, остановиться
Иначе сравнить K с ключом X корневого узла n.
Если K>X, рекурсивно удалить K из правого поддерева Т.
Если KЕсли K=X, то необходимо рассмотреть три случая.
Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла.
Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m.
Если оба ребёнка присутствуют, то
найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
присвоим ссылке Left(m) значение Left(n)
ссылку на узел n в узле Parent(n) заменить на Right(n);
освободим память, занимаемую узлом n (на него теперь никто не указывает).
16

17Реализация алгоритма поиска//--------------------------------------- // Фун.

17 слайд 17
Реализация алгоритма поиска
//—————————————
// Функция Search – поиск по дереву
// Вход: Tree — адрес корня,
// x — что ищем
// Выход: адрес узла или NULL (не нашли)
//—————————————
PNode Search (PNode Tree, int x)
if ( ! Tree ) return NULL;
if ( x == Tree->data )
return Tree;
if ( x < Tree->data )
return Search(Tree->left, x);
else
return Search(Tree->right, x);
>
дерево пустое: ключ не нашли…
нашли, возвращаем адрес корня
искать в левом поддереве
искать в правом поддереве

18Как построить дерево поиска?//---------------------------------------------.

18 слайд 18
Как построить дерево поиска?
//———————————————
// Функция AddToTree – добавить элемент к дереву
// Вход: Tree — адрес корня,
// x — что добавляем
//———————————————-
void AddToTree (PNode &Tree, int x)
if ( ! Tree ) Tree = new Node;
Tree->data = x;
Tree->left = NULL;
Tree->right = NULL;
return;
>
if ( x < Tree->data )
AddToTree ( Tree->left, x );
else AddToTree ( Tree->right, x );
>
дерево пустое: создаем новый узел (корень)
адрес корня может измениться
добавляем к левому или правому поддереву
Минимальная высота не гарантируется!
!

19Обход дерева164530761259859Обход дерева – это перечисление всех узлов в опр.

19 слайд 19
Обход дерева
16
45
30
76
125
98
59
Обход дерева – это перечисление всех узлов в определенном порядке.
Обход ЛКП («левый – корень – правый»):
125
98
76
45
59
30
16
Обход ПКЛ («правый – корень – левый»):
16
30
45
76
59
98
125
Обход КЛП («корень – левый – правый»):
125
76
98
16
45
30
59
Обход ЛПК («левый – правый – корень»):
59
98
125
30
76
45
16

20Обход дерева – реализация//--------------------------------------------- //.

20 слайд 20
Обход дерева – реализация
//———————————————
// Функция LKP – обход дерева в порядке ЛКП
// (левый – корень – правый)
// Вход: Tree — адрес корня
//———————————————-
void LKP( PNode Tree )
if ( ! Tree ) return;
LKP ( Tree->left );
printf ( «%d «, Tree->data );
LKP ( Tree->right );
>
обход этой ветки закончен
обход левого поддерева
вывод данных корня
обход правого поддерева
Для рекурсивной структуры удобно
применять рекурсивную обработку!
!

Двоичная кучаДвоичная кучаСтруктура данных для хранения двоичной кучи21

21 слайд Двоичная куча
Двоичная куча
Структура данных для хранения двоичной кучи
21

Двоичная кучаДвоичная куча (пирамида) — такое двоичное дерево, для которого в.

22 слайд Двоичная куча
Двоичная куча (пирамида) — такое двоичное дерево, для которого выполнены три условия:
Значение в любой вершине больше, чем значения её потомков.
Каждый лист имеет глубину (расстояние до корня) либо d либо d-1. Иными словами, если назвать слоем совокупность листьев, находящемся на определённой глубине, то все слои, кроме, может быть, последнего, заполнены полностью.
Последний слой заполняется слева направо.
Существуют также кучи, где значение в любой вершине, наоборот, меньше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap.
22

КучиMax-heap Значение в любой вершине больше, чем значения ее потомков.

23 слайд Кучи
Max-heap

Значение в любой вершине больше, чем значения ее потомков

Значение в любой вершине меньше, чем значения ее потомков
23

Красно-чёрное дерево24

24 слайд Красно-чёрное дерево
24

Красно-чёрное деревоКрасно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно.

25 слайд Красно-чёрное дерево
Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла.
Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Красно-чёрное дерево обладает следующими свойствами:
Все листья черные.
Все потомки красных узлов черные (т.е. запрещена ситуация с двумя красными узлами подряд).
На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково. Это число называется чёрной высотой дерева.

При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных.
25

АВЛ-деревоАВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для.

26 слайд АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962
26

B-деревоB-дерево (по-русски произносится как Б-дерево) — структура данных, де.

27 слайд B-дерево
B-дерево (по-русски произносится как Б-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.
Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же.
Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.
С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.

Пример B-дерева степени 2

28 слайд Пример B-дерева степени 2

2-3-дерево2-3 дерево — структура данных являющаяся B-деревом степени 1, стран.

29 слайд 2-3-дерево
2-3 дерево — структура данных являющаяся B-деревом степени 1, страницы которого могут содержать только 2-вершины (вершины с одним полем и 2-мя детьми) и 3-вершины (вершины с 2-мя полями и 3-мя детьми).
Листовые вершины являются исключением — у них нет детей (но может быть одно или два поля). 2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.

30Разбор арифметических выраженийab++1-/cda b + c d + 1 - /Как вычислять авто.

30 слайд 30
Разбор арифметических выражений
a
b
+
+
1

/
c
d
a b + c d + 1 — /
Как вычислять автоматически:
Инфиксная запись, обход ЛКП
(знак операции между операндами)
(a + b) / (c + d – 1)
необходимы скобки!
Постфиксная запись, ЛПК (знак операции после операндов)
a + b / c + d – 1
польская нотация,
Jan Łukasiewicz (1920)
скобки не нужны, можно однозначно вычислить!
Префиксная запись, КЛП (знак операции до операндов)
/ + a b — + c d 1
обратная польская нотация,
F. L. Bauer and E. W. Dijkstra

31Вычисление выраженийПостфиксная форма:a b + c d + 1 - / Алгорит.

31 слайд 31
Вычисление выражений
Постфиксная форма:
a b + c d + 1 — /
Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.
X =

32Вычисление выраженийЗадача: в символьной строке записано правильное арифмет.

32 слайд 32
Вычисление выражений
Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение.
Алгоритм:
ввести строку;
построить дерево;
вычислить выражение по дереву.
Ограничения:
ошибки не обрабатываем;
многозначные числа не разрешены;
дробные числа не разрешены;
скобки не разрешены.

33Построение дереваАлгоритм: если first=last (остался один символ – число), т.

33 слайд 33
Построение дерева
Алгоритм:
если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе.
среди элементов от first до last включительно найти последнюю операцию (элемент с номером k);
создать новый узел (корень) и записать в него знак операции;
рекурсивно применить этот алгоритм два раза:
построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1;
построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last.
first
last
k
k+1
k-1

34Как найти последнюю операцию?Порядок выполнения операций умножение и делени.

34 слайд 34
Как найти последнюю операцию?
Порядок выполнения операций
умножение и деление;
сложение и вычитание.
Нужно искать последнюю операцию с
наименьшим приоритетом!
!
Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом:
умножение и деление (приоритет 2);
сложение и вычитание (приоритет 1).

35Приоритет операции//-------------------------------------------- // Функция.

35 слайд 35
Приоритет операции
//———————————————
// Функция Priority – приоритет операции
// Вход: символ операции
// Выход: приоритет или 100, если не операция
//———————————————
int Priority ( char c )
switch ( c ) case ‘+’: case ‘-‘:
return 1;
case ‘*’: case ‘/’:
return 2;
>
return 100;
>
сложение и вычитание: приоритет 1
умножение и деление: приоритет 2
это вообще не операция

36Номер последней операции//-------------------------------------------- // Ф.

36 слайд 36
Номер последней операции
//———————————————
// Функция LastOperation – номер последней операции
// Вход: строка, номера первого и последнего
// символов рассматриваемой части
// Выход: номер символа — последней операции
//———————————————
int LastOperation ( char Expr[], int first, int last )
int MinPrt, i, k, prt;
MinPrt = 100;
for( i = first; i <= last; i++ ) prt = Priority ( Expr[i] );
if ( prt <= MinPrt ) MinPrt = prt;
k = i;
>
>
return k;
>
проверяем все символы
вернуть номер символа
нашли операцию с минимальным приоритетом

37Построение дереваСтруктура узлаstruct Node < char data; Node *left, *ri.

37 слайд 37
Построение дерева
Структура узла
struct Node char data;
Node *left, *right;
>;
typedef Node *PNode;
Создание узла для числа (без потомков)
PNode NumberNode ( char c )
PNode Tree = new Node;
Tree->data = c;
Tree->left = NULL;
Tree->right = NULL;
return Tree;
>
возвращает адрес созданного узла
один символ, число

38Построение дерева//-------------------------------------------- // Функция.

38 слайд 38
Построение дерева
//———————————————
// Функция MakeTree – построение дерева
// Вход: строка, номера первого и последнего
// символов рассматриваемой части
// Выход: адрес построенного дерева
//———————————————
PNode MakeTree ( char Expr[], int first, int last )
PNode Tree;
int k;
if ( first == last )
return NumberNode ( Expr[first] );
k = LastOperation ( Expr, first, last );
Tree = new Node;
Tree->data = Expr[k];
Tree->left = MakeTree ( Expr, first, k-1 );
Tree->right = MakeTree ( Expr, k+1, last );
return Tree;
>
осталось только число
новый узел: операция

39Вычисление выражения по дереву//-------------------------------------------.

39 слайд 39
Вычисление выражения по дереву
//———————————————
// Функция CalcTree – вычисление по дереву
// Вход: адрес дерева
// Выход: значение выражения
//———————————————
int CalcTree (PNode Tree)
int num1, num2;
if ( ! Tree->left ) return Tree->data — ‘0’;
num1 = CalcTree( Tree->left);
num2 = CalcTree(Tree->right);
switch ( Tree->data ) case ‘+’: return num1+num2;
case ‘-‘: return num1-num2;
case ‘*’: return num1*num2;
case ‘/’: return num1/num2;
>
return 32767;
>
вернуть число, если это лист
вычисляем операнды (поддеревья)
выполняем операцию
некорректная операция

40Основная программа//-------------------------------------------- // Основна.

40 слайд 40
Основная программа
//———————————————
// Основная программа: ввод и вычисление
// выражения с помощью дерева
//———————————————
void main()
char s[80];
PNode Tree;
printf ( «Введите выражение > » );
gets(s);
Tree = MakeTree ( s, 0, strlen(s)-1 );
printf ( «= %d \n», CalcTree ( Tree ) );
getch();
>

41Дерево игрыЗадача. Перед двумя игроками лежат две кучки камней, в первой и.

41 слайд 41
Дерево игры
Задача.
Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней.
Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу.
Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16.
Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

42Дерево игры3, 2игрок 13, 627, 23, 183, 34, 212, 24, 65, 24, 39, 34, 336, 24.

42 слайд 42
Дерево игры
3, 2
игрок 1
3, 6
27, 2
3, 18
3, 3
4, 2
12, 2
4, 6
5, 2
4, 3
9, 3
4, 3
36, 2
4, 18
15, 2
12, 2
4, 6
5, 3
4, 4
36, 2
12, 6
15, 3
12, 4
27, 3
При правильной игре выиграет игрок 2!
!
игрок 1
игрок 2
игрок 2
9, 2
4, 3
4, 3
ключевой ход
выиграл игрок 1

Рабочие листы
к вашим урокам

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *