AJBM 30 Denunciar mensagem Publicado 25 de Janeiro de 2013 Boas! Eu tenho este método, que faz a travessia numa árvore binaria, mas não estou a compreender muito bem a parte da recursividade. protected void inorder (BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) { if (node != null) { inorder (node.left, tempList); tempList.addToRear(node.element); inorder (node.right, tempList); } } Por exemplo nesta árvore http://www.imagensonline.net/images/arvore.png, o resultado da travessia é D B E A C, e eu não percebi porque? Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 25 de Janeiro de 2013 protected void inorder (BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) { if (node != null) { // se for um nó válido inorder (node.left, tempList); // chamar a função de leitura do nó na sub árvore da esquerda tempList.addToRear(node.element); // guardar o valor do nó actual inorder (node.right, tempList); // chamar a função de leitura do nó na sub árvore da direita } } agora apresentar o código que é executado, mas sem chamadas recursivas, simplesmente como se o código fosse todo corrifo // Nó A if (node != null) { // válido //inorder (node.left, tempList); // Nó B if (node != null) { // válido //inorder (node.left, tempList); // Nó D if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D //inorder (node.right, tempList); // NULL if (node != null) // inválido } tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B //inorder (node.left, tempList); // Nó E if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E //inorder (node.right, tempList); // NULL if (node != null) // inválido } } tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A //inorder (node.right, tempList); // Nó C if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A C //inorder (node.right, tempList); // NULL if (node != null) // inválido } } IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 25 de Janeiro de 2013 protected void inorder (BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) { if (node != null) { // se for um nó válido inorder (node.left, tempList); // chamar a função de leitura do nó na sub árvore da esquerda tempList.addToRear(node.element); // guardar o valor do nó actual inorder (node.right, tempList); // chamar a função de leitura do nó na sub árvore da direita } } agora apresentar o código que é executado, mas sem chamadas recursivas, simplesmente como se o código fosse todo corrifo // Nó A if (node != null) { // válido //inorder (node.left, tempList); // Nó B if (node != null) { // válido //inorder (node.left, tempList); // Nó D if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D //inorder (node.right, tempList); // NULL if (node != null) // inválido } tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B //inorder (node.left, tempList); // Nó E if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E //inorder (node.right, tempList); // NULL if (node != null) // inválido } } tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A //inorder (node.right, tempList); // Nó C if (node != null) { // válido //inorder (node.left, tempList); // NULL if (node != null) // inválido tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A C //inorder (node.right, tempList); // NULL if (node != null) // inválido } } Como é que sabes que no segundo add é o elemento B?? Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 25 de Janeiro de 2013 vê se assim consegues perceber melhor : +// Nó A |if (node != null) { // válido | //inorder (node.left, tempList); +->// Nó B . |if (node != null) { // válido . | //inorder (node.left, tempList); . +->// Nó D . . |if (node != null) { // válido . . | //inorder (node.left, tempList); . . | // NULL . . | if (node != null) // inválido . . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D . . | //inorder (node.right, tempList); . . | // NULL . v-< if (node != null) // inválido . | } . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B . | //inorder (node.left, tempList); . +->// Nó E . . |if (node != null) { // válido . . | //inorder (node.left, tempList); . . | // NULL . . | if (node != null) // inválido . . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E . . | //inorder (node.right, tempList); . . | // NULL . . | if (node != null) // inválido v-<-<} | } @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A | //inorder (node.right, tempList); +->// Nó C . |if (node != null) { // válido . | //inorder (node.left, tempList); . | // NULL . | if (node != null) // inválido . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B E A C . | //inorder (node.right, tempList); . | // NULL . | if (node != null) // inválido v-<} } IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B . | //inorder (node.left, tempList);//aqui nao é inorder(node.right,tempList)??????? A seguir ao add visitamos o no da direita certo? Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 26 de Janeiro de 2013 . @->tempList.addToRear(node.element); // Adicionar à lista de resultado o valor do nó actual = D B . | //inorder (node.left, tempList);//aqui nao é inorder(node.right,tempList)??????? A seguir ao add visitamos o no da direita certo? sim ... problemas de copy paste ... IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 (editado) OK Já percebi. obrigado Ja agora eu tenho um algoritmo travessia em profundidade (depth-first traversal) DFS, para um grafo e ele usa estruturas de dados LInkedStack e a ArrayUnorderedList, eu vi na net o algoritmo e ele usava estas estruturas, mas eu não sei porque. Por acaso não sabes o porque? Editado 26 de Janeiro de 2013 por AJBM Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 26 de Janeiro de 2013 o que é suporto o algoritmo fazer ? IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 Percorrer o grafo em profundidade, o algoritmo começa num nó raiz e explora tanto quanto possível cada um dos seus ramos, antes de retroceder. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 26 de Janeiro de 2013 eu sei o que é DFS, eu não sei é o que o método faz com a informação dos nós !!! porque uma pergunta dessas é mesma coisa que perguntar : - "porque razão é que um funcionário de mesa usa sapatilhas ?" resposta: - "não faço ideia porque não não faço ideia o que é que faz fora do trabalho !!!" IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 ok xD. Apenas apresenta o resultado, não faz nada de importante, eu invoco o método e vejo o resultado Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 26 de Janeiro de 2013 como não consegues explicar então para que é usado o DPS, só mesmo vendo o código IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 protected Iterator<T> iteratorDFS(int startIndex) { Integer x; boolean found; LinkedStack<Integer> traversalStack = new LinkedStack<Integer>(); ArrayUnorderedList<T> resultList = new ArrayUnorderedList<T>(); boolean[] visited = new boolean[numVertices]; if (!indexIsValid(startIndex)) { return resultList.iterator(); } for (int i = 0; i < numVertices; i++) { visited[i] = false; } traversalStack.push(new Integer(startIndex));//adiciona um elemento a stack resultList.addToRear(vertices[startIndex]);//adiciona um elemento ao array visited[startIndex] = true; while (!traversalStack.isEmpty()) { x = traversalStack.peek();//retorna o ultimo elemento a ser adiconado a stack found = false; for (int i = 0; (i < numVertices) && !found; i++) { if ((adjMatrix[x.intValue()][i] < Double.POSITIVE_INFINITY) && !visited[i]) { traversalStack.push(new Integer(i));;//adiciona um elemento a stack resultList.addToRear(vertices[i]);adiciona um elemento ao array visited[i] = true; found = true; } } if (!found && !traversalStack.isEmpty()) { traversalStack.pop(); } } return resultList.iterator(); } Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 26 de Janeiro de 2013 isso não é uma DFS, mas sim um BFS (http://en.wikipedia.org/wiki/Breadth-first_search) prova : inserir imediatamente o valor do nó antes de qualquer processamento e o uso da stack é convencional nesse método IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
AJBM 30 Denunciar mensagem Publicado 26 de Janeiro de 2013 (editado) troquei os algoritmos no BFS implementei o DFS e no DFS implementei o BFS... Utiliza-se stack neste algoritmos devido a sua implementação em LIFO? Editado 26 de Janeiro de 2013 por AJBM Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
HappyHippyHippo 1185 Denunciar mensagem Publicado 27 de Janeiro de 2013 não ... usam uma stack porque não deve conhecer uma queue. nota que estão a inserir na stack com a função "addToBack" que presumo, seja um método de inserir no local não padrão da stack IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites