Описать логическую функцию equal(T1, T2), проверяющую на равенство деревья Т1 и Т2 (рекурсивно и итеративно) - C (СИ)
Формулировка задачи:
Рекурсивно и не рекурсивно описать логическую функцию equal (T1,T2), проверяющую на равенство деревья Т1 и Т2.
Решение задачи: «Описать логическую функцию equal(T1, T2), проверяющую на равенство деревья Т1 и Т2 (рекурсивно и итеративно)»
textual
Листинг программы
#include <stdio.h>
#include <malloc.h>
struct Node
{
int Value;
Node *Left;
Node *Right;
};
/* ÏîñòðîåГ*ГЁГҐ ïðîñòîãî äåðåâГ* ïîèñêГ* */
/* ГЎГҐГ§ ГЎГ*Г«Г*Г*ñèðîâêè */
Node *BuildTree(int *Arr, int n)
{
Node *Root,*Curr,*Prev;
int i,w,f;
Root=(Node *) calloc(1,sizeof(Node));
Root->Value=Arr[0];
Root->Right=NULL;
Root->Left=NULL;
for (i=1; i<n; i++)
{
w=Arr[i];
Curr=Root;
while (1)
{
if (Curr==NULL)
{
Curr=(Node *) calloc(1,sizeof(Node));
Curr->Value=w;
if (f==1)
Prev->Right=Curr;
else
Prev->Left=Curr;
break;
}
if (Curr->Value > w)
{
Prev=Curr;
Curr=Curr->Right;
f=1;
}
else
{
Prev=Curr;
Curr=Curr->Left;
f=-1;
}
}
}
return Root;
}
/* ГЏГҐГ·Г*ГІГј äåðåâГ* Гў Ëèñï-ïîäîáГ*îì âèäå */
void PrintTree(Node *N)
{
if (N==NULL)
printf(" NULL ");
else
{
printf("(");
PrintTree(N->Left);
printf(" %d ",N->Value);
PrintTree(N->Right);
printf(")");
}
}
/* ÓäГ*ëåГ*ГЁГҐ äåðåâГ* */
void DelTree(Node *N)
{
Node *L,*R;
L=N->Left;
R=N->Right;
free(N);
if (L != NULL) DelTree(L);
if (R != NULL) DelTree(R);
}
/* ÑðГ*ГўГ*ГҐГ*ГЁГҐ äåðåâüåâ */
int CompTree(Node *N1, Node *N2)
{
if ((N1==NULL) && (N2==NULL)) return 1;
if ((N1==NULL) && (N2!=NULL)) return 0;
if ((N1!=NULL) && (N2==NULL)) return 0;
if (N1->Value == N2->Value)
return CompTree(N1->Left,N2->Left) && CompTree(N1->Right,N2->Right);
else
return 0;
}
int main(int argc, char* argv[])
{
int A[10]={0,6,1,5,-4,11,7,-1,3,-7};
int B[10]={0,6,1,5,-4,11,7,-1,3,-7};
int C[10]={11,9,-1,5,-4,11,7,-12,3,-7};
Node *r1,*r2,*r3;
r1=BuildTree(A,10);
r2=BuildTree(B,10);
r3=BuildTree(C,10);
printf("Tree: \n");
PrintTree(r1);
printf("\nand:\n");
PrintTree(r2);
printf("\n");
(CompTree(r1,r2))?printf("are equal!\n"):printf("are not equal!\n");
printf("Tree: \n");
PrintTree(r1);
printf("\nand:\n");
PrintTree(r3);
printf("\n");
(CompTree(r1,r3))?printf("are equal!\n"):printf("are not equal!\n");
DelTree(r1);
DelTree(r2);
DelTree(r3);
printf("\n");
return 0;
}
Объяснение кода листинга программы
- Структура данных, используемая в коде - это двоичное дерево, представленное через структуру Node.
- Функция BuildTree() создает и заполняет двоичное дерево на основе массива.
- Функция PrintTree() выводит представление двоичного дерева в виде текста.
- Функция DelTree() освобождает память, выделенную под узлы дерева.
- Функция CompTree() сравнивает два двоичных дерева на равенство.
- В функции main() создаются три массива, из которых затем строятся три разных двоичных дерева.
- Затем эти деревья выводятся на экран и сравниваются между собой.
- Если деревья равны, выводится сообщение
are equal!. В противном случае выводится сообщениеare not equal!. - После сравнения деревья удаляются с помощью функции DelTree().
- В конце программы выводится пустая строка. Примечание: данный код реализует сравнение деревьев по их значениям, а не по структуре. Поэтому порядок обхода дерева в функциях PrintTree() и CompTree() может быть различным.