Jump to content
RecrutaNegro

Gavar arvore binaria em ficheiro

Recommended Posts

RecrutaNegro

boas,

estou a trabalhar com arvores binarias pela primeira vez e tenho duvidas em como grava-las para ficheiro, portanto alguém me pode ajudar mostrando um exemplo de como gravar uma arvore binaria para ficheiro?

fiquem bem :thumbsup:

Share this post


Link to post
Share on other sites
KTachyon

Podes tentar gravar ao estilo do XML, que te permite estruturar convenientemente a árvore no ficheiro.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
RecrutaNegro

sou novo em programação e daqui, será que me podes apontar algum post que mostre a gravação de ficheiro XML?

fica bem :thumbsup:

Share this post


Link to post
Share on other sites
pikax

sou novo em programação e daqui, será que me podes apontar algum post que mostre a gravação de ficheiro XML?

fica bem :)

Acho que o que KTachyon queria dizer era que podias estruturar a gravação no ficheiro de forma parecida ao XML.

A maneira que gravas um XML é a mesma maneira que gravas num TXT.

A minha opinião era criar um ficheiro algo assim do género:

4 //tamanho da arvore
1 //raiz
1 2 //2 nivel
3 4 5 6 //3 nivel
6 7 8 9 10 11 12 13 //4 nivel

*EDIT: enganei-me no exemplo  😳

PS. Já está corrigido :)


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Share this post


Link to post
Share on other sites
KTachyon

Pois, mas assim não consegues garantir que sabes que nós estão ligados a que nós. Com XML não há enganos, ficas com um ficheiro estruturado em àrvore. Podes argumentar que é tudo seguido, mas há casos em que um nível da árvore não está completo.

Penso que não existem bibliotecas de base no C++ para trabalhar facilmente com XML, mas não custa nada ir ao Google, procurar e sacar uma.

http://www.codeproject.com/KB/trace/C___XML_wrapper.aspx


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
pikax

Pois, mas assim não consegues garantir que sabes que nós estão ligados a que nós. Com XML não há enganos, ficas com um ficheiro estruturado em àrvore. Podes argumentar que é tudo seguido, mas há casos em que um nível da árvore não está completo.

Não estou muito dentro do XML, mas a forma que eu dei é simples, dá para saber se eles estão ligados:

4 //tamanho da arvore
1 //raiz
1 2 //2 nivel
3 4 0 6 //3 nivel
6 7 8 9 0 0 12 13 //4 nivel

basta saber em que nível estamos na árvore e em qual é a posição do nó, basta só fazer um calculo simples para a seguinte linha:

Nó_da_esquerda=Nivel_seguinte.posicao(Nivel_Actual.posicao*2-1);

Nó_da_direita=Nivel_seguinte.posicao(Nivel_Actual.posicao*2-1);

Algo assim do género... claro que esta forma é melhor para árvores balanceadas se não for estaremos a desperdiçar tempo a escrever e a ler 0's


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Share this post


Link to post
Share on other sites
Metaluim

Pois, mas assim não consegues garantir que sabes que nós estão ligados a que nós. Com XML não há enganos, ficas com um ficheiro estruturado em àrvore. Podes argumentar que é tudo seguido, mas há casos em que um nível da árvore não está completo.

Penso que não existem bibliotecas de base no C++ para trabalhar facilmente com XML, mas não custa nada ir ao Google, procurar e sacar uma.

http://www.codeproject.com/KB/trace/C___XML_wrapper.aspx

Uma pesquisa no google deu-me este post do stackoverflow:

http://stackoverflow.com/questions/1042855/boost-and-xml-c

Share this post


Link to post
Share on other sites
RecrutaNegro

ok!

Vou começar a ver isso de xml...

Mas pikax, em relaçao ao que dizes.te:

Não estou muito dentro do XML, mas a forma que eu dei é simples, dá para saber se eles estão ligados:

4 //tamanho da arvore
1 //raiz
1 2 //2 nivel
3 4 0 6 //3 nivel
6 7 8 9 0 0 12 13 //4 nivel

basta saber em que nível estamos na árvore e em qual é a posição do nó, basta só fazer um calculo simples para a seguinte linha:

Nó_da_esquerda=Nivel_seguinte.posicao(Nivel_Actual.posicao*2-1);

