Changes

Á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.

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.

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.

Determina Determine a ordem dos filhos e percorra a sub-árvore baseada no filho mais a à esquerda

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.

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:

Também testamos esse procedure na tree árvore Trav com raiz A

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 também 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 uma representação de árvore binária. Essa representação é em á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 implementearimplementar, consideraremos uma versão modificada da notação infixa, para evitar manipulações complicadas de string que depreciam o verdadeiro problema.

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 como [x,"+",y] , onde + é uma string.

O resultado é uma lista incluindo versões especialmente encodadas codificadas 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). 

Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário para isso em pseudocódigo é:

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 o operando a à esquerda.

3. Repita o passo (2) no operando a à direita.

Nossa implementação é a seguinteesta:

Se não tivermos sublistas em nossa expressão, retorne as listas de arestas e vértices como mostrado

A raiz da árvore é manipulada de maneira especial. Recomputando Recomputar a raiz da árvore é estranho complicado e carotaxativo, então nós simplesmente pedimos a cada árvore que se lembre de sua própria raiz. Isso é feito por declarações de tarefa como T(Root) := LocL;.

Para testar esse procedure, use-o para construir uma árvore de expressão árvore para a expressão anterior Expr1.

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 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.

Note que em release 4, nós somos permitidos atribuir diretamente a à lista elements.

Nós iremos agora implementar o merge sort em Maple. Nós Usaremos também iremos usar o Maple para estudar a complexidade desse algoritmo. O algoritmo de merge sort pode ser implementado como um procedure recursivo. A idéia básica da tarefa de aplicar merge sort numa lista é de dividir a lista dividi-la em duas de tamanhos iguais ou quase iguais, ordenando cada sub-lista usando o algoritmo merge sort, e no final juntando as listas resultantes. Isso pode ser descrito no seguinte pseudocódigo:

1. Se a lista L tem apenas um elemento, ela é está ordenada em ordem, então retornamos L como ela é.

Nós iremos agora analizar o tempo de execução do MergeSort em relação ao BubbleSort. Especificamente, nós iremos criar uma lista desordenada com 10000 1000 elementos aleatórios e executar o BubbleSort e o MergeSort nessa lista. Isso irá nos dar uma ilustração limitada do tempo de execução desses procedures, na qual o leitor deve expandir lendo análises teóricos no texto.

Para criar uma lista aleatória com 1000 100 elementos, usamos os comandos rand e seq do Maple, como representado a seguir:

O leitor é encorajado a implementar outros tipos de algoritmos de ordenação usando o Maple e a estudar a complexidade relativa desses algoritmos quando usandos para ordenar listas de vários tamanhos diferentes. Também é interessante usar técnicas de animação para ilustrar os passos dos algoritmos de ordenação. Apesar de não fazermos isso aqui, o leitor com habilidades avançadas de programação é convidado a fazê-lo. Tome nota especial para a Atente-se à importância de usar a estrutura de dados correta, ex: lists vs arrays.

Essa seção explica como usar o Maple para construir árvores de extensão (spanning trees) para grafos e como usar árvores de extensão usá-las para resolver muitos tipos diferentes de problema. Árvores de extensão já foram usadas no capítulo 7; elas tem uma grande quantidade de aplicações. Em particular, nós iremos mostrar como usar o Maple para formar as essas árvores de extensão usando dois algoritmos: depth-first search (busca em profundidade) e breadth-first search(busca em largura). Então nós iremos mostrar , mostraremos como usar o Maple para fazer backtracking, uma ténica baseada em depth-first search , usada para resolver vários problemas.

Para começar, nós iremos discutir discutiremos como implementar o algoritmo de depth-first search no Maple. Como o nome do algoritmo (busca em profundidade, em português) sugere, os vértices são visitados em ordem de crescimento crescente de profundidade da na árvore de extensão. O pseudocódigo é:

2. Escolha x para ser um vizinho de w que não está na árvore. Adicione aresta(x,w) e faça conjunto w igual a = x.

3. Repita o passo (2) até não haver ter mais vértices que não estão na árvore.

 Nós demonstramos Demonstramos o uso do procedure de depth-first search com o seguinte exemplo:

Tendo implementado o algoritmo de árvore de extensão de depth-first search, agora nós podemos modificar levemente o código Maple e conseguir uma árvore de extensão com breadth-first search. Especificamente, o O algoritmo de breadth-first search opera examinando todos os vértices da atual profundidade do grafo antes de se mover para baixo, no próximo nível do grafo. Antes de implementar esse algoritmo, nós damos uma descrição em pseudocódigo do algoritmodele.

2. Adicione arestas de V até para cada vértice em N_1 que ainda não está na árvore de extensão.

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 é um método que pode ser usado para achar soluções para resolver problemas que poderiam ser impráticos de se resolver solucionar usando técnicas de busca excessiva, . O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos como usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de , que consiste em posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em visa encontrar um subconjunto de um conjunto de inteiros cuja soma é um inteiro dado inteiro.

O primeiro problemas problema que nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde sendo n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudocódigo para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn:

Outro problema que pode ser solucionado com uma solução elegante de backtracking é o problema de posicionar n-rainhas em um tabuleiro de xadrez de dimensão nXn de maneira que nenhuma rainha tem tenha como atacar a outra. Isso significa que nenhum par de rainhas pode ser posicionadona posicionado na mesma linha horizontal, vertical ou diagonal. Nós iremos resolver esse problema usando um procedure baseado em backtracking. Iremos posicionar as rainhas no tabuleiro de uma maneira gananciosa, até que todas as rainhas elas estejam posicionadas ou não haja mais posição disponível para um rainha ficar sem estar na mesma linha diagonal, vertical ou horizontal que outra já posicionada.