Ağaçlar/Trees, verilerin birbirlerine bağlanmasıyla oluşturulan, ağaç yapısına benzer bir yapıya sahip veri modelleridir.

Ağaç Yapısını İnceleyelim..

• Bir ağacın her bir elemanına node/düğüm denir.
  • Veriler node’larda tutulur.

• Düğümler birbirlerine edge/kenar/dal ile bağlanır.
  • Bu bağlantılar iki node arasındaki ilişkiyi gösterir

• Düğümler ağaca seviyeler oluşturacak şekilde yerleştirilirler, yani ağaçlar hiyerarşik bir yapıya sahiptir.

• Bu hiyerarşik yapının en tepesindeki düğüm; root/kök,

• En ucundaki, çocuğu olmayan düğümler; leaf/yaprak,

• Çocuğu olan düğümler; parent/ebeveyn, çocuklar ise child/çocuk olarak adlandırılır.

• Bir düğümün alt ağaçlarına subtree denir.

 

 

• Aynı parent’a sahip düğümler birbirlerinin sibling/kardeş node’larıdır.

• Bir düğümden köke kadar izlenen yoldaki diğer tüm düğümler, o düğümün ancestor/atalarıdır.

• Bir düğümün çocuklarına bağlı olan tüm düğümler, o düğümün descendant/torunlarıdır.

• Bir düğüme ulaşmak için üzerinden geçilen düğümler listesine path/yol/iz denir.

• Düğümün depth/derinliği, o düğümden kök düğüme kadar olan yolun uzaklığıdır. (Kök düğümünün derinliği 1 kabul edilerek örnekleme yapılacaktır).
  • Bir ağacın derinliği kök düğümün en uçtaki yaprak düğüme olan uzaklığıyla ölçülür.

• Düğümün height/yüksekliği, o düğümden kendisiyle ilişkili en uzak yaprak düğüme kadar giden yolun uzunluğudur.

• Düğümün level/düzey/seviyesi, kök ve ilgili düğüm arasında bulunan düğümlerin sayısına eşittir. ( Bu yazı için kök düğümün düzeyi 1 kabul ederek örnekleme yapılacaktır)

• Bir node’un degree/derecesi, çocuk sayısına eşittir.

• Ağaçlar döngü/cycle içermezler.

• Bir ağacın hiç düğümü yoksa, boş/empty tree olarak adlandırılır. 🙂

Ne Öğrendik ?

Şekildeki ağacı aşağıdaki tabloda inceleyelim;

	Root ( M )	E	R
Derece/Çocuk Sayısı	2	1	0
Düzey	1	3	4
Derinlik	1	3	4
Ebeveyn/Parent	–	K	S
Kardeş	–	L	T
Ata	–	M	P, M
Çocuk	K, P	C	–
Path	M	M, K, E	M, P, S, R

Binary Tree / İkili Ağaçlar 

Binary/İkili ağaç yapısında bir node’un en fazla iki çocuğu vardır. Bu çocuklar sağ ve sol olarak adlandırılır.

• Full Binary Tree; Yapraklar hariç her bir node’un iki çocuğu olmak zorundadır ve dolayısıyla tüm yaprakları aynı derinliktedir.

• Complete Binary Tree ; Her bir yeni derinliğe düğümler soldan sağa doğru eklenir ve bir derinlik tamamlanmadan bir sonraki derinliğe geçilmez.
  • Her node iki tane çocuğa sahip olmayabilir ve bazı yapraklar arasında derinlik farkı olabilir. Bu nedenle bir complete tree, full binary tree özelliği taşımayabilir.

• Yapraklar arasındaki derinlik farkı en fazla 1’dir.

Complete Binary Tree

Not full and complete tree

• Balanced Binary Tree ; Her bir düğümün sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasında en çok 1 fark olmalıdır.
  • Complete Binary Tree’ler aynı zamanda Balanced Binary Tree’dir ancak tam tersi durum her zaman doğru değildir.

Ağaç Üzerinde Nasıl Dolaşırım ?

Ağaç üzerindeki gezinme/traversal işlemi tüm düğümlere uğrayarak gerçekleştirilir. Doğrusal veri modellerinden farklı bir yapıya sahip olan ağaçları dolaşmak için kullanılan bir kaç algoritma örneği verirsek;

• Pre-order Traversal (root-left-right)
  • Kökü ziyaret et
  • Sol alt ağacı dolaş
  • Sağ alt ağacı dolaş
• In-order Traversal (left-root-right)
  • Sol alt ağacı dolaş
  • Kökü ziyaret et
  • Sağ alt ağacı dolaş
• Post-order Traversal (left-right-root)
  • Sol alt ağacı dolaş
  • Sağ alt ağacı dolaş
  • Kökü ziyaret et

 

 

 

Pre-order   : F, B, A, D, C, E, G, I, H

In-order     : A, B, C, D, E, F, G, H, I

Post-order : A, C, E, D, B, H, I, G, F

 

 

 

• Level-order Traversal (Breadth-first)
  • Kökü ziyaret et
  • Soldan sağa ağacı dolaş

 

 

Level-order : F, B, G, A, D, I, C, E, H

 

 

Expression Tree / İfade Ağaçları 

• Matematiksel işlemlerin ağaca aktarılmış halidir.
• Yapraklar her zaman değişken ya da sabit değerler alır.
• Parent node’lar işlem operatörlerini tutar.
• In-order traversal normal işlem düzenini sağlarken (infix), Pre-order prefix, Post-order ise postfix sonuçlar verir.
• En son yapılacak işlem root node’unda tutulur.

 

 

 

infix     : (a+b) *c + 7

prefix   : +*+abc7

postfix : ab+c*7+

 

Yararlandığım Kaynaklar :  

1. Veri Yapıları Ders Notlarım 🙂
2. ÇU Veriyapıları Ders Notları
3. Tree Traversal
4. Binary Expression Tree – Wikipedia
5. KU Veri Yapıları Ders Notları