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

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

Идеально сбалансированное – такое, что для любого узла верно, что количество узлов в левом поддереве отличается от количества узлов в правом поддереве не больше чем на единицу.

Построение: Пусть информационной частью будут номера вершин, вводимых с клавиатуры. Рекурсивный алгоритм. 1) Взять 1 узел в качестве корня. 2) построить левое поддерево состоящее из nl = n/2 узлов тем же способом. 3) Построить правое поддерево состоящее из nr=n-nl-1 узлов.

1. Не возвращающая.

Void Tree(tnode *&t, int n)

{tnode *r; int nr, nl, x;

If (n==0) t=NULL;

Else {nl=n/2; nr=n-nl-1;

Cout<<”Введите номер вершины”<<endl; cin>>x;

r=new tnode; r->inf=x;

Tree(n->left, nl); Tree(n->right, nr);};};

2. Возвращающая.

Tnode *Tree(int n)

{tnode *r; int nl, nr, x;

If (n==0) return 0;

Else {nl=n/2; nr=n-nl-1; cout<<nl<<nr;

Cout<<”введите номер вершины”;cin>>x;

r=new tnode; r->inf=x;

r->left=Tree(nl); r->right=Tree(nr); return r;};};

Обходы бинарного дерева: 1) Прямой (Сверху вниз). 2) Симметричный (слева направо). 3) Обратный (Снизу вверх).

1. Void Preorder(tnode *t)

{If (t!=NULL) {cout<<t->inf<<’t’;

Preorder(t->left);

Rteorder(t->right);};};

2. Void Inorder(tnode *t)

{if (t!=NULL)

{Inorder(t->left);

Cout<<t->inf<<’\t’;

Inorder(t->right);};};

3. Void Postorder(tnode *t)

{if(t!=NULL)

{Postorder(t->left);

Postorder(t->right);

Cout<<t->inf<<’\t’;};};

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

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

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

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;}}; \\ обработка найденного у3ла

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

r=NULL ; cout<<x;

while (x!=0) {

Search(x,r);

cout<<"введите номер вершины"<<endl;

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

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

tnode*q;

void Del_node (inf x; tnode *&t){

if(t==NULL)

{ cout<< "такого у3ла нет" <<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;};

};

void Del_vs( tnode *&r){

if(r-> right!=NULL) Del_vs( r->right);

else{ q->inf=r->inf;

q=r; r=r->left;};

В функции Del_node 1я ветвь оператора if выводит сообщение , что данного элемента нет, 2я и 3я осуществляют спуск по дереву до у3лаЮ который надо удалить. Когда он найден вводится вспомогательная переменная и осуществляется проверка на кол-во потомков удаляемого у3ла. Если он найден , вводится вспомогательная переменная и осуществляется проверка на кол-во потомков, удаляемого у3ла.

Если потомок 1 , то работает 1 и3 след. строк, после присваивания q=t , а если 2 то обращаемся к вспомогательной переменной ф-и Del_vs , которая в левом поддереве удаляемого у3ла находит самый правый у3ел, меняет 3начения информационных полей с удаляемым и во3вращается в основную , в которой освобождается память от удалённого у3ла.