Estruturas de Dados: Pilhas, Filas e Árvores em C

Pilhas: Declaração em Vetor

#define tam 10
typedef struct {
    int topo;
    int el[tam]; // Lugar onde serão armazenados os dados
} pilha;

Operações com Pilhas

• Inicialização: void inicia(pilha *p) { p->topo = -1; }
• Verificar se está cheia: int cheia(pilha *p) { return (p->topo == tam - 1); }
• Verificar se está vazia: int vazia(pilha *p) { return (p->topo == -1); }
• Inserção (Push): int push(pilha *p, int val) { if (cheia(p)) return 0; p->el[++p->topo] = val; return 1; }
• Remoção (Pop): int pop(pilha *p, int *val) { if (vazia(p)) return 0; *val = p->el[p->topo--]; return 1; }

Filas: Implementação

• Inicialização: void fila_vazia(int *i, int *f) { *i = 0; *f = 0; }
• Inserção: int ins_fila(int *fila, int *inicio, int *fim, int val) { if (((*fim + 1) % tam) == *inicio) return 0; else { *fim = (*fim + 1) % tam; fila[*fim] = val; return 1; } }
• Remoção: int rem_fila(int *fila, int *inicio, int *fim, int *val) { if (*fim == *inicio) return 0; else { *inicio = (*inicio + 1) % tam; *val = fila[*inicio]; return 1; } }
• Impressão: void imprime(int *fila, int inicio, int fim) { ... }

Árvores Binárias

Uma árvore estritamente binária é aquela em que todo nó que não é folha possui sub-árvores esquerda e direita não vazias.

Árvores perfeitamente balanceadas: A sub-árvore à esquerda possui (N div 2) nós e a sub-árvore à direita possui N - (N div 2) - 1 nós.

Conceitos Fundamentais

• Raiz: Nó no topo da árvore.
• Descendentes: Nós ligados abaixo de um nó específico.
• Altura: O nível máximo da árvore.
• Folha: Nós que não possuem descendentes.
• Grau: Número de descendentes diretos.

Percursos em Árvores

• PreOrder: Raiz, Esquerda, Direita.
• InOrder: Esquerda, Raiz, Direita.
• PosOrder: Esquerda, Direita, Raiz.

Implementação dos Percursos

void Pre_Ordem(struct no_arvore *R) { if (R != NULL) { printf("%i ", R->info); Pre_Ordem(R->esq); Pre_Ordem(R->dir); } }

void In_Ordem(struct no_arvore *R) { if (R != NULL) { In_Ordem(R->esq); printf("%i ", R->info); In_Ordem(R->dir); } }

void Pos_Ordem(struct no_arvore *R) { if (R != NULL) { Pos_Ordem(R->esq); Pos_Ordem(R->dir); printf("%i ", R->info); } }