[c++]Dubbio su costruzione dinamica di Alberi in>> da file di testo

[apatriarca]

Immagino che per stampare l'albero tu segua un qualche tipo di visita dell'albero. Durante la visita dell'albero seguirai un qualche tipo di percorso. Ogni volta che scegli di visitare l'albero destro o sinistro dovresti aggiungere una lettera alla stringa. Ogni volta che torni da un nodo figlio a uno genitore dovresti invece eliminare tale lettera.

[apatriarca]

Immagino che per stampare l'albero tu segua un qualche tipo di visita dell'albero. Durante la visita dell'albero seguirai un qualche tipo di percorso. Ogni volta che scegli di visitare l'albero destro o sinistro dovresti aggiungere una lettera alla stringa. Ogni volta che torni da un nodo figlio a uno genitore dovresti invece eliminare tale lettera.

[vict85]

Il particolare modo in cui fai l'input permette di calcolare l'LCA senza neanche generare l'albero.

Per semplificare cambio la tua notazione eliminando caratteri inutili. Supponiamo di avere

Codice:

10 1 D 3 S 14 DD 15 SS 19 SSD 27 DDS 17 DDD Q

(il Q è inutile, basterebbe un \n)
A questo punto vuoi trovare il LCA di 17 e 27. A questo punto cerchi nella stringa la sottostringa 17 e la sottostringa 27, quindi estrai la successiva parola (DDD e DDS rispettivamente) quindi confronti le due stringhe e ricavi che DD è la sottostringa comune. A questo punto cerchi DD nella stringa e torni indietro per trovare che (14, DD) è l'elemento che cerchi. Ovviamente se l'albero ha 1000 nodi la stringa da considerare sarà molto grande (penso che 600000 elementi siano sufficienti¹).

In ogni caso le lettura dal file è l'operazione più lunga che devi fare.

Detto questo 1000 nodi penso che te lo generi anche un semplice generatore ricorsivo. Stessa cosa per la stampa:

Codice:

typedef struct _tN
{
   int value;
   struct _tN* left;
   struct _tN* right;
} treeNode;

typedef struct
{
   int size;
   treeNode *first;
} tree_s;

void print_tree(tree_s const tree)
{
   if (tree.first != nullptr)
   {
      std::string POS{};
      print_subtree(tree.first, POS);
   }
   else
   {
      std::cout << "L'albero e' vuoto";
   }
   std::cout << std::endl;
}

void print_subtree(treeNode *node, std::string &POS)
{
   if (node != nullptr)
   {
      std::cout << "(" << node->value << ", " << POS << ") ";
      if (node->left != nullptr)
      {
         POS.push_back('S');
         print_subtree(node->left, POS);
         POS.pop_back();
      }

      if (node->right != nullptr)
      {
         POS.push_back('D');
         print_subtree(node->right, POS);
         POS.pop_back();
      }
   }

}

Ovviamente te lo stampa in modo ordinato.

---

Note

1. per ogni albero ↑

[Giova411]

E te dove spunti?!?!?!?
Mitico VIC!!!!!