9

Qual a diferença entre uma árvore binária cheia e uma árvore binária completa?

3 Respostas 3

11

Definição do Prof. Adriano Cruz da UFRJ que acredito ser bem tranquila de entender:

Uma árvore estritamente binária é uma árvore binária em que cada nó tem 0 ou 2 filhos. Uma árvore binária cheia é uma árvore em que se um nó tem alguma sub-árvore vazia então ele está no último nível.

Uma árvore completa é aquela em se n é um nó com alguma sub-árvores vazias, então n se localiza no penúltimo ou no último nível. Portanto, toda árvore cheia é completa e estritamente binária.

Cheia (Full tree)

inserir a descrição da imagem aqui

Completa (Complete tree)

inserir a descrição da imagem aqui

2
  • @Matheus kkkkkkk , mai se respondeu primeiro... Rápido no gatilho...Nice...
    – MagicHat
    9/06/2016 às 17:20
  • @MagicHat kkkkkk que coincidência! +Upvote pra você! Respondeu certo chefe :-D
    – Mateus
    9/06/2016 às 17:28
6

Tipo assim patrão:

Árvore binária cheia : é uma árvore em que cada nó na árvore tem 0 ou 2 nós filhos(ou folhas).

Árvore Binária Cheia

Árvore binária completa : em uma árvore binária completa todos os níveis, exceto possivelmente o último , está completamente cheia, e todos os nós no último nível são, tanto à esquerda quanto possível.

inserir a descrição da imagem aqui

Assim fica claro entender o termo, "tanto à esquerda quanto possível". Caso contrário, os nós vão se sobrepôr.

3

Penso que a definição de árvore binária cheia dada pelo MagicHat está incorreta, porque a árvore binária cheia não pode ter nó com zero filhos antes do último nível e a resposta dele deixa aberta esta alternativa, porém a imagem realmente representa uma árvore binária cheia, olha a definição do livro estrutura de dados e seus algoritmos, 2a. Edição de Jayme Luiz Szwarcfiter. “Uma árvore binária cheia é aquela em que, se v é um nó com alguma de suas sub árvores vazias, então v se localiza no último nível. Segue-se que toda árvore binária cheia é completa e estritamente binária.” inserir a descrição da imagem aqui

2
  • Não entendi a crítica à resposta anterior. Tem como reforçar com uma imagem? 24/03/2018 às 13:44
  • imagem inserida, não foi crítica, apenas uma correção, baseado no livro que inclusive estou lendo neste momento. 24/03/2018 às 14:33

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .