- •1. Функциональные структуры данных.
- •2.Рекурсивные структуры данных.
- •3.Теоретико-множественные структуры данных.
- •4.Абстрактные типы данных.
- •5.Атд «Список»: основные понятия, типы.
- •6.Линейные списки. Описать алгоритм и написать пример функции создания списка.
- •7.Линейные списки. Описать алгоритм и написать пример функции включения нового элемента в список.
- •8.Линейные списки. Описать алгоритм и написать пример функции исключения элемента из списка.
- •9.Линейные списки. Описать алгоритм и написать пример функции поиска элемента в списке.
- •10.Понятие «очередь».
- •11.Понятие «стек».
- •12.Понятие «дек».
- •13.Обратная польская запись: алгоритм ее составления.
- •15.Двусвязные списки и их свойства.
- •16.Иерархические списки и их свойства.
- •17.Ассоциативные списки и их свойства.
- •18. Атд «Дерево»: основные понятия.
- •19.Двоичные деревья и их свойства.
- •20.Деревья двоичного поиска. Описать алгоритм и написать пример функции добавления узла в дерево.
- •21.Деревья двоичного поиска. Описать алгоритм и написать пример функции обхода узлов дерева.
- •22.Деревья двоичного поиска. Описать алгоритм и написать пример функции поиска узла по его метке.
- •23.Деревья двоичного поиска. Описать алгоритм и написать пример функции удаления узла дерева.
21.Деревья двоичного поиска. Описать алгоритм и написать пример функции обхода узлов дерева.
Существует три способа обхода
Симметричный (левый сын, корень, правый сын - ЛКП)
void inOrder(TREENODE* tree)
{
if(tree!=NULL)
{
inOrder(tree->left);
printf("%3d ",tree->data);
inOrder(tree->right);
}
}
Прямой (корень, левый сын, правый сын - КЛП)
void preOrder(TREENODE* tree)
{
if(tree!=NULL)
{
printf("%3d ",tree->data);
preOrder(tree->left);
preOrder(tree->right);
}
}
Обратный (левый сын, правый сын, корень - КПЛ)
void postOrder(TREENODE* tree)
{
if(tree!=NULL)
{
postOrder(tree->left);
postOrder(tree->right);
printf("%3d ",tree->data);
}
}
22.Деревья двоичного поиска. Описать алгоритм и написать пример функции поиска узла по его метке.
Алгоритм поиска узла в ДДП строится на последовательном сравнении искомой метки с метками узлов, начиная с корня. Если искомая метка меньше, чем метка корня, то сравнение выполняется в таком же порядке с метками узлов его левого поддерева, если больше, то - с метками узлов его правого поддерева. Сравнение выполняется до тех пор, пока метка очередного узла не совпадет с искомой меткой или при необходимости перехода к левому или правому сыну соответствующая ссылка окажется равной NULL, что означает, что в дереве нет узла с указанной меткой.
TREENODE* searchNode(TREENODE* tree, int value)
{
TREENODE* q=tree;/*указатель на текущий узел*/
/*цикл поиска узла*/
while(q!=NULL)
{
if(q->data==value)
break;/*нашли узел и выходим из цикла*/
else
{
if(value<q->data)/*если число меньше, нужно двигаться влево*/
q=q->left;
else /*если число больше, нужно двигаться вправо*/
q=q->right;
}
}
/*вышли из цикла поиска элемента*/
if(q==NULL)
{
puts("Not founded!");
return NULL; /*узел не найден */
}
puts("Founded!");
return q;/*узел найден */
}
23.Деревья двоичного поиска. Описать алгоритм и написать пример функции удаления узла дерева.
Последовательность действий при выполнении операции удаления узла из ДДП зависит от того, сколько сыновей имеет удаляемый узел:
1.если удаляемый узел является листом, то для его удаления достаточно обнулить соответствующую ссылку его предка;
2.если удаляемый узел имеет единственного сына, то последний должен его заменить;
3.если удаляемый узел имеет двух сыновей, то его следует заменить узлом с подходящей меткой, причем у последнего должно быть не более одного сын.