Duas ABBs são IGUAIS se são ambas vazias ou então se armazenam valores iguais em suas raizes, suas subárvores esquerdas são iguais, e suas subárvores direitas são iguais. Implemente a função que verifica se duas árvores são simlares.
Passo 1
Vamos começar entendendo o que o exercício pede: verificar se duas árvores binárias de busca (ABB) são iguais seguindo o critério de recursão estrutural.
Passo 2
Identificar os casos base da recursão: (1) Se as duas árvores forem vazias, são iguais; (2) Se exatamente uma for vazia, são diferentes.
Passo 3
Para o caso recursivo, quando ambas as árvores não são vazias, comparamos o valor armazenado na raiz e chamamos a mesma função para as subárvores esquerda e direita.
Passo 4
Agora que temos o raciocínio, implementamos a função recursiva em C conforme o fluxo definido: verificar nulos, comparar valor da raiz e descer recursivamente.
Resposta
#include <stdbool.h>
typedef struct ABB {
int info;
struct ABB *esq;
struct ABB *dir;
} ABB;
int info;
struct ABB *esq;
struct ABB *dir;
} ABB;
bool iguais(ABB *a, ABB *b) {
// Caso base 1: ambas vazias
if (a == NULL && b == NULL)
return true;
// Caso base 2: uma vazia, outra não
if (a == NULL || b == NULL)
return false;
// Se as raízes diferem, não são iguais
if (a->info != b->info)
return false;
// Caso recursivo: comparar subárvores esquerda e direita
return iguais(a->esq, b->esq) && iguais(a->dir, b->dir);
}
// Caso base 1: ambas vazias
if (a == NULL && b == NULL)
return true;
// Caso base 2: uma vazia, outra não
if (a == NULL || b == NULL)
return false;
// Se as raízes diferem, não são iguais
if (a->info != b->info)
return false;
// Caso recursivo: comparar subárvores esquerda e direita
return iguais(a->esq, b->esq) && iguais(a->dir, b->dir);
}