数据结构与算法-二叉查找树(java描述)

2017年3月31日 11点热度 0条评论 来源: 欧阳思海

一、概述

二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

1.1、定义

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
(3)左、右子树也分别为二叉排序树;

二、二叉查找树的实现

这里的二叉查找树的定义是在上篇博客的二叉树的定义上扩展的,因此这些操作是二叉树已定义的那些操作的补充。

2.1、抽象实现

BinarySearchTreeADT.java:

package sihai;

/** * 二叉查找树接口 */
public interface BinarySearchTreeADT<T> extends BinaryTreeADT<T> 
{
    /** * 在树中的适当位置添加一个元素 */
    public void addElement(T element);

    /** * 根据特定的元素删除元素 */ 
    public T removeElement(T targetElement);

    /** * 删除和目标元素有关的所有元素 */
    public void removeAllOccurrences(T targetElement);

    /** * 删除树中的最小元素 */
    public T removeMin();

    /** * 删除树中的最大元素 */ 
    public T removeMax();

    /** * 查找树中的最小元素 */ 
    public T findMin();

    /** *查找树中的最大元素 */
    public T findMax();
}


三、用链表实现二叉查找树

这里BinaryTreeNode类来表示树中的每个节点。每个BinaryTreeNode对象要维护一个指向节点所存储元素的引用,另外还要维护指向节点的每个孩子的引用。
LinkedBinaryTree提供两个构造函数:一个负责创建空的;另外一个负责创建一颗根节点为特定的元素的链接二叉查找树。

LinkedBinaryTree.java:

package jsjf;

import jsjf.exceptions.*;
import jsjf.*;

/** * 链接二叉查找树实现了链接二叉树接口和二叉查找树接口 */
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>
                                        implements BinarySearchTreeADT<T>
{

    public LinkedBinarySearchTree() 
    {
        super();
    }


    public LinkedBinarySearchTree(T element) 
    {
        super(element);

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

    /** * 添加元素 */
    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++;
    }

    /** * 在特定的节点插入元素 */
    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());
        }
    }


    /** * 删除目标元素 */
    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;
    }

    /** * 删除元素 */
    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;
    }

    /** * 返回一个引用代替将要删除的元素 */
    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;
    }

    /** * 删除目标元素的所有引用 */
    public void removeAllOccurrences(T targetElement)
                   throws ElementNotFoundException 
    {
        removeElement(targetElement);

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

        catch (Exception ElementNotFoundException)
        {
        }
    }

    /** *删除最小元素 */
    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;
    }

    /** * 删除最大元素 */
    public T removeMax() throws EmptyCollectionException 
    {
        // TODO
    }

    /** * 查询二叉查询树中的最小值 */
    public T findMin() throws EmptyCollectionException 
    {
        // TODO
    }

    /** * 查询二叉查询树中的最大值 */
    public T findMax() throws EmptyCollectionException 
    {
        // TODO
    }

    /** * 查询目标元素 */
    public T find(T targetElement) throws ElementNotFoundException 
    {
        // TODO
    }

    /** * 查询左节点 */
    public LinkedBinarySearchTree<T> getLeft()
    {
        // TODO
    }

    /** * 查询右节点 */
    public LinkedBinarySearchTree<T> getRight()
    {
        // TODO
    }

    /** * 查找目标节点 */
    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) 
    {
        // TODO
    }
}

注意:其中还有一些没有完善,日后再慢慢学习完善。

    原文作者:欧阳思海
    原文地址: https://blog.csdn.net/sihai12345/article/details/68928641
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。