栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java实现AVL树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java实现AVL树

一、定义AVL树类


public class AVLTree> {
    private AVLNode mRoot; //结点

    //AVL树的结点(内部类)
    class  AVLNode>{
        T key;  //结点的值
        int height; //高度
        AVLNode left; //左孩子
        AVLNode right; //右孩子

        public AVLNode(T key, AVLNode left, AVLNode right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }
    //构造函数
    public AVLTree() {
        mRoot = null;
    }
    //获取树的高度
    private int  height(AVLNode tree){
        if (tree != null){
            return tree.height;
        }
        return  0;
    }
    public  int getHeight(){
        return height(mRoot);
    }

    //找两个树的最大值
    private int max(int a,int b){
        return a>b ? a : b;
    }
    //前序遍历
    private void preOrder(AVLNode tree){
        if (tree != null){
            System.out.print("["+tree.key+"]   ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
    public void proOrder(){
        preOrder(mRoot);
    }

    //中序遍历
    private void inOrder(AVLNode tree){
        if (tree != null){
            inOrder(tree.left);
            System.out.print("["+tree.key+"]   ");
            inOrder(tree.right);
        }
    }
    public void inOrder(){
        inOrder(mRoot);
    }

    //后序遍历
    private void postOrder(AVLNode tree){
        if (tree != null){
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print("["+tree.key+"]   ");
        }
    }
    public void postOrder(){
        postOrder(mRoot);
    }

    
    private AVLNode search(AVLNode x,T key){
        if (x == null){
            return x;
        }
        int cmp = key.compareTo(x.key); //比较
        if (cmp < 0){ //如果key比x的key小,在x的左子树中找
            return search(x.left,key);
        }else if (cmp > 0){//如果key比x的key大,在x的右子树中找
            return search(x.right,key);
        }else{
            return x;
        }
    }
    public AVLNode search(T key){
        return search(mRoot,key);
    }
    
    private AVLNode iterativeSearch(AVLNode x, T key){
        while ( x != null){
            int cmp = key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            }else if (cmp > 0){
                x = x.right;
            }else{
                return x;
            }
        }
        return x;
    }
    public AVLNode iterativeSearch(T key){
        return iterativeSearch(mRoot,key);
    }

    
    private AVLNode minNum(AVLNode tree){
        if (tree == null){
            return null;
        }
        while (tree.left != null){ //在tree的左子树中查找
            tree = tree.left;
        }
        return tree;
    }

    public T minNum(){
        AVLNode p = minNum(mRoot);
        if (p != null){
            return p.key;
        }
        return null;
    }

    
    private AVLNode maxNum(AVLNode tree){
        if (tree == null){
            return null;
        }
        while (tree.right != null){ //在tree的右子树中查找
            tree = tree.right;
        }
        return tree;
    }

    public T maxNum(){
        AVLNode p = maxNum(mRoot);
        if (p != null){
            return p.key;
        }
        return null;
    }

    
    private AVLNode leftLeftRotate(AVLNode k2){
        AVLNode k1;
        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = max(height(k2.left),height(k2.right)) + 1;
        k1.height = max(height(k1.left),k2.height) + 1;

        return k1;
    }
    
    private AVLNode rightRightRotate(AVLNode k1){
        AVLNode k2;
        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max(height(k1.left),height(k1.right)) + 1;
        k2.height = max(height(k2.right),k1.height) + 1;

        return k2;
    }

    
    private AVLNode leftRightRotate(AVLNode k3){
        k3.left = rightRightRotate(k3.left);

        return leftLeftRotate(k3);
    }

    
    private AVLNode rightLeftRotate(AVLNode k1){
        k1.right = leftLeftRotate(k1.right);

        return rightRightRotate(k1);
    }

    
    private AVLNode insert(AVLNode tree,T key){
        if (tree == null){ //如果树为空,新建结点
            tree = new AVLNode(key,null,null);
            if (tree == null){
                System.out.println("Error:create avltree node failed!");
                return null;
            }
        }else {
            int cmp = key.compareTo(tree.key);
            if (cmp < 0){ //若key小于根结点,则插入到左子树
                tree.left = insert(tree.left,key);
                //插入结点后,若AVL树失去平衡,则进行相应的调节
                if (height(tree.left) - height(tree.right) == 2){
                    if (key.compareTo(tree.left.key) < 0){
                        tree = leftLeftRotate(tree);
                    }else {
                        tree = leftRightRotate(tree);
                    }
                }
            }else if (cmp > 0){ //若key大于根结点,则插入到右子树
                tree.right = insert(tree.right,key);
                //插入结点后,若AVL树失去平衡,则进行相应的调节
                if (height(tree.right) - height(tree.left) == 2){
                    if (key.compareTo(tree.right.key) > 0){
                        tree = rightRightRotate(tree);
                    }else{
                        tree = rightLeftRotate(tree);
                    }
                }
            }else{ //cmp ==0
                System.out.println("添加失败:不允许添加相同的结点!");
            }
        }
        tree.height = max(height(tree.left),height(tree.right)) + 1;
        return tree;
    }

    public void insert(T key){
        mRoot = insert(mRoot,key);
    }

    
    private AVLNode remove(AVLNode tree,AVLNode z){
        //根为空 或者 没有要删除的结点,直接返回null
        if (tree == null || z == null){
            return null;
        }
        int cmp = z.key.compareTo(tree.key);
        if (cmp < 0){  //待删除结点在tree的左子树中
            tree.left = remove(tree.left,z);

            //删除结点后,若AVL树失去平衡,则进行相应的调节
            if (height(tree.right) - height(tree.left) == 2){
                AVLNode r = tree.right;
                if (height(r.left) > height(r.right)){
                    tree = rightLeftRotate(tree);
                }else{
                    tree = rightRightRotate(tree);
                }
            }
        }else if (cmp > 0){ //待删除结点在tree的右子树中
            tree.right = remove(tree.right,z);
            //删除结点后,若AVL树失去平衡,则进行相应的调节
            if (height(tree.left) - height(tree.right) == 2){
                AVLNode l = tree.left;
                if (height(l.right) > height(l.left)){
                    tree = leftRightRotate(tree);
                }else{
                    tree = leftLeftRotate(tree);
                }
            }
        }else{ //tree是对应要删除的结点
            if ((tree.left != null) &&(tree.right != null)){ //tree的左右孩子都非空
                if (height(tree.left) > height(tree.right)){
                    
                    AVLNode max = minNum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left,max);
                }else{
                    
                    AVLNode min = minNum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right,min);
                }
            }else{
                AVLNode tmp = tree;
                tree = (tree.left != null)?tree.left : tree.right;
                tmp = null;
            }
        }
        return tree;
    }

