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

[Giova411]

Son mancato qualche giorno e devo ancora chiudere qualche Topic passato dove sono stato aiutato molto da Apa e Vic.

Ora volevo iniziare a discutere su un dubbio che mi sta venendo e che sarà un mio problema prossimo....

Quando si parla di alberi che vanno costruiti in tempo "reale" ossia che la struttura viene immessa da tastiere o viene letta da file. Ho sempre visto alberi già formati dove "staticamente" si costruiva root figlio destro poi sinistro e compagnia bella (lavorando di puntatori)

Per costruirlo di volta in volta e sottoporre quindi alberi diversi ad un algoritmo come si fa? Forse è una domanda stupida, ma che consigli potete darmi?

Mi spiego con un esempio.. Una "interview" di google chiedeva il Lowest Common Ancestor (LCA Problem).
Problema classico, ad esempio:
http://www.geeksforgeeks.org/lowest-com ... ree-set-1/

Io vorrei sottoporre alberi diversi, magari scritti in file di testo, che il programma legge e forma di volta in volta.
Non voglio una cosa scritta così:

    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

Vorrei una cosa flessibile che "capisca" come formare l'albero usando un ciclo al massimo.
Ossia se nel file.txt abbiamo
-------------------------------------------------------------
7
1 2
1 3
2 4
2 5
3 6
3 7
-------------------------------------------------------------
Possiamo pensare che la prima riga contiene n, ossia il numero di nodi totale.
Le successive n-1 contengono, ciascuna, una coppia padre / figlio.
Ecco, avere una 20 di file del genere, tutti diversi tra loro, generano 20 alberi diversi. Giusto?
Vorrei capire come scrivere del codice flessibile che legga e formi, in modo intelligente, queste strutture.

[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

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[nota]per ogni albero[/nota]).

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:

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.

[Giova411]

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