17.Ассоциативные списки и их свойства.

Информационная часть состоит из нескольких ассоц. списков, которые организованы на основе одного общего или базового списка, т.к. одна и та же запись может входить в несколько списков одновременно.

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

Таким образом информ. сеть может быть задана на базе двууровнего иерархического списка.

Головные элементы удобно представлять в виде элементов спец. созданного для этого списка.

18. Атд «Дерево»: основные понятия.

- совокупность элементов или узлов между которыми установлены иерархические отношения типа «отец – сын». Каждый элемент может иметь несколько потомков и только одного предка (кроме корня дерева – нет предка).

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

Каждый элемент и потомок, и предок для самого себя.

Узел – дерево. Дерево без узлов – пустое нулевое дерево.

Лист – узел не имеющий истинных потомков.

Длина пути – число на 1 меньше кол-ва узлов в пути.

Высота дерева – высота корня.

Высота узла – длина самого длинного пути из этого узла до какого-либо листа дерева.

Глубина узла – длина от корня до этого узла.

Неупорядоченное дерево – дерево в котором произвольный порядок следования потомков узлов.

Упорядоченное дерево – дерево с определенным порядком следования потомков одного узла.

Каждый узел можно сопоставлять с значением – метка узла.

Поддерево – любой элемент в дереве со всеми своими потомками.

19.Двоичные деревья и их свойства.

- дерево у которого любой узел имеет на более двух прямых потомков, назыв. левым и правым сыном.

Строго двоичное дерево – дерево, у которого каждая внутренняя вершина имеет не пустые правые и левые поддерева.

Полное двоичное дерево – все листья на одном уровне и каждая внутренняя вершина имеет не пустые правые и левые поддеревья.

20.Деревья двоичного поиска. Описать алгоритм и написать пример функции добавления узла в дерево.

ДДП – это двоичные деревья, обладающие следующими свойствами:

• Для меток узлов определено отношение порядка больше/меньше

• Метки всех узлов уникальны

• Метка любого узла (кроме листьев) больше метки любого его потомка из левого поддерева, но меньше метки любого потомка из правого поддерева.

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

TREENODE* insertNode(TREENODE* tree, int value)

{

TREENODE* newNode=(TREENODE*)malloc(sizeof(TREENODE));

TREENODE* root=tree;

if(newNode!=NULL)

{

/*создали узел дерева*/

newNode->data=value;

newNode->left=NULL;

newNode->right=NULL;

}

else

{

puts("Error!");

}

if(root==NULL) /*пустое дерево*/

return newNode;/*новый узел становиться корнем дерева*/

while(root!=NULL)

{

/*вставка в дерево*/

if(value<root->data)

{ /*если число меньше, нужно двигаться влево*/

if(root->left!=NULL)

root=root->left;

else

{

root->left=newNode;

break;

}

}

else if(value>root->data)

{

/*если число больше, нужно двигаться вправо*/

if(root->right!=NULL)

root=root->right;

else

{

root->right=newNode;

break;

}

}

else

{

puts("Clone");

break;

}

}

return tree;

}