Jump to content
Hercles

árvore binária na ordem de seus nívies..

Recommended Posts

Hercles

Caros, estou com esta questão: Descreva um algoritmo que percorra os nós de uma árvore binária na ordem de seus nívies. (pode se utilizar uma fila com estrutura). Já tentei assim:

se ponteiro.esquerdo diferente de vazio então pos(ponteiro.esquerdo)

se ponteito.direito diferente de vazio então pos(ponteiro.direito)

Mas eu acho que não esta errado porque uma árvore binaria na ordem de seus niveis segue de cima para baixo e da esquerda pra direita... é isso?

Share this post


Link to post
Share on other sites
Warrior

Mostra (pseudo-)código do que estás a tentar.

Não percebo o que queres dizer com "pos(ponteiro.esquerdo)".

Share this post


Link to post
Share on other sites
Hercles

pos(ponteiro.esquerdo) seria uma função recursiva. mas que eu não estou conseguindo escrever...

Share this post


Link to post
Share on other sites
HappyHippyHippo

o que tu queres está descrito no link que apresentei, que por milagre tem a solução em pseudo-código !!!


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Hercles

verdade estou vendo agora... Estou com dificuldade para explicar como ocorre....

1  procedure BFS(G,v) is
2      create a queue Q
3      create a set V
4      enqueue v onto Q
5      add v to V
6      while Q is not empty loop
7          t ← Q.dequeue()
8          if t is what we are looking for then
9              return t
10         end if
11         for all edges e in G.adjacentEdges(t) loop
12             u ← G.adjacentVertex(t,e)
13             if u is not in V then
14                  add u to V
15                  enqueue u onto Q
16             end if
17         end loop
18     end loop
19     return none
20 end BFS

Edited by thoga31
Tags code

Share this post


Link to post
Share on other sites
HappyHippyHippo

a única diferênca entre esse código e o que tens de implementar é que esse é uma pesquisa e tu tens de "encontrar" todos os nós


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Hercles

este linha eu posso colocar assim => while Q is not empty loop => Enquanto Q λ do

Share this post


Link to post
Share on other sites
thoga31

aqui na minha universidade eles consideram o lambida como vazio em pseudo-código.

Lambda, não lambida.

Pois, é que o lambda representa no geral as chamadas funções lambda. Aliás, em Haskell pode-se mesmo usar o símbolo para criar funções deste género:

λx -> -- função


Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

ora deixa ca ver as definições/simbolos de vazio que conheço:

- um circulo cruzado com uma barra vertical ascendente a 45 graus da esquerda para a direita

- zero

- 0

- {}

- []

- nulo

- conjunto de todos os elementos que não pertence ao infinito ?

agora lambda nunca tinha ouvido falar ...

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Hercles

Aparte em vermelho não consigo enteder...

create a queue Q => CRIA UMA FILA EM Q

create a set V => CRIA UM CONJUNTO EM V

enqueue v onto Q => ENFILEIRA V EM Q

add v to V => ADICIONA V A v

while Q is not empty loop = ENQUANTO Q NÃO FOR VAZIO FAÇA

t ← Q.dequeue()

if t is what we are looking for then

return t

end if

for all edges e in G.adjacentEdges(t) loop

u ← G.adjacentVertex(t,e)

obs. do Lambda
Isto deve ser tipo problema de matemática... O aluno faz a questão e diz: Seja x = 0... Ai no caso, seja Lambda = vazio...  deve ser pra facititar a escrita.

Edited by Hercles

Share this post


Link to post
Share on other sites
thoga31

Seja lambda = vazio... ok. Então como será com a função lambda? "Seja Pinóquio = função lambda", suponho?

</offtopic>


Knowledge is free!

Share this post


Link to post
Share on other sites
thoga31

Não entendo o que você quer dizer.

Não te preocupes, foi uma epifania que me deu.

Quanto ao que não consegues perceber no pseudocódigo, o que achas que é "dequeue"?


Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

de|queue

- qual o significado da palavra "queue" e o seu significado em termos computacionais

- qual o significado do prefixo "de" na língua inglesa ?


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

×
×
  • Create New...

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.