Добре дошли!

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

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

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

Последователи

12 май 201115 г.

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

Редактирано 12 май 201115 г. от cecko0 (преглед на промените)

12 май 201115 г.

Започни и като срещнеш трудност питай защо се получава така и как може да се оправи....

16 май 201115 г.

Автор

Измислих следния алгоритъм: записвам двете дървета, след това ги подреждам в прав ред (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";
}