Binary Treeler Hakkinda

03/Oca/13 20:12

Kısayol

Şikayet

Özel Mesaj

ataturkcu1

Kayıt Tarihi: 20/Nisan/2007

Hocalar merhaba,

Binary treeler hakkinda duzgun bir kaynak verebilir misiniz?Googledan arastirdim genellikle OOP mantigiyla anlatilmis,bana struct haliyle lazim.Nasil yeni bir node eklenir,nasil bir node bulunur vs bunlar gerekiyor.

Pragmatism&Realism

Alıntı yap

03/Oca/13 21:08

Kısayol

Şikayet

Özel Mesaj

Tugberk

Kayıt Tarihi: 04/Ekim/2009

Binary search tree örneği istiyorsun anladığım kadarıyla. En doğal uygulaması özyinelemeli fonksiyonlar ile, ancak döngüsel de yazılabilir aynı kolaylıkta.

Biraz incelersen anlayacağını düşünüyorum. Yoketme fonksiyonunu yazmadım sadece ekleyen ve bulan fonksiyonları yazdım, ayrıca sadece bu değil tüm veri yapıları için handle yöntemi uygulamak daha kullanışlıdır bu şekilde tek pointer üzerinde işlem yapmaktan ancak en kısa kod en kolay anlaşılan koddur diyerek böyle yazdım kolay gelsin.

Biraz açıklama,

Öncelikle binary search treede eleman eklenirken kullanılan tek kural küçük olan eleman sola, büyük olan eleman sağa eklenir, mesela mevcut node 75 ise, 77 sağa, 65 sola eklenir. her node ayrıca sağ ve sol nodu gösteren bir pointer a sahiptir, mesela bir node un sağ pointer ı NULL ise, orada eleman yok demektir, eleman olmayan yöndeki pointer NULL olur kısacası.

Treenin herhangi bir parçasını alırsan o da bir treedir, yani her hangi bir node u root kabul edersen, alt tree yi elde edersin. bu yüzden ekleme ve arama işlemleri hep özyineleme ile yapılır, sonraki fonksiyona alt tree yollanır, alan fonksiyon tabiki bunu root olarak bilir ve işlem yapar.

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;
	char *name;
	struct node *left;
	struct node *right;
} Node;

Node* insert(Node *treep, Node *newp)
{
	if (treep == NULL) {
		return newp;
	}
	
	if (newp->value > treep->value) {
		treep->right = insert(treep->right, newp);
	} 
	else if (newp->value < treep->value){
		treep->left = insert(treep->left, newp);
	} 
	else {
		printf("Duplicate entry ignored: %d\n", newp->value);
	}
	return treep;
}

Node* lookup(Node *treep, int value)
{
	if (treep == NULL) {
		return NULL;
	}
	
	if (value == treep->value) {
		return treep;
	} 
	else if (value > treep->value) {
		return lookup(treep->right, value);
	} 
	else {
		return lookup(treep->left, value);
	}
}

Node* newnode(int value, char *name)
{
	Node *newp = calloc(1, sizeof(Node));
	if (newp == NULL) {
		fprintf(stderr, "Out of memory");
		exit(1);
	}
	
	newp->value = value;
	newp->name = name;
	return newp;
}

int main()
{
	Node *tree = NULL;
	Node *testNode = NULL;
	
	tree = insert(tree, newnode(77, "root"));
	insert(tree, newnode(55, "dogan"));
	insert(tree, newnode(66, "ozgur"));
	insert(tree, newnode(88, "cancan"));
	insert(tree, newnode(99, "ahmet"));
	
	testNode = lookup(tree, 55);
	
	if (testNode) {
		printf("Value: %d  Name: %s\n", testNode->value, testNode->name);
	}
	getchar();
	return 0;
}

Tugberk tarafından 03/Oca/13 21:29 tarihinde düzenlenmiştir

Alıntı yap

03/Oca/13 23:14

Kısayol

Şikayet

Özel Mesaj

erngnctrk

Kayıt Tarihi: 10/Eylül/2012

http://www.erengencturk.com.tr/files/trees.jar

veri yapılarında iyiişime yaramıştı mantığını anlama konusunda.

.

Alıntı yap