Tweet

Ana Sayfa   Forum   Java Teknolojileri
Yeni Başlık Cevap Ekle
white_bullet Java da binary tree (01/10/2008 02:15)
profil seyhan
 offline OFFLINE
 Junior Coder

Herkese merhaba eğitim yılımız yeni başladığı için şu sıralar biraz yoğunum.
Ama bayram tatilini en iyi şekilde değerlendirmek istedim ve adminimizinde
uyarısını dikkate alıp önce konuyu anlatıp daha sonra kod örneği vermeye karar verdim.
Sizlere ilk anlatacağim veri yapısı ikili ağaç(binary tree) olsun istedim.
İkili ağaç veri yapısı, arama ve sıralama algoritmalarındaki hızı nedeniyle sıkça
kullanılan veri saklama biçimlerinden bir tanesidir. Genel olarak ağaç veri yapıları
başlığı altında incelenir. Bu ağaç veri yapısını diğerlerinden ayıran ilk özellik her
düğümün en fazla 2 tane dal içermesidir. İkinci özellik ise her düğümün bir değer taşımasıdır.
Düğümün dalları arasında tam bir sıralama vardır. Sol daldaki değer düğümden küçük
iken sağ daldaki değer düğümden büyüktür. İkili ağaç veri yapısında, bir değer ancak
ve ancak bir defa ağaca dahil olabilir. Şimdi bunun örnek kodunu verelim.Ben java
öğrendiğim için sizlere Java kod öreneğini vereceğim.Umarım kod örneği
arayan arkadaşlar için iyi bir örnek olur.Ben eminim ki ikili ağaç yapısı bir çok
bil. müh. bölümünde ödev olarak verilmekte galiba bu sene biz de bu ödevle
karşılaşacağiz.Tüm arkadaşlar bu koddan en iyi şekilde yararlansın lütfen.
Herkese kolay gelsin.Bu arada isimlerinden bahsetmekten kendimi alamadığım
yardımlarını benden esirgemeyen site moderatörümüz Oğuz arkadaşıma
ve okuldan Osman Abime ,Dilek Ablama teşekkür ederim.Bol javalı günler.

Saygılarımla.
Seyhan Uçar

CODE:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*********************************
* *
* *
* @author UÇAR *
* Seyhan Uçar *
* *
* *
********************************/


class Node
{
Node left,right;
int id,parentId;
String name;

public Node(int d,String isim)
{
id = d;
name = isim;
parentId = -1;
left = right = null;

}
}

//THİS CLASS CONTAİN METHODS
class BinarySearcTree
{
static BufferedReader k = new BufferedReader(new InputStreamReader(System.in));

//INSERTİON OF NODES TO THE TREE

public static void insert(Node root,Node node)
{
if(((node.name).compareToIgnoreCase(root.name)) < 0)
{
if(root.left ==null)
{
root.left = node;
root.left.parentId = root.id;

}
else
{
insert(root.left,node);
}
}
if(((node.name).compareTo(root.name)) > 0)
{
if(root.right == null)
{
root.right = node;
root.right.parentId = root.id;

}
else
{
insert(root.right,node);

}
}
if(((node.name).compareTo(root.name)) == 0);
{
System.out.print("This element is already exist in tree");
return;

}

}
//DİSPLAY THE NODES İN A LİST FORM
public static void display(Node root)
{
if(root == null)
return;
else
{
System.out.println(root.id + "t"
+root.parentId +"t"
+root.name +"t");
if(root.left != null & root.right != null)

System.out.println(root.left.id +"t"
+root.right.id);
if(root.left == null & root.right !=null)

System.out.println("-1t"+root.right.id);

else
{
if(root.left != null & root.right == null)
System.out.println(root.left.id +"-1");
if(root.left == null & root.right == null)
{
System.out.println("t-1t-1");

}
}


}
display(root.left);
display(root.right);

}

public static void main(String args[])
throws NumberFormatException,IOException
{
int choise = 0,Id = 0 ;
String ad;
Node kok = null;

while(choise != 3)
{
do{
System.out.println("****CHOOSE ONE*******");
System.out.println("****1-ADD NODE**********");
System.out.println("****2-DİSPLAY TREE******");
System.out.println("****3-EXİT**************");
choise = Integer.parseInt(k.readLine());
}while(choise > 3 && choise < 1);

switch(choise){
case 1:
System.out.println("ENTER A NAME TO ADD NODE:");
ad = k.readLine();
if(Id == 0)
{
kok = new Node(0,ad);
kok.parentId = -1;

}
else
{
Node temp = new Node(Id,ad);
insert(kok,temp);

}
Id++;
break;
case 2:
System.out.println(
"IdtP.IdtNtLCtRC");
display(kok);
break;
case 3:
System.exit(0);
}
}
}
}































