资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

Java中怎么实现二叉树平衡

Java中怎么实现 二叉树平衡,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

十载的清镇网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。营销型网站的优势是能够根据用户设备显示端的尺寸不同,自动调整清镇建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联建站从事“清镇网站设计”,“清镇网站推广”以来,每个客户项目都认真落实执行。


  二叉树平衡的基本思想是通过旋转使得平衡因子的绝对值小于1。
  如图所示:


Java中怎么实现 二叉树平衡


输入:失衡的结点z
输出:平衡后子树的根结点

private BinTreeNode rotate(BinTreeNode z){
    BinTreeNode y = higherSubT(z); //取y 为z 更高的孩子BinTreeNode x = higherSubT(y); //取x 为y 更高的孩子boolean isLeft = z.isLChild(); //记录:z 是否左孩子BinTreeNode p = z.getParent(); //p 为z 的父亲BinTreeNode a, b, c; //自左向右,三个节点BinTreeNode t0, t1, t2, t3; //自左向右,四棵子树// 以下分四种情况重命名if (y.isLChild()) { //若y 是左孩子,则c = z; t3 = z.getRChild();if (x.isLChild()) { //若x 是左孩子(左左失衡)b = y; t2 = y.getRChild();
            a = x; t1 = x.getRChild(); t0 = x.getLChild();
        } else { //若x 是右孩子(左右失衡)a = y; t0 = y.getLChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    } else { //若y 是右孩子,则a = z; t0 = z.getLChild();if (x.isRChild()) { //若x 是右孩子(右右失衡)b = y; t1 = y.getLChild();
            c = x; t2 = x.getLChild(); t3 = x.getRChild();
        } else { //若x 是左孩子(右左失衡)c = y; t3 = y.getRChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    }//摘下三个节点z.sever();
    y.sever();
    x.sever();//摘下四棵子树if (t0!=null) t0.sever();if (t1!=null) t1.sever();if (t2!=null) t2.sever();if (t3!=null) t3.sever();//重新链接a.setLChild(t0); a.setRChild(t1);
    c.setLChild(t2); c.setRChild(t3);
    b.setLChild(a); b.setRChild(c);//子树重新接入原树if (p!=null)if (isLeft) p.setLChild(b);else p.setRChild(b);return b;//返回新的子树根}//返回结点v 较高的子树private BinTreeNode higherSubT(BinTreeNode v){if (v==null) return null;int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;if (lH>rH) return v.getLChild();if (lH

输入:待插元素ele
输出:在AVL 树中插入ele
代码:

public void insert(Object ele){super.insert(ele);
    root = reBalance(startBN);
}//从v 开始重新平衡AVL 树private BinTreeNode reBalance(BinTreeNode v){if (v==null) return root;
    BinTreeNode c = v;while (v!=null) { //从v 开始,向上逐一检查z 的祖先if (!isBalance(v)) v = rotate(v); //若v 失衡,则旋转使之重新平衡c = v;
        v = v.getParent(); //继续检查其父亲}//whilereturn c;
}//判断一个结点是否失衡private boolean isBalance(BinTreeNode v){if (v==null) return true;int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;return (Math.abs(lH - rH)<=1);
}

输入:待删元素ele
输出:在AVL 树中删除ele
代码:

public Object remove(Object ele){
    Object obj = super.remove(ele);
    root = reBalance(startBN);return obj;
}

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。


网站标题:Java中怎么实现二叉树平衡
网页链接:http://www.cdkjz.cn/article/jspgip.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220