package ch6;

import java.util.*;

class TreeNode implements Comparable
{
    T data;
    TreeNode llink;
    TreeNode rlink;

    public TreeNode(T data)  { this.data = data; }
    public int compareTo(Object o) {
        Comparable d1 = (Comparable) data;
        Comparable d2 = (Comparable) (((TreeNode)o).data);
        return d1.compareTo(d2);
    }

    public String toString() { return ""+data; }
}
/**
 *
 * @author student
 */
public class BinarySearchTree {
    private TreeNode root;
    public void printTree()
    {
        printTree(root);
    }
    private void printTree(TreeNode node)
    {
        if (node == null) return;
        System.out.println(node);
        printTree(node.llink);
        printTree(node.rlink);
    }
    public void postorderTraverse()
    {
        postorderTraverse(root);
    }
    private void postorderTraverse(TreeNode node)
    {
        if (node == null) return;
        postorderTraverse(node.llink);
        postorderTraverse(node.rlink);
        System.out.print(node.data+" ");
    }
    public void levelorderTraverse()
    {
        levelorderTraverse(root);
    }
    private void levelorderTraverse(TreeNode node)
    {
        if (node == null) return;
        Queue > queue = new LinkedList >();
        queue.add(node);
        while (! queue.isEmpty())
        {
            TreeNode p = queue.remove();
            System.out.print(p.data+" ");
            if (p.llink != null) queue.add(p.llink);
            if (p.rlink != null) queue.add(p.rlink);
        }
    }
    public BinarySearchTree delete(T data)
    {
        root=delete(root, data);
        return this;
    }
    private TreeNode delete(TreeNode node, T data)
    {
        TreeNode newnode = new TreeNode(data);
        if (node == null)
        {
            System.out.println("Cannot find data="+data+" in this tree.");
            return node;
        }
        if (newnode.compareTo(node) < 0)
            node.llink = delete(node.llink, data);
        else if (newnode.compareTo(node) > 0)
            node.rlink = delete(node.rlink, data);
        else  // has found!
        {
            if (node.llink == null)
                node = node.rlink;
            else if (node.rlink == null)
                node = node.llink;
            else  // both left & right trees are existent
            {
                TreeNode successor = findSuccessor(node.rlink);
                node.data = successor.data;
                node.rlink = delete(node.rlink, successor.data);
            }
        }
        return node;
    }

    private TreeNode findSuccessor(TreeNode node)
    {
        if (node.llink == null) return node;
        return findSuccessor(node.llink);
    }

    public BinarySearchTree insert(T data)
    {
        root=insert(root, data);
        return this;
    }
    private TreeNode insert(TreeNode node, T data)
    {
        TreeNode newnode = new TreeNode(data);
        if (node == null) { node=newnode; return node; }
        if (newnode.compareTo(node) < 0)  // left tree
            node.llink = insert(node.llink, data);
        else
            node.rlink = insert(node.rlink, data);
        return node;
    }
}