Veri Yapıları - Ders Notu - Süper

4. İKİLİ ARAMA AĞACI
Düğüm geçişi
void preorder(node* r)
{
if (r!=NULL)
{ cout<<r->data<<" ";
inorder(r->l);
inorder(r->r);
}
}
Önce kök değer yazdırılır,
Ardından LDR formunda
Diğer değerler yazdırılır.
4. İKİLİ ARAMA AĞACI
Düğüm geçişi
Recursive olarak inOrder
Uygulanmıştır.
4. İKİLİ ARAMA AĞACI
Düğüm geçişi
Ağaç kökten incelemeye
Başlansa dahi önce
yazdırılan değer en soldaki
Daha sonra ortadaki
en sonda ise sağdakidir.
Örnek 1
Aşağıdaki listelerden ikili arama ağaçları inşa
ediniz.
–
–
10 4 7 12 16 20 30 5 2 26 15
24 12 89 4 32 50 10 6 36 79 5 9 11
Örnek 2
Aşağıdaki ağacı; inorder, postorder, preorder
için diziniz
Örnek 3
Aşağıda preOrder
yöntemine göre
ekleme yapılmıştır
diğerlerine göre de
siz ekleyiniz.
Hafta 10
Düğüm arama
Sayma
–
–
Tek/çift
Yaprak düğüm
Toplama
–
Tek/çift
Yükseklik
Düğüm silme
1. DÜĞÜMÜN ARANMASI
node* search(node* &r, int data)
{
if (r==NULL)
return NULL;
else
if (r->data==data)
return r;
else
if (data<r->data)
return search (r->l,data);
else
if (data>r->data)
return seach(r->r,data);
}
1. DÜĞÜMÜN ARANMASI
H3
100
node* search(node* &r, int data)
{
if ( (r==NULL) || (r->data==data) )
return r;
else
if (data<r->data)
return search (r->l,data);
H20
H40
H20
H40
else
if (data>r->data)
return seach(r->r,data);
}
80
120
NULL NULL
NULL NULL
Node* S=search(r,80)
What does S stand for?
2. DÜĞÜMLERİN SAYILMASI
int count(struct tnode *p)
Without Recursion
{
if( p == NULL)
With Recursion
return(0);
else
if( p->lchild == NULL && p->rchild == NULL)
return(1);
// yaprak düğümlerin kontrolü
else
return(1 + (count(p->lchild) + count(p->rchild)));
// yaprak olmayan düğümlerin kontrolü
}
2. DÜĞÜMLERİN SAYILMASI
int count(struct tnode *p)
{
if( p == NULL)
return(0);
else
return(1 + (count(p->lchild) + count(p->rchild)));
}
Null olan düğümlere kadar gidilir (bir öncekinden bir adım daha fazla)
3. Bütün düğümlerin toplanması
int sum(node *p)
{
if( p == NULL)
return(0);
else
return( p->data+sum(p->l)+sum(p->r) );
}
Düğüm sayma mantığı ile aynı, tek değişen 1 yerine düğümün değeri ekleniyor
4. ÇİFT DEĞERLİ DÜĞÜMLERİN
SAYILMASI
int counteven(node* r)
{
if (r!=NULL)
if (r->data%2==0)
return 1+ counteven(r->l)+counteven(r->r);
else
return counteven(r->l)+counteven(r->r);
else
return 0;
}
5. ÇİFT DEĞERLİ DÜĞÜMLERİN
DEĞERİNİN TOPLANMASI
int counteven(node* r)
{
if (r!=NULL)
if (r->data%2==0)
????????????????????
else
????????????????????
else
return 0;
}
6. Yaprak düğümlerin sayılması
int countleaf(node* r)
{
if (r!=NULL)
if (r->l==NULL && r->r==NULL)
return 1;
else
return countleaf(r->l)+countleaf(r->r);
else
return 0;
}
6. Sadece 1 tane evladı olan
düğümlerin sayısı
int count1child(node* r)
{
if (r!=NULL)
if (????????????????????????????)
return 1+count1child(r->l)+count1child(r->r);
else
return count1child(r->l)+count1child(r->r);
else
return 0;
}
Cevap!!!
if ((r l==NULL && r r!=NULL) || (r l!=NULL && r r==NULL))
Burada XOR mantığı çalıştırılmalıdır.
6. İki evladı olan düğümlerin sayısı
int count2child(node* r)
{
if (r!=NULL)
if (????????????????????????)
return 1+count2child(r->l)+count2child(r->r);
else
return count2child(r->l)+count2child(r->r);
else
return 0;
}
Cevap!!!
if ((r l!=NULL && r r!=NULL))
Her iki dal da NULL olmamalıdır.
7. Bir düğümün yüksekliği
int Height (node* n)
{
if(n==NULL) return 0;
else return 1+max(Height (n->l)),
Height (n->r));
}
Height (n l) ve Height(n r) n==NULL olana kadar işletilir,
Bu işletim sonunda çıkan değerlerden maksimum olanı ağacın yüksekliğidir.