首页 > 代码库 > 二叉查找树java实现

二叉查找树java实现

2024-07-07 23:15:12   226人阅读

主要参考<<数据结构与算法分析>>Java语言描述(Mark Allen Weiss)

二叉查找树主要的操作是:1.查找，2，插入，删除。

查找操作：从根节点开始，递归查找。如果值等于当前根节点，返回根节点存储的值。若果查找的值小于跟根节点的值，则查找左子树，反之递归查找右子树。如果要查找的当前节点为NULL，说明查找结束了，没有找到要查找的元素。

插入操作：基本和查找操作相同，只是最后加入找到的是null，则新建一个节点，并返回。

删除操作：找到要删除的节点，让右子树最左边的节点替代。然后删除此节点右子树最小节点。

代码如下：

public class BinarySearchTree<T extends Comparable<? super T>> {
    
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        Integer[] a = {2,45,43,67,8,10,12,43,65,87,432,11,90,48,40};//测试数据
        for(int i = 0;i<a.length;i++){
            bst.insert(a[i]);
        }
        bst.remove(45);
        bst.remove(12);
         bst.showTree();
    }
    
    private BinaryNode<T> root;
    public static class BinaryNode<T>{
        public T element;
        public BinaryNode<T> left;
        public BinaryNode<T> right;
        public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
        public BinaryNode(T theElement) {
            element = theElement;
        }    
        
    }
    
    public BinarySearchTree() {
        root = null;
    }

    public BinarySearchTree(BinaryNode<T> root) {
        this.root = root;
    }
    
    
    public boolean isEmpty(){
        return root == null;
    }
    
    public void makeEmpty(){
        root = null;
    }
    
    public boolean contains(T x){
        return contains(root,x);
    }
    private boolean contains(BinaryNode<T> root, T x) {
        if(root==null){
            return false;
        }
        int comparaResult = x.compareTo(root.element);
        if(comparaResult==1){
            return true;
        }
        else if(comparaResult<0){
            return contains(root.left,x);
        }
        else
            return contains(root.right,x);
    }
    public T findMin(){
        if(isEmpty()){
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return findMin(root).element;
    }
    
    public T findMax() throws Exception{
        if(isEmpty()){
            throw new Exception();
        }
        return findMax(root).element;
    }
    private BinaryNode<T> findMin(BinaryNode<T> root) {
        if(root==null){
            return null;
        }
        else if(root.left==null){
            return root;
        }
        return findMin(root.left);
    }
    private BinaryNode<T> findMax(BinaryNode<T> root) {
        if(root==null){
            return null;
        }
        else if(root.right==null){
            return root;
        }
        return findMax(root.right);
    }
    
    public void insert(T x){
        root = insert(x,root);
    }
    public BinaryNode<T> insert(T x,BinaryNode<T> root){
        if(root==null){
            return new BinaryNode<T>(x, null, null);
        }
        int compareResult = x.compareTo(root.element);
        if(compareResult>0){
            root.right = insert(x,root.right);
        }
        else if(compareResult<0){
            root.left = insert(x,root.left);
        }
        else
            ;
        return root;
    }
    public void remove(T a){
        remove(a,root);
    }

    private BinaryNode<T> remove(T x, BinaryNode<T> root2) {
        if(root2==null){
            return null;
        }
        int comparaResult = x.compareTo(root2.element);
        if(comparaResult < 0){
            root2.left = remove(x,root2.left);
        }
        else if(comparaResult > 0){
            root2.right = remove(x,root2.right);
        }
        else if(root2.left!=null&&root2.right!=null){
            root2.element = findMin(root2.right).element;
            root2.right = remove(root2.element,root2.right);
        }
        else{
            if(root2.left!=null){
                root2 = root2.left;
            }
            else{
                root2 = root2.right;
            }
        }
        return root2;
    }
    public void showTree(){
        showTree(root);
    }
    
    public void showTree(BinaryNode<T> T){
        if(T==null){
            return;
        }
        else{
            showTree(T.left);
            System.out.println(T.element);            
            showTree(T.right);
        }
        
    }
}

 


联系
我们