53
edits
Changes
Jump to navigation
Jump to search
Determina Determine a ordem dos filhos e percorra a sub-árvore baseada no filho mais a à esquerda
no edit summary
O resultado é claramente uma árvore binária de busca.
Árvores binárias existem para serem usadas como método de busca. O procedure BiSearch a seguir faz isso. Declarações do tipo Print foram adicionadas para ilustrar o caminho que o algoritmo usa enquanto faz a busca na árvore.
<pre>
</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 rotina de comparação de rotina diferente.Podemos examinar a execução esse procedure no percurso de árvore criado anteriormente, enraizado com raiz no vértice A.
<pre>
</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, e em seguida a sub-árvore mais a direita dos vértices. Em pseudocódigo, temos:
1. Se a árvore T tem apenas um vérticer, 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 com raiz 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.
</pre>
<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 rotina de comparação de rotina diferentes diferente para ordenar os descendentes. Teste esse novo procedure executando ele em tree na árvore Trav.
<pre>
</pre>
O percurso final que devemos implementar implementaremos é em pós-ordem. Percurso O percurso em pós-ordem é similar ao percurso em pré-ordem, exceto que apenas visitamos a raiz após visitar cada sub-árvore. Segue o pseudocódigo:
1. Considere os filhos da raiz as sub-árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita.
end:
</pre>
Também testamos esse procedure na tree árvore Trav com raiz A
<pre>
</pre>
Note que as duas árvores de extensão são diferentes mesmo que elas estejam enraizadas tenham raiz no mesmo vértice. Em particular, a árvore com depth-first search tem uma estrutura funda e magra, enquanto a árvore com breadth-first search é menor e mais larga. Essas representações gráficas ajudam a ilustrar o algoritmo utilizado, e heuristicamente, nós podemos usar as representações para adivinhar qual dos dois algoritmos foi usado.
=== Backtracking ===
