package btree;

import java.util.*;

class Node {
        int key;
        int height;

        Node left;
        Node right;
        Node (int newKey) {
            this.key = newKey;
            height = 1;
            left = null;
            right = null;
        }
}

public class BTree {
    static Node root;
    int deep = 0;

    public void addNode(int key) {
        Node newNode = new Node(key);
        newNode.height = 1;

        if (root == null) {
            root = newNode;
        } else {
            Node focusNode = root;

            while (true) {
                if (key < focusNode.key) {
                    focusNode.height = Math.max( getHeight(focusNode.left) + 1, getHeight(focusNode.right) ) + 1;
                    if (focusNode.left == null) {
                        focusNode.left = newNode;
                        return;
                    }
                    //focusNode.height = Math.max( getHeight(focusNode.left) + 1, getHeight(focusNode.right) ) + 1;
                    focusNode = focusNode.left;
                } else {
                    focusNode.height = Math.max( getHeight(focusNode.left), getHeight(focusNode.right) + 1 ) + 1;
                    if (focusNode.right == null) {
                        focusNode.right = newNode;
                        //focusNode.height = Math.max( getHeight(focusNode.left), getHeight(focusNode.right) + 1 ) + 1;
                        return;
                    }   else {
                        //focusNode.height = Math.max( getHeight(focusNode.left), getHeight(focusNode.right) + 1 ) + 1;
                        focusNode = focusNode.right;
                    }
                }
            }
        }
    }

    public void add(Node root, int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return;
        }
        Node focusNode = root;
        if (key < focusNode.key) {
            if (focusNode.left == null) {
                focusNode.left = newNode;
            } else {
                add(focusNode.left, key);
            }
        } else {
            if (focusNode.right == null) {
                focusNode.right = newNode;
            } else {
                add(focusNode.right, key);
            }
        }
    }



    public int getHeight(Node n) {
        return ( (n == null) ? 0 : n.height );
    }

    public Node rem(int key) {
        if (root == null) return null;
        Node focusNode = root;
        Node parent = null;

        Boolean flagLeft = null;
        System.out.println(flagLeft);

        while (focusNode.key != key) {          //Поиск нужного узла
            if (key < focusNode.key) {
                parent = focusNode;
                focusNode = focusNode.left;
                flagLeft = true;
            } else {
                parent = focusNode;
                focusNode = focusNode.right;
                flagLeft = false;
            }
            if (focusNode == null) {
                return null;
            }
        }

        if (focusNode.left  == null) {              //Левый потомок пуст
            if (focusNode.right  == null) {             //Оба потомка пусты
                if (flagLeft)
                    parent.left = null;
                else
                    parent.right = null;
                return focusNode;                       //
            }

            parent.key = focusNode.key;
            parent.right = null;
            return focusNode;                       //
        } else  if  (focusNode.right  == null ) {   // Только правый потомок пуст
            focusNode.key = focusNode.left.key;
            focusNode.left = null;
            /*parent.key = focusNode.key;
            parent.left = null;*/
            return focusNode;
        } else {                                    //Оба потомка присутствуют
            Node temp = focusNode.right;
            while (temp.left != null) {
                parent = temp;
                temp = temp.left;
            }
            focusNode.key = temp.key;
            parent.left = null;
            return temp;
        }                                           //
    }

    public void preorder(Node focusNode) {
        if (root == null)
            return;
        for (int i = 0; i < deep; i++) {
            System.out.print("_");
        }
        System.out.println(focusNode.key + "(" + focusNode.height + ")");

        ++deep;
        if (focusNode.left != null) {
            this.preorder(focusNode.left);
            --deep;
        }

        if (focusNode.right != null) {
            this.preorder(focusNode.right);
            --deep;
        }
    }

    public static void main(String[] args) {
        BTree tree = new BTree();
        int d;
        Scanner sc = new Scanner(System.in);



         while (true) {
             System.out.println("Добавить узел: 1");
             System.out.println("Удалить узел: 2");
             System.out.println("Вывести дерево: 3");
             System.out.println("Выход: 0");

             d = sc.nextInt();

             if (d == 1)
                 while(true) {
                     System.out.println("Введите узел: ");
                     int x = sc.nextInt();
                     if (x == 0) break;
                     tree.add(root, x);
                 }
             if (d == 2) {
                 System.out.println("Введите значение удаляемого узла: ");
                 tree.rem(sc.nextInt());
                 continue;
             }
             if (d == 3) {
                 System.out.println("Вывод дерева:");
                 tree.preorder(root);
             }
             if (d == 0) {
                 return;
             }
         }
    }

}