Árvores e grafos em C

Árvores e grafos são estruturas de dados não lineares usadas para representar dados hierárquicos e de redes.

Nesta lição, você aprenderá:

• Como as árvores e os grafos são estruturados.
• Como implementar uma árvore binária em C.
• Como representar grafos usando listas e matrizes de adjacência.

O que é uma árvore?

Uma árvore é uma estrutura de dados hierárquica composta por nós.

Termos importantes:

• Raiz - O nó superior.
• Pai e filho - Nós conectados diretamente.
• Folha - Um nó sem filhos.

Exemplo: nó de árvore binária

Em C, um nó de árvore binária é definido usando uma struct com ponteiros para os filhos esquerdo e direito.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Travessia de árvore binária

Métodos de travessia:

• Inorder (LNR) - Esquerda, Node, direita.
• Preorder (NLR) - Node, esquerda, direita.
• Postorder (LRN) - Esquerda, direita, Node.

Exemplo: travessia Inorder

Este programa realiza uma travessia Inorder de uma árvore binária.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

O que é um grafo?

Um grafo é uma coleção de nós (vértices) conectados por arestas.

Os grafos podem ser:

• Direcionados - As arestas têm uma direção.
• Não direcionados - As arestas não têm direção.

Representação de grafos

Os grafos podem ser representados usando:

• Matriz de adjacência - Um vetor bidimensional que representa as conexões.
• Lista de adjacência - Uma lista em que cada nó aponta para seus vizinhos.

Travessia de grafos

Métodos comuns de travessia:

• Busca em largura (BFS) - Visita todos os vizinhos antes de avançar para níveis mais profundos.
• Busca em profundidade (DFS) - Explora o máximo possível em profundidade antes de retroceder.

Resumo

Nesta lição, você aprendeu:

• Como as árvores e os grafos são estruturados.
• Como realizar travessias em árvores.
• Como os grafos são representados e percorridos.

Esta é a conclusão da seção Estruturas de Dados em C!