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

ZNez

[RESOLVIDO] Arvores binarias

6 mensagens neste tópico

Boas, estava a ver uns exercicios na net sobre travessias em arvores binarias, quando encontro o seguinte exemplo:

        A

    /       \

  B        C

/         /  \

D        E   F

\       /   \

  G    H    I

Com a seguinte solucao:

pre-ordem: A B D G C E H I F

em ordem : D G B A H E I C F

pos-ordem: G D B H I E F C A

Duvida: - os metodos d pre-ordem e em ordem nao estao errados?

a minha resolucao seria:

pre-ordem: A B D G C E H F I

em ordem: D B G A H E C I F

qualquer ajuda, desde ja obrigado :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Repara que o I é o "filho" direito do E, e não o esquerdo do F.

        A

    /       \

  B          C

/          / \

D          E   F

\        / \

  G      H   I

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E na em ordem tu passas pela esquerda do D, desces pela esquerda a um imaginário e sobes pra passar por baixo do D e depois tens de descer pro G. Nao podes subir pro B e dps vir ca abaixo ao G. Aconselho a criares ramificaçoes com x (nao valem nada) para fazeres as passagens.

              A

          /          \

      B              C

    /    \          /    \

  D      x        E      F

  /  \    /  \      /  \    / \

x  G  x  x    H  I  x  x

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Repara que quando é pre ordem tu assinalas o nó na primeira vez em que chegas a ele. Ao fazeres o contorno da árvore pela esquerda (A -> B -> D -> G ...), chegarás ao E e passarás no H e logo a seguir no I e só depois voltas para cima, passando no F.

Não sei se deu para perceberes melhor.

Edit: Bom já tinhas percebido. Mas como já tinha tido o trabalho de escrever a msg, posto na mesma, pode ser que sirva a mais alguém. :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora