Binarno stablo

[GrimReaper]

Potreban mi je algoritam/pseudo-kod/C++ kod koji prolazi (jednom) kroz sve čvorove dinamičkog (tj, realizovanog uz pomoć lančanih lista) binarnog stabla. Hvala unapred.

[chaami]

Ne znam da li sam te dobro razumeo ali meni izgleda da ovde treba samo rekurzija.

pozoveš funkciju Prolazak() i predaš joj prvi čvor kao argument.

Prolazak(čvor)
{ ako čvor ima levo dete pozovi Prolazak(levo_dete)
ako čvor ima desno dete pozovi Prolazak(desno_dete)
return}

tako se prolazi kroz sve elemente binarnog stabla.

[pyost]

Samo treba obratiti paznju na slucaj kada je stablo prazno, posto ce u tom slucaju pri prvom pozivu dobiti null pointer exception.

[GrimReaper]

Hm, nisam siguran da razumem ovo dobro. Koji je redosled prolaska kroz čvorove u ovom slučaju (može, recimo na primeru nekog stabla sa 3-4 nivoa)? Najbolje što sam ja uspeo je da obuhvatim možda nekih pola čvorova u jednom prolazu, tj, jednoj petlji. Imajte u vidu da je jedini način za prelazak na sledeći čvor kod dinamičkog vezivanja, nesto tipa node = node->left ili node = node->right.

[chaami]

Šta ti ovde nije jasno (nisi precizirao), ali ajde da probam ponovo da ti objasnim.
Nemam predstavu kako izgleda tvoj kod ali da zamislimo jedan čvor kao strukturu

struct TreeNode 
{      int data;         // neki podatak      
       TreeNode *left;   // pokazivač na levi čvor
       TreeNode *right;  // pokazivač na desni čvor 
}

Sve što ti treba da uradiš je da proveriš (ko što ti reče pyost) da li uopšte ima čvorova u listi i ako ih ima da pozoveš funkciju Prolazak(TreeNode *root)
Ono root ti je prvi čvor a sama funkcija izgleda ovako:

void Prolazak( TreeNode *root ) 
{     
       if (root->left)Prolazak(root->left);     
       if (root->right)Prolazak(root->right);
       // ovde možeš da uradiš nešto sa čvorom
       return; 
}

Za svaki čvor funcija će biti pozvana jednom.
Ako i dalje ne razumeš onda jedino da staviš ovde svoj kod pa da probamo na njemu ili da ti objasni neko ko je bolji u objašnjavanju.
Ja bolje ne umem

[Belphegor]

Treba da proverava samo root pokazivac da li je null:

void rekurzija(Tree* root)
{
    if(0 != root)
    {
        // ovde radis na trenutnom pokazivacu
        rekurzija(root->lef);
        rekurzija(root->right);
    }
}

edit:Nasao sam ti primer.

[chaami]

Belphegor kaže:

Treba da proverava samo root pokazivac da li je null:

void rekurzija(Tree* root)
{
    if(0 != root)
    {
        // ovde radis na trenutnom pokazivacu
        rekurzija(root->lef);
        rekurzija(root->right);
    }
}

edit:Nasao sam ti primer.

Verovatno si hteo da kažeš da može da proverava samo root a ne da treba.
Kako god, sad ima dva primera pa će valjda lakše da shvati.

[Belphegor]

Treba jer ostali rekurzivni pozivi funkcije proveravaju left i right koji su u stvari root na tom "nivou", ako me razumes posto ne umem ni ja bas da objasnjavam.

[chaami]

Belphegor kaže:

Treba jer ostali rekurzivni pozivi funkcije proveravaju left i right koji su u stvari root na tom "nivou", ako me razumes posto ne umem ni ja bas da objasnjavam.

U stvari si ti u pravu. Nisi napisao da mora tako već da bi trebalo. Onaj primer što si našao mi je odavno poznat i služi za prebrojavanje elemenata stabla. Pravi školski primer kako treba da se uradi. Sa druge strane čovek kaže da mu nije jasno i čak je zamolio ako može da mu se nacrta. Zato je to kod mene malo drukčije urađeno. Naglašeno je proveravanje čvorova.

@GrimReaper tebi je sve jedno šta ćeš od ovoga koristiti. Nadam se da ti je pomogao bilo koji primer. Ovaj drugi primer možda čak i deluje optimizovanije jer ima samo jednu proveru u petlji. Sa druge strane on će za svaki krajnji čvor pozvati rekurziju još dva puta u prazno.

[GrimReaper]

Ok, hvala na pomoći, uspeo sam da uradim ono što sam hteo. U suštini, moj zadatak je bio da prebrojim listove stabla, a mislio sam da to uradim na ovaj način. No, na internetu sam našao elegantnije rešenje.

int countLeaves(BTnode<T> *p)
	{
		if (p == NULL)
			return 0;
		else if (p->left == NULL && p->right == NULL)
			return 1;
		else
			return countLeaves(p->left) + countLeaves(p->right);
	}

Opet se primenjuje rekurzija, ali malo je bolje od onoga što je meni palo na pamet (nešto slično kao ono što je Belphegor napisao), a i pucao mi je program sa dve rekurzije:

void traverse(BTnode<T> *p)
          {
                 l = p->left;
                 r = p->right;
                 while (p != NULL)
                 {
                        traverse(l);
                        traverse(r);
                 }
          }

(BTnode je klasa čvora)