İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme Nasıl Yapılır?

İkili ağaç, her düğümünde en fazla iki düğüm bağlı olan ağaç yapısıdır. İkili arama ağacı ise kök düğümün solunda kökten küçük değerlerin, sağında ise kökten büyük değerlerin sıralandığı araçtır.

İkili ağaç, rekürsif(özyineli) bir yapıdadır. İkili ağaçlara Directed Acyclic Graph(DAG) ismi de verilmektedir.

Aynı sayıları farklı sıralarda eklersek farklı ikili arama ağaçları oluşur.

Ağaçta dolaşmak için infix, prefix ve postfix stratejileri bulunur.

infix-> LNR, RNL -> Sol-Kök-Sağ veya Sağ-Kök-Sol
prefix -> NLR, NRL -> Kök-Sol-Sağ veya Kök-Sağ-Sol
postfix -> LRN, RLN -> Sol-Sağ-Kök veya Sağ-Sol-Kök

Şadi Evren ŞEKER’in anlatımındaki İkili Arama Ağacı’nda Ekleme, Arama, Dolaşma, En Küçük Eleman Bulma, En Büyük Eleman Bulma, Silme yapan kod aşağıdadır:

#include <stdio.h>
#include <stdlib.h>
struct n{
	int data;
	n * sol;
	n * sag;
};
typedef n node;
node * ekle (node *agac,int x){
	if(agac == NULL){
		node *root= (node *)malloc(sizeof(node));
		root -> sol = NULL;
		root -> sag = NULL;
		root -> data = x;
		return root;
	}
	
	if(agac->data < x){
		agac->sag = ekle(agac->sag,x);
		return agac;
	}
	agac->sol = ekle (agac->sol,x);
	return agac;
}
void dolas(node *agac){
	if(agac == NULL)
		return;
	printf("%d ",agac->data);
	dolas(agac->sag);
	dolas(agac->sol);
}
int bul (node * agac,int aranan){
	if(agac == NULL)
		return -1;
	if(agac->data == aranan)
		return 1;
	if(bul(agac->sag,aranan)==1)
		return 1;
	if(bul(agac->sol,aranan)==1)
		return 1;
	return -1;
}
int max(node *agac){

	while(agac->sag!=NULL)
		agac=agac->sag;
	return agac->data;
}
int min(node *agac){
	while(agac->sol!=NULL)
		agac=agac->sol;
	return agac->data;
}
node * sil(node *agac,int x){
	if(agac==NULL)
		return NULL;
	if(agac->data == x){
		if(agac->sol==NULL && agac->sag==NULL)
			return NULL;
		if(agac->sag!=NULL){
			agac->data = min(agac->sag);
			agac->sag = sil(agac->sag, min(agac->sag));
			return agac;
		}
		agac->data = max(agac->sol);
		agac->sol = sil(agac->sol,max(agac->sol));
		return agac;
	}	
	if(agac->data < x){
		agac->sag = sil(agac->sag,x);
		return agac;
	}
	agac->sol= sil(agac->sol,x);
	return agac;
	

}
int main(){
	node * agac=NULL;
	agac=ekle(agac,56);
	agac=ekle(agac,200);
	agac=ekle(agac,26);
	agac=ekle(agac,190);
	agac=ekle(agac,213);
	agac=ekle(agac,18);
	agac=ekle(agac,28);
	agac=ekle(agac,12);
	agac=ekle(agac,24);
	agac=ekle(agac,27);
	dolas(agac);	
	printf("arama sonucu: %d",bul(agac,24));
	printf("max = %d min = %d",max(agac),min(agac));
	agac= sil(agac,56);
	dolas(agac);
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir