Caminhamento em árvore

Prévia do material em texto

Caminhamento em árvore
1. As árvores são estruturas de dados de grande contribuição, principalmente no que tange as expressões 
aritméticas, em que o percurso utilizado pode influenciar diretamente.
O caminhamento em árvore é realizado de três formas, as quais variam conforme a posição de leitura do nó raiz,
que podem ser: 
D. em-ordem, pós-ordem, pré-ordem.
Os percursos realizados em árvores binárias variam em três tipos, conforme a posição de leitura do nó raiz,
podendo ser pré-ordem, quando a raiz de cada subárvore é lida anteriormente às subárvores esquerda e direita.
Quando somente a subárvore esquerda é visitada antes do nó raiz, dá-se o nome de percurso em-ordem. E
quando tanto a subárvore esquerda como a direita são lidas anteriormente à raiz, atribui-se o percurso pós-
ordem.
2. Árvores binárias possibilitam maior organização dos elementos adicionados, o que facilita separar os 
elementos a cada nível de crescimento da árvore.
Dada a seguinte lista de caracteres [P, R, O, G, R, A, M, A, D, O, R, U, M], como ficaria seu resultado final em
uma leitura pós-ordem, caso seus valores fossem adicionados sequencialmente, do primeiro ao último elemento,
em uma árvore binária? Para montar uma árvore binária, os elementos menores ou iguais ao nó mais abaixo
entrará à esquerda; caso contrário, ficará à direita.
B. A D A M O M G O R R U R P.
A leitura em pós-ordem é realizada de modo que é feita primeira a visita na subárvore esquerda, depois à raiz e, por fim,
a subárvore à direita. Atendendo a forma de inserção dos elementos, e seguindo a regra de leitura em pós-ordem, será 
obtida a seguinte sequência: A D A M O M G O R R U R P.
As demais alternativas não atendem aos critérios exigidos na questão, sendo que a alternativa A apresenta o modelo de 
leitura em-ordem, e a alternativa C em pré-ordem.
3. Uma árvore binária que tenha como finalidade resolver problemas aritméticos, necessita que sua leitura seja 
feita de tal modo a combinar dois operandos para o operador da expressão. Exemplo: A + B.
Portanto, como uma árvore deveria posicionar seus elementos e qual seria a melhor forma de leitura para que as
operações ocorram?
B. É preferível que os valores da operação aritmética estejam localizados à esquerda e à direita da raiz, desde que o
operador seja raiz, e a leitura da árvore seja feita em-ordem.
Em uma árvore binária, para avaliar expressões aritméticas, é importante organizá-la de tal forma que os
operadores dividam simetricamente cada subexpressão, de modo a facilitar sua leitura. Tendo este objetivo em
mente, é preferível que existam os operadores (soma, subtração, multiplicação e divisão), ocupando sempre a
raiz, separando de forma mais simétrica os operandos (valores) da expressão, para uma leitura realizada em-
ordem.
4. O caminhamento de uma árvore binária influencia diretamente no resultado final de leitura de uma
determinada sequência de símbolos, e pode se encontrar em 3 tipos, como percursos em pré-ordem,  in-ordem e
pós-ordem, variando, assim, a posição do valor raiz.
Qual função a seguir descreve o percurso realizado em pós-ordem?
A. 
def funcao(no):
if atual != None:
funcao(no.esquerdo)
funcao(no.direito)
print("Valor: {}.".format(no.valor))
A ordem dos elementos visitados em pós-ordem estabelece que os elementos da subárvore à esquerda serão
visitados, seguidos dos elementos das subárvores à direita e, por fim, os elementos raízes.
Mesmo que todas as funções apresentem recursividade, apenas a função com a impressão sucedendo às duas
chamadas recursivas para as subárvores esquerda e direita imprimem o caminho pós-ordem.
5. O modo como é feito o percurso determina como será o nível de prioridade de leitura dos elementos, podendo
o nó raiz estar com prioridade (leitura em pré-ordem), ou os elementos da subárvore à esquerda (leitura  in-
ordem), ou os elementos da subárvore à esquerda seguido da leitura à direita (pós-ordem).
Considerando a imagem a seguir, mostre a sequência de expressões resultantes, conforme os percursos de pré-
ordem, em-ordem e pós-ordem, respectivamente.
C. * 3 * 5 13
3 * 5 * 13
3 5 13 * *
Os percursos variam conforme a sua modalidade, a qual está relacionada à posição de visita do nó raiz. Neste
caso, onde é desejado obter as 3 formas de leitura, é possível identificar um padrão no posicionamento do
operador aritmético, cujo posicionamento está mais à esquerda na leitura em pré-ordem: * 3 * 5 13; está mais
simétrico na leitura em-ordem: 3 * 5 * 13; e mais à direita para a leitura em pós-ordem: 3 5 13 * *.
	Caminhamento em árvore