[IMG SRC="http://img225.imageshack.us/img225/2408/seyhanzt2.jpg" ALIGN="oğuz"]seyhan[/IMG]

Üye Profili

white_bullet Re:Java da binary tree (01/10/2008 05:17)
profil Oguzz
 offline OFFLINE
 Senior Coder

Seyhan öncelikle teşekkürler ancak konuda eksiklik sezdim ben.Tek tek açıklasan daha iyi olur mesela inorder, preorder ,postorder lar veya düğüm isimleri sağ alt ağaç, sol alt ağaç bahsetsen ve detaya insen güzel olur diye düşünüyorum ben şahsen.Tabi konu senin anlatma biçimin senin bileceğin birşey.Ama önerimi dikkate alırsan sevinirim.Kolay gelsin. [IMG SRC="http://www.csharpnedir.com/MImages/btree_1.gif" ALIGN="CENTER"]http://www.csharpnedir.com/MImages/btree_1.gif[/IMG]

just code it!

profil

white_bullet Re:Java da binary tree (01/10/2008 06:49)
profil seyhan
 offline OFFLINE
 Junior Coder

Sen varsın içim rahat ben eksik bıraksam sen tamamlarsın .
Teşekkürler uyarıları tabi ki dikkate alıyorum.Sen zaman bulursan
beni kontrol et ne olur ne olmaz.Kolay gelsin..

Saygılarımla.
Seyhan

[IMG SRC="http://img225.imageshack.us/img225/2408/seyhanzt2.jpg" ALIGN="oğuz"]seyhan[/IMG]

profil

white_bullet Re:Java da binary tree (01/10/2008 07:42)
profil seyhan
 offline OFFLINE
 Junior Coder

Oğuz arkadaşımın uyarısını dikkate alıp konuyu daha detaylı bir şekilde inceleyelim.

Birçok programcının en az bir defa karşısına çıkan yada çıkma olasılığı yüksek bir konu olan Binary Tree (İkili Ağaç)?yi inceleyeceğiz. Ağaç yapısının kullanım alanlarını göz önüne aldığımızda, arama işlemleri, parsing işlemleri, matematiksel ifadelerin uyarlanması ( örneğin a^3 + b * (c - d) gibi ), sıkıştırma algoritmaları, verilerin sıralanması, işletim sistemlerindeki dosya sistemi, oyun programlama, veri tabanı yönetim sitemleri (dbms) ve daha birçok uygulamada sıklıkla kullanılan bir veri yapısı olduğundan bu konu ile karşılaşma olasılığımızın neden çok yüksek olduğunu daha iyi anlayabiliriz.

Ağaç veri yapısını incelemeye başladığımızda yukardaki şekilde de görüldüğü gibi bir çok düğümden (node) oluşmaktadır ve bu düğümler sonlu sayıdadır(örneğin B, F, K ...). Eğer özel bir ağaç modeli oluşturmak istenildiğinde herbir düğümün n tane düğümü olabilir. Kök (root) düğüm (A düğümü) denilen özel bir düğüme sahiptir ve herhangi bir düğümden yukarı doğru çıkıldığında kök düğüme ulaşılır. Kök düğümün sağ tarafındaki daldan oluşan ağaca sağ alt ağaç(D, F), sol tarafındaki daldan oluşan ağaca ise sol alt ağaç(B, C, E, K, L) denir. Bir düğüme bağlanan sağ ve sol düğümlere alt (child) düğüm(B?nin alt düğümleri E ve C dir) denir. Bir düğümün bağlı olduğu düğüme üst (parent) ( K ve L nin parenti E) düğüm denir. Eğer bir düğümün sağ ve sol alt düğümleri yoksa bu tür düğümlere yaprak (leaf) düğüm denir. İki düğüm aynı üst düğüme sahip ise bu iki düğüme kardeş (sibling) düğüm denir. Ağacımızı oluşturan herhangi bir düğümü incelediğimizde, öncelikle bu düğümde tutulacak veri kısmı daha sonra sağ ve sol alt düğümler ile bağlantı oluşturacak göstericilerden oluştuğunu görürüz :C dilindeki gösterimi

CODE:

typedef struct testnode {
int data;
struct testnode* p_left_node;
struct testnode* p_right_node;
/* struct testnode* p_x1_node;*/
/* struct testnode* p_x2_node;*/
/* ... */
}test_Node;


