¿Cómo hacer un árbol en C++?

Question

¿Cómo creo una estructura de datos de árbol en C++ que utiliza iteradores en lugar de punteros?No pude encontrar nada en el STL que pueda hacer esto.Lo que me gustaría hacer es poder crear y manipular árboles como este:

#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;
}

---

Gracias, tree.hh parece ser justo lo que estaba buscando.

Si esto es para obtener el beneficio de una estructura de datos que contiene tipos de índices arbitrarios, optimizados para buscar y buenos en la inserción, considere usar un mapa.

Un mapa es un contenedor asociativo que tiene garantías de rendimiento idénticas a las de un árbol:Búsqueda logarítmica, inserción logarítmica, deleción logarítmica, espacio lineal.Internamente a menudo se implementan como árboles rojos-negro, aunque eso no es una garantía.Aún así, como usuario de STL, todo lo que debe preocuparse es la garantía de rendimiento de los algoritmos STL y las estructuras de datos.Si se implementan como árboles o pequeños hombres verdes no deberían importarle.

No estoy seguro de si lo que necesito es un mapa, pero gracias por la información.Recordaré utilizar mapas siempre que sea posible en lugar de implementar árboles.

Answer 1

Aquí está arbol.hh Lo cual está un poco cerca de lo que quieres hacer, aunque un poco diferente.

Aquí hay un fragmento de código extraído de su sitio web.

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;
         }
      }
   }

Ahora ¿qué es diferente?Su implementación es más simple cuando se trata de agregar un nodo al árbol.Aunque su versión es indiscutiblemente más simple, el desarrollador de esta biblioteca probablemente quería tener alguna información accesible sin explorar el árbol, como el tamaño del árbol, por ejemplo.

También supongo que no quería almacenar la raíz en todos los nodos por motivos de rendimiento.Entonces, si desea implementarlo a su manera, le sugiero que mantenga la mayor parte de la lógica y agregue el enlace al árbol principal en el iterador y reescriba append un poco.

Answer 2

¿Por qué querrías hacer eso?Si esto es para fines de aprendizaje, entonces puede escribir su propia estructura de datos de árbol.Si esto es para obtener el beneficio de una estructura de datos que contiene tipos de índice arbitrarios, optimizados para la búsqueda y buenos para la inserción, entonces considere usar un mapa.

Un mapa es un contenedor asociativo que tiene garantías de rendimiento idénticas a las de un árbol:búsqueda logarítmica, inserción logarítmica, eliminación logarítmica, espacio lineal.Internamente, a menudo se implementan como árboles rojo-negro, aunque eso no es una garantía.Aún así, como usuario de STL, lo único que debería importarle son las garantías de rendimiento de los algoritmos y las estructuras de datos de STL.No debería importarle si se implementan como árboles o como pequeños hombres verdes.

Como nota al margen, no existe la función root().Todos los contenedores STL tienen la función comenzar() que implementa el comienzo conceptual de un contenedor.El tipo de iterador devuelto por esa función depende de las características del contenedor.