Arbore binar

[•nedster88]

Am si eu o prblema la crearea unui arbore binar in C. VArianta mea este urmatoarea:

Cod:

struct nod {
  int info;
  struct nod *st, *dr;
};
typedef struct nod *pnod;
pnod prim;

void creare(pnod p)
{
  int x; scanf("%d", &x);
  if (x)
  {
    p->info = x;
    creare(p->st);
    creare(p->dr);
  }
    else
  p = NULL;
}

In main() fac apelul creare(prim). Stiu ca nu e bine pt ca prim ar trebui transmis prin referinta, insa prim este de tip pnod, adica reprezinta o adresa. Cum sa fac? SAu ce varianta de creare si definitie a unui binary tree se foloseste in general?

[•Dastas]

Poti sa faci fara sa te complici cu pointeri, cu un singur vector, sa zicem un vector A.

A[1] va fi radacina, A[2] si A[3] vor fi fiii.

In caz general, fiii unui nod A[k] sunt A[2*k] si A[2*k + 1]. Parintele unui nod A[k] e A[k/2]. Mai multe detalii gasesti aici: http://en.wikipedia.org/wiki/Binary_tree

[•wefgef]

Merge asa?

Cod:

void creare(nod *&p)

Metoda cu vectorul nu este indicata, deoarece e mare consumatoare de memorie (2^n).

[•devilkind]

Metoda cu vectorul nu este indicata, deoarece e mare consumatoare de memorie (2^n).

depinde de arbore. Daca arborele e echilibrat cat de cat atunci memoria e mai putina. Intradevar dak ai un lant in care fiecare nod se duce in dreapta atunci memoria e 2^n dar dak ai sa zicem un arbore de intervale memoria folosita e cam 2*nr de noduri ale arborelui

[•svalentin]

mai bine iti faci functia altfel, ea primeste ca parametru doar valoarea nodului ce urmeaza afi inserat (sau nu primeste nici un parametru si citeste valoarea cu scanf) si apoi returneaza nodul nou. ex:

Cod:

pnod* creare()
{
  int x=0; scanf("%d", &x);
  if (x)
  {
    // alocam memorie pentru nod
    pnod* p = (pnod*) malloc(sizeof(pnod));

    // umplem nodul cu informatie
    p->info = x;
    p->st = creare();
    p->dr = creare();
  }
  else p = NULL;
  return p;
}

Functia, apelata din programul principal, returneaza un pointer la radacina arborelui.
Dar in structura ta a programului ai o problema, arborele va fi cat se poate de debalansat - toate elementele vor avea doar fiu stang, caci in recursivitate acela se apeleaza primul (dar va fi un arbore binar )
Depinde acum cum vrei sa construiesti arborele, poate vrei sa aiba anumite proprietati (gen fiul stang sa fie mai mare ca tatal si fiul drept mai mic ca tatal). In cazul acesta iti sugerez sa faci 2 functii: una care creeaza un nod si alta care adauga un nod in arbore. (La creere, nodul are fii NULL)

Daca te uiti, in codul tau original nu alocai nicaieri memorie pentru fii, aveai doar pointeri la ei

PS: codul e scris direct in fereastra, nu e testat, sper ca nu am gresit la sintaxa

[•MarcvsHdr]

O alta problema la implementarea cu vectori este ca spre deosebire de heap, de exemplu, arborele nu este compact. Altfel spus, e posibil ca A[10] sa reprezinte un nod de arbore, iar A[9] sa nu existe. Si te costa in plus sa tii minte nodurile existente, oricum.

Eu folosesc alocare dinamica mereu. Stiu ca e mai lent lucrul cu pointeri, dar dupa mine, apar mai putine erori dupa ce te inveti. Pentru un arbore binar, fac asa:

typedef struct NOD {INFORMATIE a; NOD *stga,*drta;};

unde INFORMATIE e un tip de date (poate fi si int). Deasemenea, recomand puternic cand lucrezi cu alocare dinamica sa faci functii speciale pentru acces la structura. De exemplu, insert(x); delete (x);, etc...

Daca ai timp, cel mai bine e sa faci clase, dar merge si cu functii clasice, in mod special la concursuri unde nu ai timp.

Si nu uita, "NOD *a;" nu inseamna ca ai memorie alocata pentru a.

[•Darth_Niculus]

  Cel mai bine e sa te ghidezi in functie de situatie. Daca ai memorie si n-ai timp e mai bine sa folosesti vector.... daca ai timp si n-ai memorie poate o sa preferi cu alocare dinamica...