Construa a árvore binária com os códigos de prefixo que representam estes esquemas de codificação.
a: 1, e: 01, t:001, s: 0001, n: 00001
a: 1, e: 01, t:001, s: 0001, n: 00001
Passo 1
O enunciado dá um código de prefixo para os símbolos
com as seguintes associações:
,
,
,
,
.
O que precisamos é montar a árvore de decisão binária em que cada ramo “0” leva ao filho esquerdo e cada ramo “1” ao filho direito, de modo que cada código seja o caminho da raiz até a folha correspondente.
O que precisamos é montar a árvore de decisão binária em que cada ramo “0” leva ao filho esquerdo e cada ramo “1” ao filho direito, de modo que cada código seja o caminho da raiz até a folha correspondente.
Passo 2
Definimos: a cada sequência de bits corresponde um percurso na árvore, partindo da raiz, seguindo “0”→esquerda e “1”→direita, e terminamos em uma folha rotulada pelo símbolo. Como é código prefixo, nenhuma folha pode estar no caminho de outra.
Passo 3
Insira o código de
:
– Da raiz, ao ir por “1” chegamos a uma folha marcada .
Ou seja, raiz→direita = .
– Da raiz, ao ir por “1” chegamos a uma folha marcada
Ou seja, raiz→direita =
Passo 4
Agora trataremos todos os códigos que começam em “0”, criando uma cadeia de nós internos à esquerda:
Defina
• nó =raiz
nó
=
nó
=
nó
=
Em cada um desses nós colocaremos como filho direito a folha do símbolo cujo código termina aí em “1”:
– (código
)
– (código
)
– (código
)
– (código
)
Defina
• nó
Em cada um desses nós colocaremos como filho direito a folha do símbolo cujo código termina aí em “1”:
–
–
–
–
Passo 5
Assim, não há mais códigos a inserir. A árvore final fica:
Resposta
(raiz)
/ \
0/ \1
/ a
(N1)
/ \
1/ \0
/ \
e (N2)
/ \
1/ \0
/ \
t (N3)
/ \
1/ \0
/ \
s (N4)
/ \
1/ \
/ \
n (vazio)