Bolu Beyi tarafından yazıldı Aralık - 26 - 2010 3 Yorum

Bugün veri yapıları dersinde görmüş olduğumuz konu olan c# üzerinde ağaç yapıları ile ilgili yazı paylaşmak istedim. Ağaç yapılarına, hiyerarşik yapıda düğümlerin(node) bulunduğu sonlu düğümler kümesidir diyebiliriz. Kök(root) düğüm dışındaki tüm düğümler de aynı zamanda her biri alt ağaç olarak adlandırılan ağaç özelliğinde küme oluşturabilirler. Her ağaç kümesi düğümlerden ve kenarlardan(edge) oluşur. Her node bir veriyi tutar. Kenarlar da iki ayrı düğümü birbirine bağlar. Her ağaç mutlaka kökten oluşur. Ve çocuk node’lara sahip olabilir, bu çocuk node’lara aynı zamanda leaf(yaprak) de denir. Seviye(level), alta doğru düşündüğümüzde iki node arasındaki mesafedir. Mesela resimde görmüş olduğunuz ağaç yapısının seviyesi 2’dir.

İkili ya da binary tree yapısını birçoğunuz duymuşsunuzdur. Özellikle aramalarda kullanılır. Bu tür ağaç yapılarında kök olarak adlandırılan özel bir düğüm vardır. Her düğüm en fazla iki düğüme bağlıdır. Kök dışında her düğüm bir daldan gelmektedir. Tüm düğümlerden yukarı doğru çıkıldıkça kök düğüme ulaşılır.  Yukarıda seviyeden(level) bahsetmiştim, Derinlik ise seviyeden bir fazla olur. Yani resimdeki ağaç yapısının
derinliği 3’tür. Full binary tree’de her yaprak aynı derinliğe sahiptir.Yaprak olmayan düğümlerin tümünün iki çocuğu olmalıdır. Bir full binary tree n adet yaprağa sahipse 2n-1 adet node olması gerekmektedir. Eğer herhangi bir ağacın her bir düğümü hiç bir çocuğa sahip değilse veya iki çocuğa sahipse bu ağaç yapısı proper binary tree olarak adlandırılır. Yani bu yapıda tek çocuk olmaz.

Dengeli(balanced) binary tree, yüksekliği ayarlanmış ağaç yapılarıdır. Bütün düğümler için sol alt ağacın yüksekliği ile sağ alt ağacın yüksekliği arasında en fazla bir fark varsa bu dengeli ağaç olarak adlandırılır.

Ağaçların sıralanış şekli:

Preorder(ön ek), kök-sol-sağ.
İnorder(iç ek), sol-kök-sağ.
Postorder(son ek), sol-sağ-kök.
Sıralama yapacağımız zaman; preorder isteniyorsa, ağaç yapısına bakılır, önce kök yazılır daha sonra sol ve sağ taraf taranır. İnorder ve ve postorderda da yapacağımız işlemler benzerdir. Örnek olarak resimdeki ağaç yapısını inorder’a göre sıralayacağımız zaman şu şekilde sıralarız: D-B-E-A-F-C-G

İkili arama ağacı silme işleminde 3 farklı durum vardır. Eğer silenecek node, yapraksa silme işlemi gerçekleştirilir. Silinecek olan node çocuğa sahipse o düğümün işaretçi bilgisi o düğümün atasına yani parent’ına aktarılması gerekmektedir. Bunun işlem için iki yol vardır. Silinen düğüm yerine o düğümün sağ alt ağacındaki en küçük değerli düğüm getirilir. Veya silinen düğüm yerine sol alt ağacın en büyük değerli düğümü getirilir. Şimdi aşağıda bir örnek paylaşacağım, kod açıklamalarını kabataslak bir şekilde yanlarında belirttim.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace bolubeyi.net
{
class Node
{
public int? veri;//Normalde değişkene “null” değeri atayamadığımız için, int’in yanına “?” koyduk.
public Node RightNode, LeftNode;// İki adet düğüm tanımladık.
public Node(int? veri, Node LeftNode, Node RightNode)//Yapıcı metodumuzu oluşturduk.
{
this.veri = veri;
this.LeftNode = LeftNode;
this.RightNode = RightNode;
}
}
class uygulama
{
static void ekle(int veri, Node root)//Ekleme işlemi için yeni bir node oluşturduk ve önce root ekledik.
{
Node yeniNode = new Node(veri, null, null);
if (root == null)
{
root.veri = veri;
}
else//Burada da eklediğimiz kökün sağına ve soluna yeni bir node ekledik.
{
Node current = root;
Node parent;
while (true)
{
parent = current;
if (veri < current.veri)
{
current = current.LeftNode;
if (current == null)
{
parent.LeftNode = yeniNode;
break;
}
}
else
{
current = current.RightNode;
if (current == null)
{
parent.RightNode = yeniNode;
break;
}
}
}
}
}
static void preOrder(Node node)://Burada; preorder, postorder, inorder’a göre listeleme yaptık.
{
Console.WriteLine(node.veri);
if (node.LeftNode != null)
preOrder(node.LeftNode);
if (node.RightNode != null)
preOrder(node.RightNode);
}
static void postOrder(Node node)
{
if (node.LeftNode != null)
{
postOrder(node.LeftNode);
}
if (node.RightNode != null)
{
postOrder(node.RightNode);
}
Console.WriteLine(node.veri);
}
static void inOrder(Node node)
{
if (node.LeftNode != null)
{
inOrder(node.LeftNode);
}
Console.WriteLine(node.veri);
if (node.RightNode != null)
{
inOrder(node.RightNode);
}
}
static void sil(int veri,Node node)
{
Console.WriteLine(“————sil————“);
while (node.RightNode == null)
{
Console.WriteLine(node.LeftNode);
}
}
static void Main(string[] args)
{
Node root = new Node(null, null, null);//main fonksiyonumuz içerisinde de ekleme işlemlerini yaptık.
ekle(15, root);
ekle(10, root);
ekle(35, root);
ekle(20, root);
ekle(45, root);
ekle(43, root);
ekle(47, root);
Console.WriteLine(“———–postorder—————–“);
postOrder(root);
Console.WriteLine(“———–inorder—————–“);
inOrder(root);
Console.WriteLine(“———–preorder—————–“);
preOrder(root);
}
}
}
Ağaç yapıları ile ilgili örneğimiz bu kadar. Silme işlemini önümüzdeki hafta paylaşmayı düşünüyorum, bugünlük bu kadar yeter diyelim. Tekrar görüşmek üzere…

Bugüne kadar 3 yorum yapıldı

  1. azat tekçe dedi ki:

    süper olmuş elinize sağlık

  2. bolubeyi dedi ki:

    Teşekkür ederim.

  3. Kodcu dedi ki:

    Teşekkürler paylaşım için, çok işime yaradı:)


Time limit is exhausted. Please reload CAPTCHA.