Премини към съдържанието
  • Добре дошли!

    Добре дошли в нашите форуми, пълни с полезна информация. Имате проблем с компютъра или телефона си? Публикувайте нова тема и ще намерите решение на всичките си проблеми. Общувайте свободно и открийте безброй нови приятели.

    Моля, регистрирайте се за да публикувате тема и да получите пълен достъп до всички функции.

     

Помощ за алгоритъм (двоично дърво за търсене)


Препоръчан отговор

Здравейте. Трябва да напиша функция, която проверява дали едно двоично дърво се съдържа в друго двоично дърво, т.е. всички елементи от едното дърво се съдържат в другото. Благодаря.

Редактирано от cecko0 (преглед на промените)
Линк към коментара
Сподели в други сайтове

Измислих следния алгоритъм: записвам двете дървета, след това ги подреждам в прав ред (inorder) и записвам подредените стовйности в два динамични масива и сръвнявам дали вторият масив се съдържа в първия. НО ;] имам проблем при записването в масивите (програмата забива) и не мога да разбера къде бъркам!!?? помощ

#include <iostream.h>

struct elem
{
	int key;
	elem *left, *right;
}*root1=NULL, *root2=NULL;

void add(int n, elem *&t);
void check();

int i=0, y=0;
int *a1= new int[i];
int *a2= new int[y];

void main()
{
	int c;
	cout<<endl<<"Vavedete simvoli za dobavqne v TR1(i '0' zakraj): "<<endl;
	
	do{
		cin>>c;
		if(c!=0) add(c,root1);
	}while(c!=0);

	cout<<endl<<"Vavedete simvoli za dobavqne v TR2(i '0' zakraj): "<<endl;
	
	do{
		cin>>c;
		if(c!=0) add(c,root2);
	}while(c!=0);

	check();
	
}


void add(int n, elem *&t)
{
	if(t==NULL){
		t=new elem;
		t->key=n;
		t->left=NULL;
		t->right=NULL;
	}else
		if(t->key<n)
			add(n,t->right);
		else add(n,t->left);
}

void inorder1(elem *t)
{
	if(t){
		inorder1(t->left);
		a1[i++]=t->key;
		inorder1(t->right);
	}
}
void inorder2(elem *t)
{
	if(t){
		inorder2(t->left);
		a2[y++]=t->key;
		inorder2(t->right);
	}
}

void check()
{
	inorder1(root1);
	inorder2(root2);
	
	int flag=0;

	for(int x=0; x<i; x++){
		if(a1[x]==a2[0]){
			for(int q=1; q<y; q++){
				if(a1[++x]!=a2[q]){ flag=0;break;}
				else flag=1;
			}
		}
		if(flag==1) break;
		
	}
	if(flag==1) cout<<endl<<"TR2 e v TR1"; 
	else cout<<endl<<"TR2 ne e v TR1";
}
Линк към коментара
Сподели в други сайтове

Добавете отговор

Можете да публикувате отговор сега и да се регистрирате по-късно. Ако имате регистрация, влезте в профила си за да публикувате от него.

Гост
Напишете отговор в тази тема...

×   Вмъкнахте текст, който съдържа форматиране.   Премахни форматирането на текста

  Разрешени са само 75 емотикони.

×   Съдържанието от линка беше вградено автоматично.   Премахни съдържанието и покажи само линк

×   Съдържанието, което сте написали преди беше възстановено..   Изтрий всичко

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Добави ново...

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите Условия за ползване