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

[Giova411]

Apa il problema che trovo difficilissimo ora (dico prima di migliorare secondo quanto dici) è generare alberi binari casuali!!!
Voglio testare con tanti input... Anche per poi provare a migliorare la soluzione attuale.
Nodi non devono ripetersi mentre devo gestire le direzioni D, S, SS, SSD, DD, et etc
Oddio è da paura!!!! Che consigli?
Produre un milione di alberi che si chiudono, ciascuno, con ()
Ogni albero magari può, che ne so, arrivare a contenere mille nodi....

Codice:

(9,) (4,D) (19,S) (10,SS) ()
(9,) (4,D) (19,S) (10,SD) etc ()
(9,) (4,D) (19,S) (10,DS) etc etc ()
(9,) (4,D) (19,S) (19,DD) etc etc etc ()


[Giova411]

QUI MI SA CHE HO BISOGNO DI UNA GROSSA SPINTA APA

Creare robe "CASUALI" del genere.. Ma tante

Codice:

4 2
(3,D) (191,SS) (90,S) (2,DDS) (1272,) (4,SSD) (14,DD) ()
(,) ()
(11,SS) (7,SSS) (8,D) (5,) (4,S) (13,DS) (2,SSD) (1,DDD) (4,DD) ()
(3,S) (4,D) (2,) ()
(22,) (33,S) (44,SS) (2,D) (4,SD) ()
(22,) (44,S) (2,D) (4,SD) ()
(11,SS) (2,SSS) (8,D) (142,S) (4,SD) (390,) ()
(4,SDS) (22,SD) (2,SSS) (8,D) (6,S) (904,) (811,SS) ()
(11,SS) (7,SSS) (8,D) (5,) (4,S) (13,DS) (2,SSD) (1,DDD) (4,DD) ()
(2,S) (4,D) (420,) ()
(11,SS) (4,SSS) (8,D) (1085,) (42,S) (13,DS) (92,SSD) (1,DDDS) (14,DD) (2,DDD) ()
(5,) (4,S) (13,DS) (5,S) (6,D) ()
(2,) (4,S) ()
(3,) (2,D) (4,S) ()
(4,SS) (3,S) (2,) (6,D) ()
(2,S) (22,SD) (220,) (4,D) ()
(3,D) (191,SS) (90,S) (2,DDS) (122,) (4,SSD) (14,DD) ()


Con risultato:

Codice:

1272
Albero non corretto
4
2
22
22
142
6
4
420
1085
Albero non corretto
2
3
2
220
122

[apatriarca]

Il consiglio te l'ho già dato qualche post fa. Ho in effetti praticamente descritto l'algoritmo.

[Giova411]

Sono un frignone incapace!
Mi son messo e non riesco a stampare l'albero che voglio.
Genero i nodi a caso e poi vorrei avere l'albero completo ma non riesco con le variabili bool che dicono se è a sinistra o destra.

al livello 2^1 dovrei avere S=0 e D=1
al livello 2^2 quindi i rami 00, 01, 10, 11

al livello 2^3 avrò 000, 001, 010, 011, 100, 101, 110, 111 e così via.

Vedo un pattern che non riesco a programmare
In questo caso non voglio i rami casuali ma solo i nodi e poi strutturare l'albero completo. L'idea non mi sembra malaccio.

Codice:

#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;

int
main (void)
{
  vector < int >v (15); //albero da 15 nodi
  int r = rand () % 21 + 1;
  ofstream out ("file.txt");
  srand (time (NULL));
  v[0] = r;
  out << "(" << r << ",) ";   //radice
  bool ripeti = false;
  for (int i = 0; i < 15; i++)   
    {
      r = rand () % 21 + 1;   
      for (int c = 0; c < i; c++)   
   {
     if (v[c] == r)
       {         
         ripeti = true;   
         c = i;      
       }
   }

      if (ripeti == true)      
     i = i - 1;
      else
   {         
     v[i] = r;      
   }
      ripeti = false;      
    }
  string S = "S";
  string D = "D";
  int k = 1;
  string s1 = "";
  string d1 = ""; 
  bool primo = true;
  bool dividi = false;
  for (int u = 0; u < 14; u++)
    {   
     //qui devo stampare e dare sinistra o destra ai nodi ma mi incasino
    }
  out << "()" << endl;
 
  return 0;
}


[Giova411]

Vorrei fare questo:
http://www.researchgate.net/profile/Erk ... 000000.pdf


http://www.cs.otago.ac.nz/staffpriv/mik ... yTrees.pdf
Ma mi dovrò arrendere

[apatriarca]

Perché dovresti arrenderti? Io penso che tu ti stia in qualche modo complicando la vita. Ci sono tre problemi distinti nella generazione di un albero casuale:
1. Generazione della topologia dell'albero
2. Assegnazione casuale delle chiavi all'interno dell'albero
3. Scrittura del file nel formato desiderato
Ogni sottoproblema può essere risolto in totale autonomia rispetto agli altri e ti consiglio di affrontarli separatamente.

[Giova411]

Allora il problema non è più stampare l'albero e generarlo. Anche se non è banale (almeno per me)
Il problema che trovo è che voglio stamparlo con le direzioni di sinistra S e destra D.
Queste stringhe mi fanno uscire pazzo!
Se scegliessi di stamparlo così:
(10 ()( 1 ( 5 ()() ) ( 2 ( 3 ()() ) ( 8 ()() ) ) ) )
Avrei molti meno problemi

[apatriarca]

E allora perché non lo stampi così? In ogni caso puoi sempre mantenere una stringa che tiene conto del percorso fatto per arrivare ad uno specifico nodo e stampare di volta in volta quella stringa.

[Giova411]

E allora perché non lo stampi così? In ogni caso puoi sempre mantenere una stringa che tiene conto del percorso fatto per arrivare ad uno specifico nodo e stampare di volta in volta quella stringa.

Esatto!!! E' questo che non riesco!!!! Mi viene da picchiarmi sul capoccion!!!!! Poi faccio il frignone così --->

[Giova411]

Apa Mio..
Ma è nella struct dell'albero (dove definisco i nodi) che mi consigli di tener traccia di una stringa che inizia come string "" e, man mano, poi si "allarga", ma in modo corretto, sommando le varie direzioni casuali ossia i cari caratteri "SDSSD" etc etc.
Supponendo di non andare a creare più di 100 nodi, per ciascun BT, la stringa dovrebbe essere fattibile. Lo so che è un po' da macellaio ma mi sono impuntato.... Il nodo radice sarà, ad esempio: (4,) quindi la stringa rimane "". Diciamo che, in questo esempio abbiamo due nodi figli: (4,) (10,S) (2,D) ()
In questo esempio la string del nodo 10 è cresciuta ""+"S"; la string del nodo 2 anche ""+"D"