53
edits
Changes
Jump to navigation
Jump to search
→Percursos em Árvore
== Percursos em Árvore ==
Nessa seção, mostramos como usar o Maple para fazer percursos em árvores. Lembre-se que um algoritmo de percurso em árvore é um procedure para sistematicamente visitar cada vértice de uma árvore ordenada com raiz. Em particular, iremos dar procedures para três importantes algoritmos de percurso em árvore: pré-ordem, ordem, e pós-ordem. Então iremos mostrar como usar esses métodos de percurso para produzir as notações pré-fixa, infixa e pós-fixa para expressões aritméticas.
Esses percursos em árvore dependem da construção de árvores ordenadas com raiz. Nós devemos usar os pesos dos vértices para representar a ordem dos filhos, como foi feito nas seções anteriores.
Criamos uma árvore desordenada, baseada na árvore da figura 3 da página 5566 do texto, para ver o comportamento dos vários tipos de percurso de árvore. Então o grafo da árvore se torna:
d := 'd':
<pre>
new(Trav):
addvertex( [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p],
weights=[0,1,2,3,1,2,1,2,3,1,2,1,2,1,2,3], Trav):
addedge( [[a,b],[a,c],[a,d],[b,e],[b,f],[d,g],[d,h],
[d,i],[e,j],[e,k],[g,l],[g,m],[k,n],[k,o],[k,p]], Trav):
draw(Tree(a),Trav);
</pre>
Os pesos adicionados aos vértices aqui representam o número que desse vértice em termos de seu pai. Por exemplo, d é o terceiro filho de a. Como nas seções anteriores, tais pesos poderiam ser usados para ordenação, apesar de que em fato, a ordenação por baixo é simplesmente alfabético nos nomes dos vértices.
Primeiro implementamos o algaritmo de percurso em pré-ordem. Esse visita a raiz e então cada sub-árvore da esquerda a direita em uma maneira de percurso em pré-ordem. Em forma de pseudo-código, o algoritmo para pré-ordem é:
1. Visite a raiz de T. Ponha o atua vértice para ser a raiz.
2. Considere os filhos do vértice atual como raízes das árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita. Repita o passo (1) em cada sub-árvore em ordem.
Como pode ser visto no passo (2) do pseudo-código acima, esse algoritmo é recursivo. Nós providenciamos a seguinte implementação em Maple:
<pre>
Preorder:=proc(G::graph, r)
local Dep, v, T;
</pre>
Visite a raiz
<pre>
printf(`%a `, r);
</pre>
Considere os filhos da raiz
<pre>
Dep:= departures(r, G);
</pre>
Forme a ordem correta dos filhos
<pre>
Dep:= sort( convert(Dep,list) , IsLessThan );
</pre>
Percorre em pré-ordem essas sub-árvores em ordem
<pre>
for v in Dep do
Preorder(G, v);
od;
printf(``, r);
end:
</pre>
A ordem em que nós percorremos os descendentes é determinada pela procedure booleana isLessThan (das seções anteriores). Para percorrer os descendentes em uma ordem diferente, use uma comparação de rotina diferente.
Podemos examinar a execução esse procedure no percurso de árvore criado anteriormente, enraizado no vértice A.
<pre>
Preorder(Trav, a);
</pre>
Nós implementamos o percurso em ordem de maneira similar. Simplesmente alteramos a sequência na qual os vértices são visitados. Especificamente, olhamos na sub-árvore mais a esquerda dos vértices, seguida pela raiz, seguida pela sub-árvore mais a direita dos vértices. Em pseudo-código, temos:
1. Se a árvore T tem apenas um vértice, r então visite r
2. Caso contrário, a árvore T tem mais que um vértice. Chame a sub-árvore mais a esquerda(enraizada no filho mais a esquerda) T_1. Percorre em ordem T_1, então visite a raiz r de T.
3. Percorra em ordem as sub-árvores com raiz T_2,...,T_m.
Em Maple, a implementação seria a seguinte:
<pre>
Inorder:=proc(G::graph, r)
local v, Dep, T;
</pre>
se tivermos atingido um vértice folha, imprima ele
<pre>
if outdegree(r, G) = 0 then
print(r);
</pre>
Estamos em um vértice interno
<pre>
else
Dep:=departures(r, G);
</pre>
Determina a ordem dos filhos e percorra a sub-árvore baseada no filho mais a esquerda
<pre>
Dep := sort( convert( Dep , list ), IsLessThan );
Inorder(G, Dep[1]);
</pre>
Visite a raiz
<pre>
print(r);
</pre>
Percorra em ordem as sub-árvores restantes
<pre>
for v in Dep[2..nops(Dep)] do
Inorder(G, v);
od;
fi; NULL;
end:
</pre>
Nós adicionamos um NULL como última declaração, para que nada seja retornado.
Novamente, para percorrer os filhos em uma ordem diferente, use uma comparação de rotina diferentes para ordenar os descendentes. Teste esse novo procedure executando ele em tree Trav.
<pre>
Inorder(Trav, a);
</pre>
O percurso final que devemos implementar é em pós-ordem. Percurso em pós-ordem é similar ao percurso em pré-ordem, exceto que visitamos a raiz após visitar cada sub-árvore. Segue o pseudo-código:
1. Considere os filhos da raiz as sub-árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita.
2. Percorre em pós-ordem T_1, então T_2, até T_m.
3. Imprima a raiz da atual árvore.
Em maple, temos o seguinte procedure:
<pre>
Postorder:=proc(G::graph, r::name)
local v,i, Dep, T;
</pre>
Considere filhos da raiz
<pre>
Dep:=departures(r, G);
</pre>
Forme a ordem correta dos filhos
<pre>
Dep:= sort( convert(Dep,list) , IsLessThan) ;
</pre>
Percorra em pós-ordem essas sub-árvores em ordem
<pre>
for v in Dep do
Postorder(G, v);
od;
</pre>
Visite a raiz
<pre>
printf(` %c`, r);
end:
</pre>
Também testamos esse procedure na tree Trav com raiz A
<pre>
Postorder(Trav, a);
</pre>
=== Notações Infixa, Pré-fixa e Pós-fixa ===
Agora iremos discutir como usar o Maple para trabalhar com as formas infixa, pré-fixa e pós-fixa de expressões aritméticas. Essas formas são discutidas na sessão 8.33 do texto. Especificamente, iremos mostrar como criar uma representação em árvore binária de uma expressão infixa, como usar percursos em pós-ordem e pré-ordem para crias as formas pós-fixa e pré-fixa de expressões, respectivamente, e como avaliar essas expressões a partir de suas formas pós-fixa e pré-fixa.
Para começar essa seção, nós construímos um procedure em Maple que pega uma expressão aritmética infixa e a converte em um representação de árvore binária. Essa representação é árvore binária pode ser percorrida usando os percursos das seções anteriores para formar vários formatos de representação aritmética. Como um exemplo, podemos construir uma árvore binária representando uma expressão infixa, como (3+10)^2 - (100-30)/(5*2), e então executar um percurso em pré-ordem nessa árvore para formar a representação pré-fixa dessa expressão aritmética.
No procedure em Maple que iremos implementear, consideraremos uma versão modificada da notação infixa, para evitar manipulações complicadas de string que depreciam o verdadeiro problema.
Especificamente, iremos utilizar chaves ao invés dos parênteses normalmente utilizados na notação infixa.
Adicionalmente, iremos definir nossos operadores em termos de suas representações em string: + para adição, - para subtração e assim vai.
Dessa maneira, as facilidades de manipulação de lista do Maple ficam imediatamente disponíveis. Então, nós representamos expressões x + y as [x,"+",y] onde + é uma string.
Procedures do Maple podem ser usados para ajudar-nos a construir tais listas. Por exemplo,
<pre>
`&Plus` := proc(a,b) [a,Unique(`+`),b] end:
</pre>
nos permite escrever e usar
<pre>
x &Plus y;
</pre>
O Maple manipula os nomes de procedures da forma ... como operadores infixos. O procedure que Unique tem é definido especialmente para as rotinas usadas nesse artigo.
O resultado é uma lista incluindo versões especialmente encodadas da string + que não colide com usos anteriores de + como nome. (Cada vértice da expressão árvore deve ter um nome diferente, mesmo que eles pareçam iguais).
Similarmente, usamos
<pre>
`&Times` := proc(a,b) [a,Unique(`*`),b] end:
`&Pow` := proc(a,b) [a,Unique(`^`),b] end:
`&Div` := proc(a,b) [a,Unique(`/`),b] end:
`&Minus` := proc(a,b) [a,Unique(`-`),b] end:
</pre>
para que possamos escrever e usar
<pre>
x &Times y, x &Pow y;
</pre>
Esses podem ser usados para escrever a expressão aritmética ((x+y)^2)+((z-4)/3) como
<pre>
Expr1:= (((x &Plus y) &Pow 2) &Plus ((z &Minus 4) &Div 3 ));
</pre>
O resultado é uma lista aninhada de listas, com cada lista representando uma operação binária.
Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário em pseudo-código é:
1. Se houver uma expressão algébrica isolada (como um nome ou número), a árvore consiste de um vértice isolado.
2. Caso contrário, a lista consiste de um operando a esquerda, um operador e um operando a direita. Use o algoritmo para construir a árvore binária para operando a esquerda.
3. Repita o passo (2) no operando a direita.
4. Combina os resultados dos passos (2) e (3) para formar a árvore binária.
Nossa implementação é a seguinte:
<pre>
InFixToTree:=proc(L::list,algebraic)
local r1,r3, T1, T3,LocL;
</pre>
Se não tivermos sublistas em nossa expressão, retorne as listas de arestas e vértices como mostrado
<pre>
if type(L,algebraic) then
new(T1); LocL := Unique(L);
addvertex(LocL,T1);
T1(Root) := LocL;
RETURN( eval(T1) );
fi;
</pre>
L é agora uma lista como [a , + , b]
<pre>
T1 := InFixToTree(L[1]); r1 := T1(Root);
T3 := InFixToTree(L[3]); r3 := T3(Root);
</pre>
construa a nova árvore
<pre>
addvertex(vertices(T3),T1);
addedge( ends(T3), T1 );
addvertex( L[2] , T1 ):
addedge( [L[2],r1], [L[2],r3] , T1 );
T1(Root) := L[2];
RETURN( eval(T1) );
end:
</pre>
A raiz da árvore é manipulada de maneira especial. Recomputando a raiz da árvore é estranho e caro, então nós simplesmente pedimos a cada árvore que se lembre sua própria raiz. Isso feito por declarações de tarefa como T(Root) := LocL;.
O procedure Unique é novamente usado para se assegurar que cada instancia de vértice tem nome único, mesmo que pareça igual a outro. Em todos os outros aspectos, a implementação é quase exatamente como descrito no pseudo-código.
Para testar esse procedure, use-o para construir uma expressão árvore para a expressão anterior Expr1.
<pre>
Expr1;
TreeExpr1:=InFixToTree(Expr1):
</pre>
Para ver isso, desenhe-o como uma árvore.
<pre>
r := TreeExpr1(Root);
draw(Tree(r),TreeExpr1);
</pre>
Suponha que somos dados uma representação em árvore binária de uma expressão aritmética. Nós podemos usar os algoritmos anteriormente criados para expressas essas árvores como expressões pós-fixas ou pré-fixas executando os percursos de pós-ordem ou pré-ordem, respectivamente. Como isso é trivial, cabe ao leitor explorar essa técnica.
Como um exemplo final dessa seção, nós demonstramos como avaliar uma dada expressão pós-fixa. Para simplificar, nós representamos as operações básicas pelas primeiras letras das palavras add, subtract, multiply, divide e exponentiate. cabe ao leitor explorar como implementar um procedure que irá avaliar uma expressão pré-fixa, dado que essa técnica é a simples modificação do argumento que será usado no caso pós-fixo.
<pre>
Post1:=[7,2,3,M,S,4,E,9,3,D,A];
Postfix:=proc(T::list)
local i, L;
L:=T;
while nops(L)>1 do
i:=1;
while not member(L[i], 'A','S','D','M','E') do
i:=i+1;
od;
if L[i]='A' then
L[i]:= L[i-2]+L[i-1];
elif L[i]='M' then
L[i]:= L[i-2]*L[i-1];
elif L[i]='S' then
L[i]:= L[i-2]-L[i-1];
elif L[i]='D' then
L[i]:= L[i-2]/L[i-1];
elif L[i]='E' then
L[i]:= L[i-2]^L[i-1];
fi;
L := [op(L[1..i-3]),op(L[i..nops(L)])];
od;
L;
end:
Postfix(Post1);
</pre>
Note que em release 4, nós somos permitidos atribuir diretamente a lista elements.
== Árvores e Ordenação ==
