Qual a diferença entre uma árvore binária cheia e uma árvore binária completa?
3 Respostas
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)
Completa (Complete tree)
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 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.
Assim fica claro entender o termo, "tanto à esquerda quanto possível". Caso contrário, os nós vão se sobrepôr.
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.”
-
Não entendi a crítica à resposta anterior. Tem como reforçar com uma imagem? Commented 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. Commented 24/03/2018 às 14:33