Binary Search Tree'de Genişlik Bulma Sorunu

[LayZee]

Arkadaşlar BinarySearchTree'nin en çok elaman olan kademesinin elaman sayısını bulmam gerekiyor. Nasıl anlatayım :garip:

http://www.imgloadtr.com/pics/aca41035095c6695489f975721df328a.jpg

Bu resimdeki tree'de mesela tree'nin genişliği 4 çünkü 3. kademede 4 eleman var ve en fazla olan o.

Bunun için bir algoritma kuramadım. İterative yapmayı düşündüm ama imkansız gibi duruyor. Recursive'de de algoritmayı kuramadım. Aklına herhangi bir düşünce gelen paylaşırsa çok mutlu olurum.

[acehreli]

Recursive (ozyinelemeli) yaparken kacinci duzeyde oldugun bilgisini de yollasan, her durumda hangi duzeyde oldugunu bilmis olursun.

Bir dizide de her duzeydeki dugum sayisi tutulsa, boylece o duzeye karsilik gelen dizi elemaninin degerini bir arttirabilirsin.

On sonunda da diziyi tarayip en fazla uyenin hangi elemanda oldugunu bulabilirsin.

Ali

[tujix]

void say(TreeNode* nodePtr){ if (nodePtr != NULL){ i++;j++;dizi[j]=i; say(nodePtr-> leftPtr); j++;dizi[j]=i ; say(nodePtr->rightPtr); bu sekilde agaci hem dolasir hemde diziye kacinci basamkta oldugunu ve o basamakta kac tane o basamaga ait uye oldugunu ogrenebilrsin. basamak sayisi =n olsun basamagin eleman sayisi 2 ^(n-1) dizideki en buyuk elemani bulup o elemanin basamaginda bulunmasi gereken eleman sayisiyla kiyaslayarak genisligi bulabilrsin...

[ortug]

@ tujix
Yazdığınız kodda i ve j değeri devamlı arttırılıyor.
Şu şekilde olabilir:

void width(TreeNode* nodePtr, int nodePtrDepth)
{
if (nodePtr != NULL)
{
dizi[nodePtrDepth]++;
width(nodePtr-> leftPtr, nodePtrDepth + 1);
width(nodePtr-> rightPtr, nodePtrDepth + 1);
}
}

dizi'nin yeterli alanının olmasına dikkat ediniz, veya vector kullanınız.

[sigmund]

@Tujix in ki dizinin genişliğini bulur sadece dizinin tutabileceği eleman sayısı çok büyük olursa sorun çıkarır bunuda pointer larla halleder.Ama @ortuğ un ki dizinin eleman sayısını bulur genişliğini değil.
Yada ben anlayamadım @ortuğun kodunu

[ortug]

Anlaşılan yazdığım kodu açıklamam gerekiyor.

//nodePtrDepth : nodePtr node'nun derinliği.
void width(TreeNode* nodePtr, int nodePtrDepth)
{
if (nodePtr != NULL)
{
dizi[nodePtrDepth]++;
width(nodePtr-> leftPtr, nodePtrDepth + 1);
width(nodePtr-> rightPtr, nodePtrDepth + 1);
}
}

Yukarıdaki fonksiyona root node ve 0 verildiğinde, fonksiyon sonlandığında dizi isimli integer dizisinde her derinlikte kaç eleman bulunduğu tutulmakta. Örnek vermek gerekirse dizi[3] = 5 ise, 3. seviyede 5 adet node vardır. Bu durumda sorunun çözümü için dizi isimli dizide en büyük elemanı bulmak gerekiyor.
dizi isimli array global bir değişken. Dizinin boyu ağacın derinliğinden küçük olmamalı ve dizinin bütün elemanları 0 olmalı.