16.Операции поиска и удаления в бинарном дереве.

1)Пусть ключевое поле — поле mf и мы рассмотрим дерево поиска:

Функция осуществляет поиск заданного элемента в дереве и если его не находит, то добавляет его в качестве листа.

Void Search (int x,tnode*&t){if(!t)/*такого эл-та нет, включаем его*/ {t=new tnode;

t->inf=x; t->left=NULL; t->right=NULL;}; else if(x<t->inf)search(x,t->left);

else if(x>t->inf) search(x,t->right); else(cout<<t->inf;}};

Эту функцию можно использовать для построения бинарного упорядоченного дерева,

вводя номер вершины с клавиатуры:

r=NULL; cin>>x; while(x!=0){Search(x,r); cout<<”vvedite№vershiny”<<endl;

cin>>x; cout<<endl;};

2)Удаление из упорядоченного дерева:

tnode*q;void Del_node(inf x;tnode*&t){if(t==NULL) {cout<<”такого узла нет”<<endl;};

else if(x<t->inf) Del_node(x,t->left); else if(x>t->inf) Del_node(x,t->right); else{ q=t;

if(q->left==NULL)t=q->right; else if(q->right==NULL)t=q->left; else Del_vs(q->left);

delete q;};};

17.Понятие графа, представление графа в эвм.

Граф G=(V,E) состоит из конечного множества вершин V и множества ребер E. Если ребра соединяют неупорядоченные пары вершин,т.е. E э {(x,y)|x,y э V&x!=y} то граф- неориентированный. Ребро(x,y).

Если ребра — направленные отрезки,то граф — ориентированный,ребра дуги,т.е множество ребер Е э VxV – множество упорядоченных пар вершин(<x,y,x-начало,

y-конец)

Если в графе G(V,E) ребро (u,v) или дуга <u,v> э E , то вершины u и v - смежные, а ребро(дуга) (u,v) - инцидентное вершинам u и v .

Для любой вершины оператора определяется кол-во дуг , исходящих из данной вершины(полустепень исхода) и входящих в неё(полустепень захода). Сумма полустепеней определяет степень вершин в орграфе. Вершина нулевой степени - изолированная.

Путь - последовательность рёбер вида (V0 , V1) ( V1 , V2)...(Vk-1, Vk) или последовательность вершин V0....Vk : V0 - начало , Vk - конец и k - длина пути.

Длина пути - сумма длин дуг , входящих в путь или их кол-во.

Путь простой, если все входящие в него вершины, кроме 1 и последней различны и путь 3амкнутый, если V0=Vk. Граф связный, если для любой пары вершин существует соединяющий их путь. Представление графа:

1) матрица инцидентности - размерности( n x m ,n- кол-во вершин, m - рёбер)

если U - откуда исходит, то в строку (-1) и (1) куда входит стрелка.

const int n= , m= ; int Matr_in [n][m]; матрица смежности где n- кол-во вершин, и aij = 1 , если существует ребро ( i,j) , иначе 0. Вершина : struct tgraf {int k; tgraf*left; Tnode*right;}; left - ука3атель на след. вершину right - на список вершин , смежной с k - oй . Struct tnode { int k; nexy*tnode;};

18.Представление графа списком инцидентности,алгоритм обхода графа в глубину.

Список смежности содержит для каждой вершины список вершин,смежных с ней.

Т.о. Для n-вершинного графа список смежности состоит из линейных связных списков,адрес и начало каждого списка хранятся в спец.массиве a[i] его элемент содержащий указатель на начало связного списка, содержащего смежные с i-ой вершины. Nach [1]->|2| |->|3| |; Nach [2]=NULL; Nach[3]=|2| |->|4|

| Представление списком смежности снимает ограничение на количество рёбер.

Обход в глубины: алгоритм: начинаем обход с произвольной вершины V0. 3атем выбираем любую вершину U , смежную с V0 и повторяем рекурсивно процесс от вершины U. В общем случае, находясь в некоторой вершине V , просматриваем, есть ли у неё не пройденные смежные вершины . Если есть , просматриваем её, полагая не новой, и продолжаем обход в глубину, если нет, полагаем её использованной и возвращаемся на шаг к вершине, из которой мы попали в V. Так до тех пор , пока не вернёмся в V0 и у нас уже не будет непройденных вершин.