Динамические данные разветвленной структуры

Сентябрь 5, 2022

Главная
Алгебра
Динамические данные разветвленной структуры

Содержание

2. Основные определения Дерево - это частный случай графа, между любыми двумя вершинами которого существует ровно один
3. Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья и
4. Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья
5. Определения Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок
6. Дерево двоичного поиска Дерево двоичного поиска для множества чисел S - это бинарное дерево, каждой вершине
7. Пример двоичного дерева поискадля набора чисел 7, 3, 5, 2, 8, 1, 6, 10, 9, 4,
8. Описание структуры «Дерево» struct Elem { int data; Elem * left, * right; }; typedef Elem
9. Создание новой вершины дерева PElem Create () { PElem b = new Elem; b->left = NULL
10. Создание новой вершины дерева с занесением в вершину значения PElem Create (int x) { PElem b
11. Задача 1. Построение дерева поиска I. Cоздать переменную-указатель на дерево II. Пока не достигли конца ввода:
12. Печать дерева Встать в корень дерева Вызвать алгоритм печати дерева Распечатать содержимое узла Вызвать алгоритм печати
14. Скачать презентацию

Слайд 2

Основные определения
Дерево - это частный случай графа, между любыми двумя вершинами

которого существует ровно один путь.
Ориентированное дерево - граф, в котором между любыми двумя вершинами существует не более одного пути.
Будем изучать только один вид ориентированных деревьев – корневые.

Слайд 3

Корневое дерево
- это ориентированное дерево, в котором можно выделить вершины трех

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

Слайд 4

Традиционно в математике и в родственных ей науках (в том числе

и в теоретическом программировании) деревья "растут" вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.
Дерево высоты 3

Слайд 5

Определения
Предок вершины v - это вершина, из которой исходит дуга, заходящая

в вершину v.
Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v.
В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.
Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.
Высота корневого дерева - это максимальное количество дуг, отделяющих листья от корня. (Будем считать, что корень дерева расположен на уровне 0.)

Слайд 6

Дерево двоичного поиска
Дерево двоичного поиска для множества чисел S - это

бинарное дерево, каждой вершине которого сопоставлено число из множества S, причем:
существует ровно одна вершина, содержащая любое число из множества S;
все значения вершин левого поддерева строго меньше, чем значение текущей вершины;
все значения вершин правого поддерева строго больше, чем значение текущей вершины.
Т.е. структура дерева двоичного поиска подчиняется простому правилу: "если больше - направо, если меньше - налево".

Слайд 7

Пример двоичного дерева поискадля набора чисел 7, 3, 5, 2, 8,

1, 6, 10, 9, 4, 11

Слайд 8

Описание структуры «Дерево»
struct Elem
{
int data;
Elem * left, * right;

};
typedef Elem * PElem;

Слайд 9

Создание новой вершины дерева
PElem Create ()
{
PElem b = new Elem;
b->left

= NULL ;
b->right = NULL ;
return b;
}

Слайд 10

Создание новой вершины дерева с занесением в вершину значения
PElem Create (int

x)
{
PElem b = new Elem;
b->left = NULL ;
b->right = NULL ;
b->data = x;
return b;
}

Слайд 11

Задача 1. Построение дерева поиска
I. Cоздать переменную-указатель на дерево
II. Пока не

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

Слайд 12