public class Treee {
    Node kok; 
    public Treee(){
        kok = null;
    }
    public **** ekle(int data){ //ekleme metodu
        Node x = new Node();
        x.data = data;
        if(kok == null){
            kok = x;
        }
        else{
            Node current = kok;
            Node parent;
            while(true){
                parent = current;
                if(x.data < current.data){
                    current = current.sol;
                    if(current == null){
                        parent.sol = x;
                        return;
                    }
                }
                else{
                    current = current.sag;
                    if(current == null){
                        parent.sag = x;
                        return;
                    }
                }
            }
        }
    }
    public **** delete(int key){
        Node current = kok;
        Node parent = kok;
        boolean isLeftTree = true;
        if(kok == null){
            System.out.println("Silinecek Ağaç Yok");
        }
        while(current.data != key){//sileceğimiz elemanı buluyoruz
            parent = current;
            if(key < current.data){
                isLeftTree = true;
                current = current.sol;
            }
            else{
                isLeftTree = false;
                current = current.sag;
            }
            if(current == null){
                System.out.println("Eleman Bulunamadı");
            }
        }
            if(current.sag == null && current.sol == null){ //sileceğimiz elemanın sağ ve solunda eleman yoksa
                if(current == kok){
                    kok = null;
                }
                else if(isLeftTree){
                    parent.sol = null;
                }
                else
                    parent.sag = null;
            }
            else if(current.sag == null){//sileceğimiz elemanın sağında eleman yoksa
                if(current == kok){
                    kok = parent.sol;
                }
                else if(isLeftTree){
                    parent.sol = current.sol;
                }
                else
                    parent.sag = current.sol;
            }
            else if(current.sol == null){//sileceğimiz elemanın solunda eleman yoksa
                if(current == kok){
                    kok = parent.sag;
                }
                else if(isLeftTree){
                    parent.sol = current.sag;
                }
                else
                    parent.sag = current.sag;
            }
            else{                       //sileceğimiz elemanın iki tane ****** varsa
                Node successor = getSuccessor(current);
                if(current == kok){
                    kok = successor;
                }
                else if(isLeftTree){
                    parent.sol = successor;
                }
                else{
                    parent.sag =successor;
                }
                successor.sol = current.sol;
            }
    }
    private Node getSuccessor(Node delNode) {
              Node successorParent = delNode;
              Node successor = delNode;
              Node current = delNode.sag;                       
              while(current != null){                                       
                    successorParent = successor;
                    successor = current;
                    current = current.sol; 		           
                    }
                         if(successor != delNode.sag){ 	           
                    successorParent.sol = successor.sag;
                    successor.sag = delNode.sag;
                    }
            return successor;
}

    public int arama(int data){
        Node current = kok;
        while(current != null){
            if(current.data == data){
                return data;
            }
            else if(data < current.data){
                current = current.sol;
            }
            else
                current = current.sag;
        }
        return -1111;
    }
    //preorder dolaşma
    public **** preOrder(Node kok){
        System.out.println(kok.data);
        if(kok.sol != null){
            preOrder(kok.sol);
        }
        if(kok.sag != null){
            preOrder(kok.sag);
        }
    }
    //inorder dolaşma
    public **** inOrder(Node kok){
        if(kok.sol != null){
            inOrder(kok.sol);
        }
        System.out.println(kok.data);
        if(kok.sag != null){
            inOrder(kok.sag);
        }
    }
    //postorder dolaşma
    public **** postOrder(Node kok){
        if(kok.sol != null){
            postOrder(kok.sol);
        }
        if(kok.sag != null){
            postOrder(kok.sag);
        }
        System.out.println(kok.data);
    }
}