package binarysearchtree;
import java.util.NoSuchElementException;
/**
*
* @author ASUS
* @param <T>
*/
//psotta en altta oluyo sout
//(pre de sout left right die gidio
//inordeda arada oluyo syste.out .pritnln
public class BinarySearchTree<T extends Comparable<T>> {//generic degerlein karsılastırması için comparable extends ettik
//generic iki nesnenin biriniryle karsılasıtmeak isitoysak extends etcez ,asagıda kıllancaz
//tree node larıdan olusur
//alt nodelara chield üst nodelara paretn denir
//binary serach tree root tan başlar
//en fazla 2 node child olur binary search de
Node root;//binary serach treenin tek özlliği bu ,linked listteki head gibi ;
//binary srach tree de recursive metodlar
//while larla da dönülrama recursive daha matıklı
void insert(T value)//roota eşitmleemzsen,yeni olusturdugun nood havada kalıyor
{
root = insert(value, root); //mainden value ile beraber rootta göndercez
//kullanıvı value girsin
}
private Node insert(T value, Node root)//sadec bunu yaprsan kullanıcıdan tree istiyomus gibi oluyosun //yukardaki metod daha iyi
{
if (root == null)//yukardaiiburda ekleme yapılıyo ,ekleeme yeri ise else iflerde belirleniyor * tmm
{
root = new Node(value); //root nullsa altta eleman yoktur ,value root olcak
} else if (value.compareTo(root.data) < 0)//value rootun datasından küçükse osoluna eklicek
//compareto ,sözlük sıorası gibi , büyüse pozitif deger eşitse 0 ,küçükse – deger döndürür
//içine value eklenmiş
//ekle ekleniş halini rootun lefti ne tekrar ata
{
root.left = insert(value, root.left);
} else {
root.right = insert(value, root.right);
}
return root;
}
boolean isComplete()
{
return isComplete(root);
}
boolean isComplete(Node root)
{
if (root==null) {
return true;
}
if (root.left!=null && root.right==null || root.right!=null && root.left==null)
return false;
return true && isComplete(root.left) && isComplete(root.right);
}
void printInOrder()//kuşşlanıcı ubunu cagprsın biz alltkini calıstırcaz hani
{
printInOrder(root);
}
//inorder ortada kök demek
int nodeCount()
{
return nodeCount(root);
}
int nodeCount(Node root)
{
if (root==null)
return 0;
return 1+nodeCount(root.left)+nodeCount(root.right);
//nodum var elimde soluyla sagını to
}
void printInOrder(Node root)//yazdıralım dedik
//sol cocuk root sag cocuk
{
if (root != null) {
printInOrder(root.left);
System.out.println(root.data);
printInOrder(root.right);
}
}
void printPreOrder() {
printPreOrder(root);
}
void printPreOrder(Node root)//yazdıralım dedik
//kök sol sag
{
if (root != null) {
System.out.println(root.data);
printPreOrder(root.left);
printPreOrder(root.right);
}
}
void printPostOrder() //sonra köke ugra idi sol-sağ-ebeveyn
{
printPostOrder(root);
}
void printPostOrder(Node root)//yazdıralım dedik
//kös ol sag
{
if (root != null) {
printPostOrder(root.left);
printPostOrder(root.right);
System.out.println(root.data);
}
}
Node findMin() {
return findMin(root);
}
Node findMin(Node root) { // solu null oluncaya kadar lefte git ,sol en küçüktür zaten
if (root != null) {
while (root.left != null) {
root = root.left;
}
}
return root;
}
Node findMax() //en sagdakini alırsak o en büyüktür zaten
//rootları değiştir temp olayı gibi ,en saga git
{
return findMax(root);
}
Node findMax(Node root) { // solu null oluncaya kadar lefte git ,sol en küçüktür zaten
if (root != null) {
while (root.right != null) {
root = root.right;
}
}
return root;
}
//istenilen
Node find(T value) {
return find(value, root);
}
Node find(T value, Node root) {
if (root == null) {
throw new NoSuchElementException(“bu eleman yok”);
} //bulamamışıkm dmkki //başka arıcak node klamadı //cizersen anlarsın bi tree
else if (value.compareTo(root.data) < 0) {
return find(value, root.left); //al bu value yu rootun solunda ara diozburda
} else if (value.compareTo(root.data) > 0) {
return find(value, root.right);
} else {
return root;
}
}
//remove da sag cocukalrdan enkçk datalıyı alıp root yaparız ya da solda en bğyük datalıyı
void remove(T value)
{
root=remove(value,root);//value yu cıkar ,valusuz notu roota ata dmk
}
Node remove(T value,Node root) //sildigi nodu döndürcek
{
if (root==null)
throw new NoSuchElementException(” sileinencek böyle bir eleman yok”);
else if(value.compareTo(root.data)<0)
root.left=remove(value,root.left); //rootun leftinde ara ,bulursa silecek tekrar atayacak
else if(value.compareTo(root.data)>0)//sagda ara elemanı
root.right=remove(value,root.right);
else
{ //iki olcukta nu calıscak
if (root.left!=null && root.right!=null)
{
//rotun lefti vartsa raigtı da var sa,iki cocukta var
//sagdaki min bulcak onu yapcaz yeni ailenin rootu
T temp= findMin(root.right).data; //sagdaki min bul tempe ata
root.data=temp;
root.right =remove(temp, root.right); //rootun rigtından = temp i sil tkrar ata
//sagdaki minimumun sol cocugu olamaz …
}else { //0 yada 1 cocugu varsa ; bir cocugu varsa ya da hiç yoksa
root=(root.left !=null )? root.left :root.right; //dogruysa sol yanlışşsa sag calısıyor //
}
}
return root;
}
class Node {
T data; //nodun içine istedğiimixz satayı koyaiblmek için generic yaptık
//priimivtive bir tip almaz,referans tip alması lazım parantez içi
Node right;
Node left;
Node(T data) {
this.data = data;
}
}
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(7);
tree.insert(3);
tree.insert(6);
tree.insert(7);
System.out.println(“****** Postorder **************************”);
tree.printPostOrder();
System.out.println(“******** INOrder ************************”);
tree.printInOrder();
System.out.println(“********** PreOrder **********************”);
tree.printPreOrder();
System.out.println(“********************************”);
System.out.println(“min : ” + tree.findMin().data);
System.out.println(“********************************”);
System.out.println(“max : ” + tree.findMax().data);
System.out.println(“********************************”);
System.out.println(“find :” + tree.find(10).data);
System.out.println(“********istenen datayı treeden silme************************”);
tree.remove(10); //
System.out.println(“********gezilen toplam node sayısı ************************”);
System.out.println(tree.nodeCount());
System.out.println(“complete mi ” +tree.isComplete());
}
}