Описать логическую функцию 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;
}

Объяснение кода листинга программы

  1. Структура данных, используемая в коде - это двоичное дерево, представленное через структуру Node.
  2. Функция BuildTree() создает и заполняет двоичное дерево на основе массива.
  3. Функция PrintTree() выводит представление двоичного дерева в виде текста.
  4. Функция DelTree() освобождает память, выделенную под узлы дерева.
  5. Функция CompTree() сравнивает два двоичных дерева на равенство.
  6. В функции main() создаются три массива, из которых затем строятся три разных двоичных дерева.
  7. Затем эти деревья выводятся на экран и сравниваются между собой.
  8. Если деревья равны, выводится сообщение are equal!. В противном случае выводится сообщение are not equal!.
  9. После сравнения деревья удаляются с помощью функции DelTree().
  10. В конце программы выводится пустая строка. Примечание: данный код реализует сравнение деревьев по их значениям, а не по структуре. Поэтому порядок обхода дерева в функциях PrintTree() и CompTree() может быть различным.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.154 из 5
Похожие ответы