package week7;

import week2.EmptyCollectionException;
import week4.ElementNotFoundException;
import week4.NonComparableElementException;
import week6.BinaryTreeNode;
import week6.LinkedBinaryTree;




public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>
        implements BinarySearchTreeADT<T>
{
    //创建空二叉查找树
    public LinkedBinarySearchTree()
    {
        super();
    }

    //创建具有指定元素作为其根的二叉查找树
    //element将成为新二叉查找树的根元素
    public LinkedBinarySearchTree(T element)
    {
        super(element);

        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }

    //将指定的对象添加到二叉查找树中。根据其自然顺序的适当位置注意,在右侧添加相等的元素。
    //element要添加到二叉查找树中的元素
    public void addElement(T element)
    {
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");

        Comparable<T> comparableElement = (Comparable<T>)element;

        if (isEmpty())
            root = new BinaryTreeNode<T>(element);
        else
        {
            if (comparableElement.compareTo(root.getElement()) < 0)
            {
                if (root.getLeft() == null)
                    this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getLeft());
            }
            else
            {
                if (root.getRight() == null)
                    this.getRootNode().setRight(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getRight());
            }
        }
        modCount++;
    }

    //将指定的对象添加到二叉查找树中。根据其自然顺序的适当位置。 注意，在右侧添加相等的元素。
    //element是要添加到二叉查找树中的元素
    private void addElement(T element, BinaryTreeNode<T> node)
    {
        Comparable<T> comparableElement = (Comparable<T>)element;

        if (comparableElement.compareTo(node.getElement()) < 0)
        {
            if (node.getLeft() == null)
                node.setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getLeft());
        }
        else
        {
            if (node.getRight() == null)
                node.setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getRight());
        }
    }


    //移除与指定目标匹配的第一个元素元素从二叉查找树, 并返回一个引用它. 如果指定的目标 ElementNotFoundException, 则引发在二叉查找树中找不到元素。
    //targetElement 是在二叉查找树中寻找的元素
    //ElementNotFoundException 如果未找到目标元素
    public T removeElement(T targetElement)
            throws ElementNotFoundException
    {
        T result = null;

        if (isEmpty())
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            BinaryTreeNode<T> parent = null;
            if (((Comparable<T>)targetElement).equals(root.element))
            {
                result =  root.element;
                BinaryTreeNode<T> temp = replacement(root);
                if (temp == null)
                    root = null;
                else
                {
                    root.element = temp.element;
                    root.setRight(temp.right);
                    root.setLeft(temp.left);
                }

                modCount--;
            }
            else
            {
                parent = root;
                if (((Comparable)targetElement).compareTo(root.element) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }

        return result;
    }

    // 移除与指定目标匹配的第一个元素元素从二叉查找树, 并返回一个引用它. 如果指定的目标 ElementNotFoundException, 则引发在二叉查找树中找不到元素。
    // @param targetElement 在二叉查找树中寻找的元素
    // @param 节点要从中搜索的节点*
    // @param 父节点的父级, 从中进行搜索
    // @throws ElementNotFoundException 如果未找到目标元素
    private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)
            throws ElementNotFoundException
    {
        T result = null;

        if (node == null)
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            if (((Comparable<T>)targetElement).equals(node.element))
            {
                result =  node.element;
                BinaryTreeNode<T> temp = replacement(node);
                if (parent.right == node)
                    parent.right = temp;
                else
                    parent.left = temp;

                modCount--;
            }
            else
            {
                parent = node;
                if (((Comparable)targetElement).compareTo(node.element) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }

        return result;
    }

    //返回对将替换一个节点的引用指定为删除。 如果已移除的节点具有两个子级, 则将该序后继项用作其替换。
    // @param 节点要删除的节点
    // @return 对替换节点的引用

    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> result = null;

        if ((node.left == null) && (node.right == null))
            result = null;

        else if ((node.left != null) && (node.right == null))
            result = node.left;

        else if ((node.left == null) && (node.right != null))
            result = node.right;

        else
        {
            BinaryTreeNode<T> current = node.right;// 初始化右侧第一个结点
            BinaryTreeNode<T> parent = node;

            // 获取右边子树的最左边的结点
            while (current.left != null)
            {
                parent = current;
                current = current.left;
            }

            // 如果当前待查询的结点
            current.left = node.left;
            if (node.right != current)
            {
                parent.left = current.right;// 整体的树结构移动就可以了
                current.right = node.right;
            }

            result = current;
        }

        return result;
    }

    //负责从二叉查找树中删除制定元素的所有存在;或者，当先在树中找不到指定元素的时候，抛出ElementNotFoundExceptio异常。如果指定元素不是com类型 则抛出class异常。
    // @param targetElement 在二进制搜索树中寻找的元素
    // @throws ElementNotFoundException 如果找不到目标元素
    public void removeAllOccurrences(T targetElement)
            throws ElementNotFoundException
    {
        removeElement(targetElement);

        try
        {
            while (contains((T)targetElement))
                removeElement(targetElement);
        }

        catch (Exception ElementNotFoundException)
        {
        }
    }

    //从二进制搜索中删除最小值的节点树并返回对其元素的引用。 抛出一个EmptyCollectionException 如果这棵树是空的。
    //@return 对具有最小值的节点的引用
    //@throws EmptyCollectionException 如果树是空的
    public T removeMin() throws EmptyCollectionException
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else
        {
            if (root.left == null)
            {
                result = root.element;
                root = root.right;
            }
            else
            {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.left;
                while (current.left != null)
                {
                    parent = current;
                    current = current.left;
                }
                result =  current.element;
                parent.left = current.right;
            }

            modCount--;
        }

        return result;
    }

    //从二进制文件中移除具有最高值的节点搜索树并返回对其元素的引用。 抛出一个EmptyCollectionException 如果这棵树是空的。
    //@return 对具有最高值的节点的引用
    //@throws EmptyCollectionException 如果树是空的
    public T removeMax() throws EmptyCollectionException
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.right == null) {
                result = root.element;
                root = root.left;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.right;
                while (current.right != null) {
                    parent = current;
                    current = current.right;
                }
                result = current.element;
                parent.right = current.left;
            }

            modCount--;
        }

        return result;
    }

    //返回二进制搜索中最小值的元素树.它不会从二进制搜索树中删除该节点。如果此树为空, 则抛出 EmptyCollectionException。
    // @return 最小值的元素
    // @throws EmptyCollectionException 如果树是空的
    public T findMin() throws EmptyCollectionException
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.left == null) {
                result = root.element;
                //root = root.right;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.left;
                while (current.left != null) {
                    parent = current;
                    current = current.left;
                }
                result = current.element;
                //parent.left = current.right;
            }

            //modCount--;
        }

        return result;

    }

    //返回在二进制文件中具有最高值的元素搜索树。 它不会从二进制文件中删除节点搜索树。 如果此树为空, 则抛出 EmptyCollectionException。
    // @return 具有最高值的元素
    // @throws EmptyCollectionException 如果树是空的
    public T findMax() throws EmptyCollectionException
    {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.right == null) {
                result = root.element;
                //root = root.left;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.right;
                while (current.right != null) {
                    parent = current;
                    current = current.right;
                }
                result = current.element;
                //parent.right = current.left;
            }

            //modCount--;
        }

        return result;

    }


    //返回对指定目标元素的引用 (如果它是在二进制树中找到。 抛出一个抛出, 如果在此树中找不到指定的目标元素。
    // @param targetElement the element being sough in the binary tree
    // @throws ElementNotFoundException if the target element is not found
    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }

    /**
     * Returns the left subtree of the root of this tree.
     *
     * @return a link to the left subtree fo the tree
     */
    public LinkedBinaryTree<T> getLeft()
    {
        LinkedBinaryTree<T> tmp = new LinkedBinaryTree(this.root.getRight());
        return tmp;
    }

    /**
     * Returns the right subtree of the root of this tree.
     *
     *
     * @return a link to the right subtree of the tree
     */
    public LinkedBinaryTree<T> getRight()
    {
        LinkedBinaryTree<T> tmp = new LinkedBinaryTree(this.root.getRight());
        return tmp;
    }

    /**
     * Returns a reference to the specified target element if it is
     * found in this tree.
     *
     * @param targetElement the element being sought in the tree
     * @param next the tree node to begin searching on
     */
    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next)
    {
        if (next == null)
            return null;

        if (next.getElement().equals(targetElement))
            return next;

        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

        if (temp == null)
            temp = findNode(targetElement, next.getRight());

        return temp;
    }

}