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

SexPistolsPT

Árvore Binária

11 mensagens neste tópico

Boa tarde,

estou com um problema na remoção do primeiro elemento de uma árvore binária percorrida de forma infixa.

Isto é, tendo uma árvore binária quero remove apenas o 1º elemento.

iremove :: a -> a
iremove x = ...

Agradeço a ajuda,

Hugo Sousa

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

estou com um problema na remoção do primeiro elemento de uma árvore binária percorrida de forma infixa.

E em concreto qual é o problema que tens? É na parte de percorrer a árvore? É não saber o que é percorrer de forma infixa? É após encontrar o elemento, não o conseguires remover?

Como é que já tentaste resolver?

Normalmente essa é a forma mais fácil de explicar, uma pessoa indicando onde está errado e como poderás corrigir...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Percorrer a árvore de forma "infixa"? Não será antes "fazer uma travessia inorder"?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Percorrer a árvore de forma infixa é Left - Root - Right.

O problema é dada uma arvore, quero remover o 1º elemento da árvore e devolver a árvore sem o 1º elemento.

O meu problema é 1º remover o elemento e depois reconstruir a árvore sem o 1º elemento.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso para mim sempre se chamou travessia inorder. Infixa diz respeito a um tipo de notação.

Para remover o elemento, podes passar a árvore para uma lista fazendo uma travessia inorder, depois removes o elemento da lista e voltas a construir a árvore.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fazes uma função que insira um elemento numa árvore. De seguida usas o fold para gerar a árvore a partir da lista.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso é complicar demasiado.

Penso que basta percorrer a árvore na devida forma e quando não poder percorrer mais (último nodo) então é removê-lo.

Ou estou a ver mal?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas aí temos um problema, não? Se removemos o 1º elemento no fim de percorrer a árvore, os outros elementos deixam de estar ligados já que removemos um dos possiveis nós (que tem filhos...)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. Porque se é o primeiro em inorder, significa que é o nó mais à esquerda na árvore e como tal não tem filhos. É só indicar onde está esse nó que passa a estar vazio.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. Porque se é o primeiro em inorder, significa que é o nó mais à esquerda na árvore e como tal não tem filhos. É só indicar onde está esse nó que passa a estar vazio.

Pode ter um filho. Mas nesse caso também é fácil de resolver o problema, pois é só um.

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