25.4 Дан файл символов сформировать дерево поиска описав процедуру удаления элнмента из дерева и функцию подсчета листьев в дереве.

//подключение внешних модулей

#include "stdio.h"

#include "string.h"

#include "iostream.h"

#include "Windows.h"

#include "io.h"

#include "fcntl.h"

#include <sys/stat.h>

struct list{//структура Эл-та дерева

char el;

int count;

list *nextl,*nextr;

};

void del_next(list ** node)

{//удаляет все поддеревья указанного корня

if((*node)->nextl!=NULL)//усли не пусто применяем проц удаления наследников

del_next(&(*node)->nextl);

if((*node)->nextr!=NULL)

del_next(&(*node)->nextr);

delete *node;//удаляем родителя

}

void search_el(char el, list ** node)//ищем элемент для удаления

{

if((*node)->el==el){//если это искомый элемент удаляем

if((*node)->nextl!=NULL)

del_next(&(*node)->nextl);

if((*node)->nextr!=NULL)

del_next(&(*node)->nextr);

delete *node;

}else{

if((*node)->nextl!=NULL)search_el(el,&(*node)->nextl);

if((*node)->nextr!=NULL)search_el(el,&(*node)->nextr);

}

}

int get_list_count(list * node)

//процедура считающая количество листьев в дереве

{

if((node->nextl==NULL)&&(node->nextr==NULL))

return 1;//если нет наследников не то это лист

else

{//иначе считаем листья у наследников

int lc,rc;

lc = rc =0;

if(node->nextl!=NULL) lc = get_list_count(node->nextl);

if(node->nextr!=NULL) rc = get_list_count(node->nextr);

return(lc+rc);//возвращаем общее их количество

}

}

void insert_el(char el, list ** node)//вставка елемента в дерево

{

if(*node == NULL)

{//создаем новый элемент

*node = new list;

(*node)->el = el;

(*node)->nextl = NULL;

(*node)->nextr = NULL;

(*node)->count = 1;

}else

if(el == (*node)->el){

(*node)->count++;

}else

{

if(el>(*node)->el) insert_el(el,&(* node)->nextr); else

insert_el(el,&(* node)->nextl);

}

}

int fh;//переменная заголовка файла

void main()//the main function

{

fh = -1;//file handle

list *fst,*tek;

fst = NULL;//создаем переменную корня дерева

fh = _open( "tmp1.file", _O_WRONLY|_O_CREAT );

//открываем файл для записи

printf("vvedite simvol i = ");

char i;

scanf("%c",&i);

do{

int j = _write(fh,&i,sizeof(char));//заполняем файл

if(j<=0) printf("error write");

printf("Vvedite simvol(konechnii element - !) i = ");

cin>>i;//читаем входной поток

}while(i!='!');

_close(fh);//close file

fh = _open( "tmp1.file",_O_RDONLY );

//открываем файл для чтения

bool is_first = true;//

while(!_eof(fh))

{

_read(fh,&i,sizeof(char));

insert_el(i,&fst);//строим бинарное дерево

}// end of tree construction

insert_el('a',&fst);//вставляем элемент для удаления

printf("list coint - %d",get_list_count(fst));//output string

search_el('a',&fst);//находим и удаляем элемент

}

25.5 R(A,B,C,D,E,F)

CD->A

CD->B

D->E

D->F

R1(C,D,A)

R2(C,D,B)

R3(D,E)

R4(D,F)

R1(C,D,A,B)

R2(D,E,F)

	A	B	C	D	E	F
R1	a1	a1	a1	a1	b15	b16
R2	b21	b22	b23	a2	a2	a2
	A	B	C	D	E	F
R1	a1	a1	a1	a1	a1	a1
R2	b21	b22	b23	a2	a2	a2

Select distinct R1.A,R1.B,R1.C

From R1,R2

Where R1.D<0 And R2.E=R2.F And R1.D=R2.D