    public void remove(T key){
        AVLNode z = search(mRoot,key);
        if (z != null){
            mRoot = remove(mRoot,z);
        }
    }

    
    private void destroy(AVLNode tree){
        if (tree == null){
            return;
        }
        if (tree.left != null){
            destroy(tree.left);
        }
        if (tree.right != null){
            destroy(tree.right);
        }
        tree = null;
    }
    public  void destroy(){
        destroy(mRoot);
    }

    
    private void print(AVLNode tree,T key,int direction){
        if (tree != null){
            if (direction ==0){ //tree是根结点
                System.out.printf("%2d is rootn",tree.key,key);
            }else{ //tree的分支结点
                System.out.printf("%2d is %2d's %6s childn",tree.key,key,direction==1?"right":"left");
            }
            print(tree.left,tree.key,-1);
            print(tree.right,tree.key,1);
        }
    }
    public void print(){
        if (mRoot != null){
            print(mRoot,mRoot.key,0);
        }
    }
}

二、测试


public class AVLTreeTest {
    private static int arr[]= {33,32,1,4,5,6,17,16,15,14,13,12,11,10,8,9};

    public static void main(String[] args) {
        int i;
        AVLTree tree = new AVLTree<>();
        System.out.printf("== 依次添加:");
        for ( i = 0; i < arr.length ; i++) {
            System.out.printf("%d ",arr[i]);
            tree.insert(arr[i]);
        }
        System.out.printf("n== 前序遍历:");
        tree.proOrder();

        System.out.printf("n== 中序遍历:");
        tree.inOrder();

        System.out.printf("n== 后序遍历:");
        tree.postOrder();
        System.out.println();

        System.out.printf("== 高度:%dn",tree.getHeight());
        System.out.printf("== 最小值:%dn",tree.minNum());
        System.out.printf("== 最大值:%dn",tree.maxNum());

        System.out.println("== 树的详细信息:");
        tree.print();

        i = 8;
        System.out.printf("n== 删除结点:%d",i);
        tree.remove(i);

        System.out.printf("n== 高度:%d",tree.getHeight());
        System.out.printf("n== 中序遍历:");
        tree.inOrder();
        System.out.printf("n== 树的详细信息:n");
        tree.print();

        tree.destroy();//销毁二叉树
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/973294.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号