SexPistolsPT Posted December 11, 2009 at 07:08 PM Report Share #299921 Posted December 11, 2009 at 07:08 PM 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 Link to comment Share on other sites More sharing options...
Betovsky Posted December 11, 2009 at 07:25 PM Report Share #299924 Posted December 11, 2009 at 07:25 PM 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... "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Link to comment Share on other sites More sharing options...
Baderous Posted December 11, 2009 at 07:26 PM Report Share #299926 Posted December 11, 2009 at 07:26 PM Percorrer a árvore de forma "infixa"? Não será antes "fazer uma travessia inorder"? Link to comment Share on other sites More sharing options...
SexPistolsPT Posted December 11, 2009 at 07:35 PM Author Report Share #299928 Posted December 11, 2009 at 07:35 PM 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. Link to comment Share on other sites More sharing options...
Baderous Posted December 11, 2009 at 07:41 PM Report Share #299930 Posted December 11, 2009 at 07:41 PM 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. Link to comment Share on other sites More sharing options...
SexPistolsPT Posted December 11, 2009 at 07:47 PM Author Report Share #299934 Posted December 11, 2009 at 07:47 PM E como construo uma árvore a partir de uma lista? Link to comment Share on other sites More sharing options...
Baderous Posted December 11, 2009 at 07:48 PM Report Share #299935 Posted December 11, 2009 at 07:48 PM Fazes uma função que insira um elemento numa árvore. De seguida usas o fold para gerar a árvore a partir da lista. Link to comment Share on other sites More sharing options...
Betovsky Posted December 11, 2009 at 08:06 PM Report Share #299940 Posted December 11, 2009 at 08:06 PM 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? "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Link to comment Share on other sites More sharing options...
SexPistolsPT Posted December 11, 2009 at 08:20 PM Author Report Share #299943 Posted December 11, 2009 at 08:20 PM 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...) Link to comment Share on other sites More sharing options...
Betovsky Posted December 12, 2009 at 01:00 PM Report Share #300008 Posted December 12, 2009 at 01:00 PM 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. "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Link to comment Share on other sites More sharing options...
Rui Carlos Posted December 12, 2009 at 09:03 PM Report Share #300081 Posted December 12, 2009 at 09:03 PM 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. Rui Carlos Gonçalves Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now