Описать логическую функцию 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() может быть различным.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д