Слайд 2
![Основные определения Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-1.jpg)
Основные определения
Дерево – структура данных, представляющая собой древовидную структуру в виде
набора связанных узлов.
Слайд 3
![Бинарное дерево](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-2.jpg)
Слайд 4
![Обход бинарного дерева прямой; (префиксный) (ABC) симметричный;(BAC) (Инфиксный) обратный (постфиксный (BCA)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-3.jpg)
Обход бинарного дерева
прямой; (префиксный) (ABC)
симметричный;(BAC) (Инфиксный)
обратный (постфиксный (BCA)
Слайд 5
![Реализация бинарного дерева struct tnode { int field; // поле](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-4.jpg)
Реализация бинарного дерева
struct tnode {
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; //правый потомок
};
Добавление узлов в дерево
struct tnode * addnode(int x, tnode *tree) {
if (tree == NULL) { // Если дерева нет, то формируем корень
tree =new tnode; // выделяем память под узел
tree->field = x; // поле данных
tree->left = NULL;
tree->right = NULL; // ветви инициализируем пустотой
}
else if (x < tree->field) // условие добавления левого потомка
tree->left = addnode(x,tree->left);
else // условие добавления правого потомка
tree->right = addnode(x,tree->right);
return(tree);
}
Слайд 6
![Реализация прямого обхода дерева void treeprint(tnode *tree) { if (tree!=NULL)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-5.jpg)
Реализация прямого обхода дерева
void treeprint(tnode *tree) {
if (tree!=NULL) { //Пока
не встретится пустой узел
cout << tree->field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
}
}
Слайд 7
![Реализация симметричного обхода дерева void treeprint(tnode *tree) { if (tree!=NULL)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-6.jpg)
Реализация симметричного обхода дерева
void treeprint(tnode *tree) {
if (tree!=NULL) { //Пока не встретится
пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout << tree->field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
}
}
Слайд 8
![Реализация обратного обхода дерева void treeprint(tnode *tree) { if (tree!=NULL)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-7.jpg)
Реализация обратного обхода дерева
void treeprint(tnode *tree) {
if (tree!=NULL) { //Пока не встретится
пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout << tree->field; //Отображаем корень дерева
}
}
Слайд 9
![Бинарная куча Бинарная куча - это бинарное дерево, для которого](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-8.jpg)
Бинарная куча
Бинарная куча - это бинарное дерево, для которого выполняется основное свойство
кучи: приоритет (значение) каждой вершины больше приоритет
ов(значений) её потомков.
Слайд 10
![Добавление элемента в кучу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/597108/slide-9.jpg)
Добавление элемента в кучу