Como fazer uma árvore em C++?

Question

Como fazer uma árvore de estrutura de dados em C++ que usa os iteradores em vez de ponteiros?Eu não poderia encontrar qualquer coisa em STL que pode fazer isso.O que eu gostaria de fazer é ser capaz de criar e manipular árvores como essa:

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

    tree<int>::iterator i = myTree.root();
    *i = 42;

    tree<int>::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

---

Obrigado, árvore.hh parece ser apenas o que eu estava procurando.

Se esta é para a obtenção do benefício de dados-estrutura de detenção arbitrária tipos de índice, otimizado para a pesquisa e bom para a inserção, em seguida, considerar usando um mapa.

Um mapa é um container associativo que tem garantias de desempenho idêntico para aqueles de uma árvore:logarítmica a pesquisa, logarítmica de inserção, logarítmica exclusão, o espaço linear.Internamente, eles são muitas vezes implementadas como a red-black trees, apesar de que é não é uma garantia.Ainda assim, como STL usuário tudo o que você deve se preocupar é o as garantias de desempenho da STL de dados e algoritmos-estruturas.Se eles são implementados como árvores ou homenzinhos verdes não importa para você.

Eu não tenho certeza se um mapa é o que eu preciso, mas obrigado pela informação.Me lembro de usar o mapas, sempre que possível, em vez de implementar árvores.

Answer 1

Aqui é árvore.hh o que é um pouco perto do que você quer fazer, apesar de um pouco diferente.

Aqui é um pedaço de código extraídos a partir do seu site.

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

Agora, o que é diferente?Sua implementação é mais simples quando se trata de acrescentar um nó da árvore.Apesar de sua versão é indiscutably mais simples, o dev deste lib provavelmente queria ter algumas informações acessíveis sem necessidade de navegar na árvore, tais como o tamanho da árvore, por exemplo.

Eu também supor que ele não deseja armazenar o arquivo de raiz em todos os nós para o desempenho razão.Então, se você quiser implementar seu jeito, eu sugiro que você mantenha a maior parte da lógica e adicionar o link para o pai árvore no iterador e reescrever acrescentar um pouco.

Answer 2

Por que você iria querer fazer isso?Se isto é para fins de aprendizagem, em seguida, você pode escrever sua própria árvore de estrutura de dados.Se esta é para a obtenção do benefício de dados-estrutura de detenção arbitrária tipos de índice, otimizado para busca e bom na inserção, em seguida, considere o uso de um mapa.

Um mapa é um container associativo que tem garantias de desempenho idênticos aos de uma árvore:logarítmica pesquisa, logarítmica de inserção, logarítmica exclusão, o espaço linear.Internamente, eles são freqüentemente implementados como vermelho, preto árvores, apesar de que não é uma garantia.Ainda assim, como STL usuário tudo o que você deve se preocupar é a garantias de desempenho do STL de dados e algoritmos-estruturas.Se elas são implementadas como árvores ou pequenos homens verdes não importa para você.

Como uma nota lateral, não existe tal coisa como uma raiz de() função.Todos os contentores STL tem o begin() função de execução conceitual início de um recipiente.O tipo de iterador retornado por essa função depende das características do recipiente.