Aula sobre Estruturas de Dados: Árvores Binárias

Definição de Árvores Binárias

• Conjunto finito de elementos, que podem ser vazios.
• Raiz com subárvore esquerda e direita, que também são binárias.
• Implementação em Python usando classes e construtores.

Representação e Características

• Representação em grafos.
• Conceito de árvore estritamente binária (grau 0 ou 2).
• Árvore binária completa: estritamente binária, folhas no último ou penúltimo nível.
• Árvore binária cheia: todas as folhas no mesmo nível.

Percurso de Árvores Binárias

• Diferença de percurso em lista (linear) e árvore (hierárquica).
• Três percursos básicos: pré-ordem, em ordem e pós-ordem.
  • Pré-ordem: Visita raiz, percorre esquerda, depois direita.
  • Em ordem: Percorre esquerda, visita raiz, percorre direita.
  • Pós-ordem: Percorre esquerda, direita, depois visita raiz.

Árvores Binárias de Busca (BST)

• Propriedade: nós na subárvore esquerda são menores, na direita são maiores.
• Importante para operações eficientes de busca.
  • Exemplo: sistemas de votação por telefone.

Operações em Árvores Binárias de Busca

• Busca: Comparação com a raiz, percorre à esquerda ou direita recursivamente.
• Inserção: Adiciona nó respeitando a propriedade BST.
• Remoção: Três casos possíveis: nó sem filho, com um filho, ou com dois filhos.
  • Remoção de nó sem filho é simples.
  • Remoção com um filho: substitui o pai pelo filho.
  • Remoção com dois filhos: substitui pelo antecessor ou sucessor.

Exercício

• Realizar inserções e remoções em uma árvore binária e verificar as propriedades.

Conclusão

• Importância das árvores binárias em estrutura de dados para operações eficientes de busca, inserção e remoção.

Estes são os pontos principais discutidos na aula sobre árvores binárias e suas propriedades. Recomenda-se revisar o material de implementação em Python e os exemplos de percurso para um entendimento mais profundo.