Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária (BT)
Á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: pode ser a árvore vazia, denotada por
.
- Passo recursivo: se não é vazia, existe um nó especial denominado raiz
e duas subárvores disjuntas
(subárvore esquerda) e
(subárvore direita), cada uma das quais também é uma árvore binária.
- Caso base:
- Passo recursivo: se
Formalmente:
é a raiz e
são árvores binárias.} \end{cases}]
Elementos importantes na estrutura de uma árvore binária:
- Nó raiz: ponto de entrada da árvore.
- Subárvore esquerda e subárvore direita: ambas podem ser vazias ou não.
- Folha: nó cujo
e . - Altura de
: o número máximo de arestas de um caminho da raiz até uma folha. - 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
, ou um nó raiz
acompanhado de duas subárvores — esquerda e direita — cada uma delas também sendo uma árvore binária.