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

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 ser capaz de crear y manipular árboles de esta manera:

#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 índice arbitrarias, optimizado para la búsqueda y bueno en la inserción y luego considerar usando un mapa.

Un mapa es un contenedor asociativo que tiene garantías de rendimiento idénticas a las de un árbol: logarítmica de búsqueda, inserción logarítmica, deleción logarítmica, espacio lineal. Internamente, a menudo se implementan como árboles rojo-negro, aunque eso es no es una garantía. Sin embargo, como usuario de STL , todo lo que debe tener en cuenta son las garantías de rendimiento de los algoritmos y las estructuras de datos de STL . Si están implementados como árboles o los pequeños hombres verdes no deberían importar .

No estoy seguro de 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

Aquí está tree.hh que está un poco cerca de lo que quiere 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 anexar 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. Así que 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.

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 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.