Ağaç veri yapısında, düğüm ekleme ,silme, arama, tüm düğümleri silme, kök düğümü oluşturma ve ağaç düğümlerini dolaşma işlemlerini gerçekleştirebiliriz. Bu işlemleri ikili ağaç veri yapısı üzerinde gerçekleştirelim. İkili ağaç veri yapısında herbir düğümün en fazla 2 adet alt düğümü olabilir. Tabi unutmamamak gerekir ki bir düğüm hiçbir alt düğüme sahip olmayabilir. Aslında ikili ağaçlar daha önceden incelediğimiz bağlı listelerin özel biçimi de diyebiliriz. İkili ağaçların önemli özelliği eğer sıralanırsa çok hızlı bir şekilde ekleme, silme arama işlemlerini yapabilabilmesidir. Ağaç veri yapısı üzerinde işlem yapan fonksiyonların birçoğu kendi kendini çağıran (recursive) fonksiyonlardır. Çünkü bir ağacı alt ağaçlara böldüğümüzde elde edilen her parça yine bir ağaç olacaktır ve fonksiyonumuz yine bu ağaç üzerinde işlem yapacağı için kendi kendini çağıracaktır. İkili ağaç yapısının önemli bir özelliği de düğümlerin yerleştirilmesi sırasında uygulanan işlemlerdir. İkli ağaçlarda kök hücresinden başlayarak, eğer eklenecek düğümün veri kısmındaki değer, kök düğümünün veri kısmındaki değerden büyük ise sağ tarafa , küçük yada eşit ise sol tarafa eklenir.Bu şekilde olşturulan sıralı ikili ağaçta biliriz ki , sol alt ağaçtaki düğümlerde kökten küçük ya da köke eşit değerler, sağ alt ağaçtaki düğümlerde ise kökten büyük değerler bulunur.

Ağaç yapısı üzerinde herhangi bir düğüme erişme sürecimize ağacı gezmek (traverse) denir. Bir ağacı ençok bilinen üç değişik yöntemle gezebiliriz :

1- Sıralı (inorder) : İlk adımda sol alt ağaç sıralı şekilde dolaşılır . Kök düğüme uğranır . Son adımda sağ alt ağaç sıralı şekilde dolaşılır.
2- Kökten Başlayarak (preorder) : İlk adımda köke uğranır. Sol alt ağaç kökten başlayarak dolaşılır. Son adımda sol alt ağaç kökten başlayarak dolaşılır .
3-Sondan Başlayarak (postorder) : İlk adımda sol alt ağaç sondan başlayarak dolaşılır . İkinci adımda sağ alt ağaç sondan başlayarak dolaşılır . Son adımda ise köke uğranır.
Yapacağımız uygulamalarda ağacın sıralı olmasını istemeyebiliriz. Buna karşın birçok uygulamada ağacın sıralı olması gerekliliği ile karşılaşırız. Tabiki bir ağacın sıralı yada sırasız olması ağacın dolaşım şekline göre belirlenir. Sıklıkla kullanılan ağaç şekli sıralı ağaç olduğunda bizde örneklerimizi sıralı ağaç veri yapısı üzerinde gerçekleştireceğiz. Bu nedenle ağacı yapılandırırken, sol alt ağacın kökten küçük veya eşit değerler içerdiğini, sağ alt ağacın ise kökten büyük değerler içerdiğini göz önünde bulundurmalıyız.

Oğuz arkadaşıma bana tavsiyeleri ile yol gösterdiği için çok teşekkür ederim.
Kendisinden site olarak öğreneceğimiz çok şey var.

Herkese kolay gelsin.
Saygılarımla.
Seyhan Uçar



[IMG SRC="http://img225.imageshack.us/img225/2408/seyhanzt2.jpg" ALIGN="oğuz"]seyhan[/IMG]

profil

white_bullet Re:Java da binary tree (01/10/2008 10:41)
profil Oguzz
 offline OFFLINE
 Senior Coder

Şimdi oldu.Bahsettiğim anlatım biçimi tam olarak buydu.Sıfırdan hiç hayatında bu binary tree konularını görmemiş birine anlatıyormuş gibi yazmalıyız eğer yaptığımızın adı ders vermek ise;)Herkezin birbirinden öğreneceği şeyler var buna bende dahilim.Bu yüzden burada değilmiyiz zaten? :)

just code it!

profil
 
1 /
 
Ana Sayfa   Forum   Java Teknolojileri
Yeni Başlık Cevap Ekle
 

MENÜ » FORUM
Menü » Takip et
RSS Facebook Twitter Friendfeed
Sık Kullanılanlar Google Yahoo Live
Menü » Paylaş
E-Posta ile gönder Twitter Facebook Friendfeed
Buzz Stumbleupon Delicious Digg