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

Passo 1

O enunciado dá um código de prefixo para os símbolos a,e,t,s,n com as seguintes associações: \mathtt{1}\to a, \mathtt{01}\to e, \mathtt{001}\to t, \mathtt{0001}\to s, \mathtt{00001}\to n.
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 a:
– Da raiz, ao ir por “1” chegamos a uma folha marcada a.
Ou seja, raiz→direita = a.

Passo 4

Agora trataremos todos os códigos que começam em “0”, criando uma cadeia de nós internos à esquerda:
Defina
• nó N_1=raiz \to 0\bullet N_2= N_1 \to 0\bullet N_3= N_2 \to 0\bullet N_4= N_3 \to 0
Em cada um desses nós colocaremos como filho direito a folha do símbolo cujo código termina aí em “1”:
N_1 \to 1= e (código \mathtt{01})
N_2 \to 1= t (código \mathtt{001})
N_3 \to 1= s (código \mathtt{0001})
N_4 \to 1= n (código \mathtt{00001})

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)

Exercícios de Livros Relacionados