Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária (BT)

Passo 1

O enunciado pede a definição de árvore binária (BT). Este é um conceito de estruturas de dados e teoria de grafos em que precisamos entender a noção de nós ligados hierarquicamente, cada um com no máximo dois filhos (subárvores).

Passo 2

Uma árvore binária [T) é definida recursivamente da seguinte forma:
- Caso base: T pode ser a árvore vazia, denotada por \emptyset.
- Passo recursivo: se T não é vazia, existe um nó especial denominado raiz r e duas subárvores disjuntas T_{\text{esq}} (subárvore esquerda) e T_{\text{dir}} (subárvore direita), cada uma das quais também é uma árvore binária.
Formalmente:
T = \begin{cases} \emptyset, &\text{se a árvore está vazia;}\\[0.5em] \{\,r\}\cup T_{\text{esq}}\cup T_{\text{dir}}, &\text{se \(r é a raiz e T_{\text{esq}},T_{\text{dir}} são árvores binárias.} \end{cases}]
Elementos importantes na estrutura de uma árvore binária:
  1. Nó raiz: ponto de entrada da árvore.
  2. Subárvore esquerda e subárvore direita: ambas podem ser vazias ou não.
  3. Folha: nó cujo T_{\text{esq}}=\emptyset e T_{\text{dir}}=\emptyset.
  4. Altura de T: o número máximo de arestas de um caminho da raiz até uma folha.
  5. Profundidade de um nó: o número de arestas do caminho da raiz até esse nó.]

Resposta

Uma árvore binária é uma estrutura hierárquica definida recursivamente como sendo ou a árvore vazia \emptyset, ou um nó raiz r acompanhado de duas subárvores — esquerda e direita — cada uma delas também sendo uma árvore binária.

Exercícios relacionados