#include<stdlib.h>
#include<conio.h>
//avl node tanımlanması
struct node
{
int key;
struct node *left;
struct node *right;
int height;
};
int adim;
int node_sayisi;
int bulundu;
//verilen nodun yüksekliğini bulan fonksiyon..
int height_calculate(struct node *node)
{
if (node == NULL)
return 0;
return node->height;
}
//iki sayının büyüğünü bulan fonksiyon.....
int max(int a, int b)
{
return (a > b)? a : b;
}
struct node* newNode(int key)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
struct node *rightRotate(struct node *b)
{
struct node* a=b->left;
struct node* subtree2=a->right;
//döndürme yapılıyor...
a->right=b;
b->left=subtree2;
a->height=max(height_calculate(a->left),height_calculate(a->right))+1;
b->height=max(height_calculate(b->left),height_calculate(b->right))+1;
return a;
}
struct node *leftRotate(struct node *a)
{
struct node* b=a->right;
struct node* subtree2=b->left;
//döndürme ...
b->left=a;
a->right=subtree2;
a->height=max(height_calculate(a->left),height_calculate(a->right))+1;
b->height=max(height_calculate(b->left),height_calculate(a->right))+1;
return b;
}
int getBalance(struct node *r)
{
if (r == NULL)
return 0;
return height_calculate(r->left) - height_calculate(r->right);
}
struct node* insert(struct node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
node->height = max(height_calculate(node->left), height_calculate(node->right)) + 1;
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inOrder(struct node *root)
{
if(root != NULL)
{
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
}
void display(){
printf("1.EKLE\n");
printf("2.LISTELE(INORDER)\n");
printf("3.ARAMA \n");
printf("4.ORTALAMA ADIM SAYISI\n");
printf("5.CIKIS\n\n");
printf("SECIMINIZ: \n\n");
}
void count_node(struct node *root){
if(root!=NULL){
node_sayisi++;
count_node(root->left);
count_node(root->right);
}
}
struct node *search(struct node *root,int aranan){
if(root==NULL) return NULL;
if(aranan<root->key) {adim++;
return search(root->left,aranan);
}
else if(aranan>root->key){ adim++;
return search(root->right,aranan);
}
else
adim++;
return root;
}
int InternalPathLength(struct node *root,int level){
if(root==NULL) return 0;
return level+InternalPathLength(root->left,level+1)+InternalPathLength(root->right,level+1);
}
int main()
{
struct node *root = NULL;
int sec;
while(1){
printf("\n\n");
display();
scanf("%d",&sec);
if(sec==1){int sayi;
printf("sayı giriniz:");
scanf("%d",&sayi);
root=insert(root,sayi);
}
if(sec==2) {
inOrder(root);
}
if(sec==3){
int aranan;
printf("\n\n Aranacak sayı:");
scanf("%d",&aranan);
adim=0;
if(search(root,aranan)==NULL) printf("\n\nkayit bulunamadı...\a\a\n\n");
else{
printf("\n\nkayit %d adimda bulundu...\n\n",adim);
}
}
if(sec==4){
node_sayisi=0;
count_node(root);
printf("\n\nnode sayisi=%d ",node_sayisi);
printf("\n\nInternal path length=%d\n\n",InternalPathLength(root,1));
printf("ORTALAMA ADIM SAYISI:%f dir\n\n",(float)InternalPathLength(root,1)/node_sayisi);
}
if(sec==5) break;
}
printf("cikis yapiliyor.. cikmak icin tusa bas");
getch();
}
