Construa a árvore binária com os códigos de prefixo que representam estes esquemas de codificação.
a: 11, e: (0, t: 101, s: 100)

Passo 1

O enunciado pede para construir a árvore binária de prefixo que representa o código dado pelos pares \;a:11,\;e:0,\;s:100,\;t:101.
O assunto aqui é a construção de uma trie (árvore de prefixos), onde cada aresta leva a 0 (filho esquerdo) ou 1 (filho direito), e cada símbolo fica em uma folha.

Passo 2

Definimos o procedimento de inserção de cada símbolo na árvore:
— Para cada bit do código, a partir da raiz seguimos à esquerda se for 0 e à direita se for 1.
— Se não existir nó, criamos um nó interno.
— Ao consumirmos todos os bits, colocamos o símbolo nessa folha.

Passo 3

Inserção dos símbolos:
e com código 0: da raiz vai-se à esquerda e coloca-se a folha e.
a com código 11: da raiz vai-se à direita (1), depois à direita (1) e põe-se a folha a.
s com código 100: raiz→direita(1)→esquerda(0)→esquerda(0) e põe-se a folha s.
t com código 101: raiz→direita(1)→esquerda(0)→direita(1) e põe-se a folha t.

Passo 4

A árvore resultante, indicando em cada aresta o bit associado, fica assim (as folhas são os símbolos):
[raiz]
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t

Resposta

A árvore binária de prefixo é:
[raiz]
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t

Exercícios de Livros Relacionados