Recursividade

[AJBM 28]

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?

[HappyHippyHippo 1,162]

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

[AJBM 28]

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

[HappyHippyHippo 1,162]

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

[AJBM 28]

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

[HappyHippyHippo 1,162]

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

[AJBM 28]

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?

Edited January 26, 2013 by AJBM

[HappyHippyHippo 1,162]

o que é suporto o algoritmo fazer ?

[AJBM 28]

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.

[HappyHippyHippo 1,162]

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 !!!"

[AJBM 28]

ok xD.

Apenas apresenta o resultado, não faz nada de importante, eu invoco o método e vejo o resultado

[HappyHippyHippo 1,162]

como não consegues explicar então para que é usado o DPS, só mesmo vendo o código

[AJBM 28]

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();
}

[HappyHippyHippo 1,162]

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

[AJBM 28]

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?

Edited January 26, 2013 by AJBM

[HappyHippyHippo 1,162]

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