Nó_da_direita=Nivel_seguinte.posicao(Nivel_Actual.posicao*2-1);

Algo assim do género... claro que esta forma é melhor para árvores balanceadas se não for estaremos a desperdiçar tempo a escrever e a ler 0's

isso nao sera a mesma coisa que estares a escrever todos os nodes no ficheiro, no final de cada node ter um " \n" ou "endl". E depois ao leres tens primeiro um inteiro a dizer quantos nodes tens na árvore e depois utiliza.se um método de ordenação para por a árvore balanceada, não???

fiquem bem :)

Share this post


Link to post
Share on other sites
pikax

Mas pikax, em relaçao ao que dizes.te:

isso nao sera a mesma coisa que estares a escrever todos os nodes no ficheiro, no final de cada node ter um " \n" ou "endl". E depois ao leres tens primeiro um inteiro a dizer quantos nodes tens na árvore e depois utiliza.se um método de ordenação para por a árvore balanceada, não???

Sim se utilizares um método de ordenação da árvore, podes criar uma estrutura para te ajudar a saber a posição correcta de cada nó, por exemplo:

struct loc_node
{
    int nivel;
    int posicao;
};

Depois quando tiveres a criar os nodes ou a grava-los, tens que saber em que nível e a posição do node, claro que esta implementação não é  a mais rápida de ser feira, nem a mais rápida em termos de run-time, por exemplo(é o mesmo exemplo que pôs anteriormente):

4 //tamanho da arvore
1 //raiz
1 2 //2 nivel
3 4 0 6 //3 nivel
6 7 8 9 0 0 12 13 //4 nivel

Eu aqui separei cada node com um espaço, e estou a considerar que o node o valor seja um int, claro que se tiver-mos outras informações teremos que fazer manipulações de strings, por exemplo

//imaginemos que queremos criar uma árvore de uma hierarquia numa empresa (inventei )

struct loc_node
{
    int nivel;
    int posicao;
};

struct node
{
string nome;
string cargo;
int idade;
string informacoes_adicionais;
        loc_node posicao;
};

3//tamanho da arvore  -> é um bocado relativo se tivermos a árvore for dinâmica
(Carlos_Rodrigues,Big_Boss,19,none) //o node será separado por () e lá dentro estará os campos ordenados
                                                       //nome, cargo, idade, informacoes_adicionais, respectivamente.
                                                      //cada campo separado por virgulas, e se houver algum espaço por um "_"(underscore) se precisarmos
                                                      //para quando procurarmos só irmos buscar uma string
(Angelina,Consultora_de_finanças,21,muito_boa_profissionalmente) (Hugo_Costa,Gerente_Geral,25,Muito_Rabugento)
(António,Contabilista,22,none) (none) (Norberto,Gerente,18,none) (Feliz_Berto,Gerente_Limpezas,45,none)
(Luis,Estafeta,17,rapido) (none) (none) (none) (Alex,trabalhador,17,none) (none) (Adriano,Homem_das_Limpezas,16,none) (none)

/*Exemplo um bocado mais claro e um bocado diferente, não meti as informações todas, só o nome para saber quem-é-quem  
3
(Carlos_Rodrigues)
(Angelina) (Hugo_Costa)
(António) (none) ; (Norberto) (Feliz_Berto)
(Luis) (none) ; (none) (none) ; (Alex) (none) ; (Adriano) (none)

/*Graficamente ficava assim*/
   Carlos Rodrigues
      /		 \
Angelina	Hugo Costa
/		  /	 \	
  Antonio	   Norberto  Feliz Berto
    /		      /		 /	
Luis 		  Alex	       Adriano	
*/ 

Algo assim do género, mas não é muito pratico.


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Share this post


Link to post
Share on other sites
KTachyon

Em XML podes gerar uma árvore, tal e qual como tens a árvore. Ou então podes criar os nós com IDs em que escreves o ID do nó pai:

<tree>
    <node id=1>
        <name>A</name>
        <value>10</value>
    </node>
    <node id=2 father_id=1>
        <name>B</name>
        <value>9</value>
    </node>
    <node id=3 father_id=1>
        <name>C</name>
        <value>11</value>
    </node>
    <node id=4 father_id=2>
        <name>D</name>
        <value>8</value>
    </node>
    <node id=5 father_id=3>
        <name>E</name>
        <value>12</value>
    </node>
</tree>


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

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.