Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

AJBM

Recursividade

Recommended Posts

AJBM

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?

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
AJBM

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

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
AJBM

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

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
AJBM

OK Já percebi. obrigado :thumbsup:

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 by AJBM

Share this post


Link to post
Share on other sites
AJBM

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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
AJBM

ok xD.

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

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
AJBM
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();
}

Share this post


Link to post
Share on other sites
AJBM

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 by AJBM

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.