Escreva um programa para copiar uma árvore binária.
Passo 1
O enunciado pede que a gente escreva um programa que, dada a raiz de uma árvore binária, construa uma cópia independente dessa árvore. O conteúdo envolvido é estrutura de dados (árvore binária) e recursão.
Passo 2
Primeiro, precisamos definir a estrutura de nó da árvore. Cada nó guarda um valor (por exemplo, um inteiro) e ponteiros para os filhos esquerdo e direito.
O algoritmo de cópia usa recursão: se o nó atual for NULL, retornamos NULL; caso contrário, alocamos um novo nó, copiamos o valor e chamamos recursivamente a função para os filhos esquerdo e direito.
O algoritmo de cópia usa recursão: se o nó atual for NULL, retornamos NULL; caso contrário, alocamos um novo nó, copiamos o valor e chamamos recursivamente a função para os filhos esquerdo e direito.
Passo 3
Depois de implementar a função de cópia, basta invocá-la passando a raiz da árvore original para obter a raiz da cópia.
Passo 4
Por fim, é importante liberar a memória de ambas as árvores quando não forem mais necessárias para evitar vazamento de memória.
Resposta
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
// Definição do nó da árvore binária
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Função para criar um novo nó
Node* createNode(int value) {
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) {
fprintf(stderr, “Erro ao alocar memória!\n”);
exit(EXIT_FAILURE);
}
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
Node* createNode(int value) {
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) {
fprintf(stderr, “Erro ao alocar memória!\n”);
exit(EXIT_FAILURE);
}
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
// Função recursiva para copiar a árvore
Node* copyTree(Node* root) {
if (root == NULL) {
return NULL;
}
// Cria o nó atual
Node* newRoot = createNode(root->data);
// Copia recursivamente subárvores
newRoot->left = copyTree(root->left);
newRoot->right = copyTree(root->right);
return newRoot;
}
Node* copyTree(Node* root) {
if (root == NULL) {
return NULL;
}
// Cria o nó atual
Node* newRoot = createNode(root->data);
// Copia recursivamente subárvores
newRoot->left = copyTree(root->left);
newRoot->right = copyTree(root->right);
return newRoot;
}
// Função auxiliar para liberar memória da árvore
typedef void (FreeFunc)(Node);
void freeTree(Node* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
typedef void (FreeFunc)(Node);
void freeTree(Node* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
// Exemplo de uso
int main() {
// Monta uma árvore de exemplo
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
int main() {
// Monta uma árvore de exemplo
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// Copia a árvore
Node* copy = copyTree(root);
// Aqui você poderia imprimir ou testar a cópia...
// Libera memória
freeTree(root);
freeTree(copy);
return 0;
}