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

tree iterator

Question

¿Cómo hago 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 contenga tipos de índices arbitrarios, optimizados para la búsqueda y una buena 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, eliminación logarítmica, espacio lineal. Internamente, a menudo se implementan como árboles rojo-negro, aunque eso no es una garantía. Sin embargo, como usuario de STL, todo lo que debe preocuparse son las garantías de rendimiento de los algoritmos y las estructuras de datos de STL. Ya sea que se implementen como árboles o como pequeños hombres verdes no deberían importarle.

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

Answer 1

¿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 contenga tipos de índices arbitrarios, optimizados para la búsqueda y una buena 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, eliminación logarítmica, espacio lineal. Internamente, a menudo se implementan como árboles rojo-negro, aunque eso no es una garantía. Sin embargo, como usuario de STL, todo lo que debe preocuparse son las garantías de rendimiento de los algoritmos y las estructuras de datos de STL. Ya sea que se implementen como árboles o como pequeños hombres verdes no deberían importarle.

Como nota al margen, no existe la función raíz (). Todos los contenedores STL tienen la función begin () implementando el principio conceptual de un contenedor. El tipo de iterador devuelto por esa función depende de las características del contenedor.

Answer 2

Aquí está tree.hh que 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 que 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 navegar por el árbol, como el tamaño del árbol, por ejemplo.

También asumo que no quería almacenar la raíz en todos los nodos por razones de rendimiento. Entonces, si quiere implementarlo a su manera, le sugiero que mantenga la mayor parte de la lógica y agregue el enlace al árbol padre en el iterador y vuelva a escribir agregue un poco.