树——平衡二叉树插入和查找的JAVA实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了树——平衡二叉树插入和查找的JAVA实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7397字，纯文字阅读大概需要11分钟。
内容图文
package
com.tomsnail.data.tree;
/**
* AVL二叉平衡树
*
@author
tomsnail
* @date 2015年3月30日 下午4:35:50
*/
public
class
AVLTree {
/**
* 根节点
*
@author
tomsnail
* @date 2015年3月30日 下午4:36:54
*/
private
AVLNode rootNode;
private String bulidType = "";
/**
* 增加一个节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:08
*/publicvoid add(int value){
AVLNode subNode = null;
if(rootNode==null){
subNode = new AVLNode(value);
rootNode = subNode;
}else{
subNode = addNode(rootNode,value);
}
reBuild(subNode);
}
private AVLNode addNode(AVLNode node,int value){
AVLNode subNode = null;
if(node.getValue()>value){
if(node.getLeftNode()==null){
subNode = new AVLNode(value);
node.setLeftNode(subNode);
}else{
subNode = addNode(node.getLeftNode(), value);
}
}
if(node.getValue()<value){
if(node.getRightNode()==null){
subNode = new AVLNode(value);
node.setRightNode(subNode);
}else{
subNode = addNode(node.getRightNode(),value);
}
}
return subNode;
}
/**
* 重平衡树
* @author tomsnail
* @date 2015年3月30日 下午5:42:00
*/privatevoid reBuild(AVLNode node){
if(node!=null){
AVLNode tempRootNode = findTempRootNode(node);
if(tempRootNode!=null){
if(bulidType.equals("ll")){
Lrotate(node,tempRootNode);
}elseif(bulidType.equals("rr")){
Rrotate(node,tempRootNode);
}elseif(bulidType.equals("lr")){
Rrotate(node,tempRootNode.getLeftNode());
Lrotate(node,tempRootNode);
}elseif(bulidType.equals("rl")){
Lrotate(node,tempRootNode.getRightNode());
Rrotate(node,tempRootNode);
}
}
}
}
/**
* 左旋
* @author tomsnail
* @date 2015年3月30日 下午9:23:28
*/privatevoid Rrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getRightNode();
AVLNode rootNode = tempRootNode.getRootNode();
String type = "";
if(rootNode!=null){
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getLeftNode();
rotateNode.setLeftNode(tempRootNode);
tempRootNode.setRightNode(null);
if(adjustNode!=null){
tempRootNode.setRightNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}elseif(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
* 右旋
* @author tomsnail
* @date 2015年3月30日 下午9:23:28
*/privatevoid Lrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getLeftNode();
AVLNode rootNode = tempRootNode.getRootNode();
String type = "";
if(rootNode!=null){
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getRightNode();
rotateNode.setRightNode(tempRootNode);
tempRootNode.setLeftNode(null);
if(adjustNode!=null){
tempRootNode.setLeftNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}elseif(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
* 查找最小不平衡的根节点
* @author tomsnail
* @date 2015年3月30日 下午5:40:55
*/private AVLNode findTempRootNode(AVLNode node){
AVLNode noB = getNoBalance(node);
if(noB==null){
returnnull;
}
if(isTypeLL(noB)){
bulidType = "ll";
}elseif(isTypeRR(noB)){
bulidType = "rr";
}elseif(isTypeLR(noB)){
bulidType = "lr";
}elseif(isTypeRL(noB)){
bulidType = "rl";
}
return noB;
}
privateboolean isTypeLL(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){
returntrue;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){
returntrue;
}
} catch (Exception e) {
}
returnfalse;
}
privateboolean isTypeRR(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){
returntrue;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){
returntrue;
}
} catch (Exception e) {
}
returnfalse;
}
privateboolean isTypeLR(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){
returntrue;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){
returntrue;
}
} catch (Exception e) {
}
returnfalse;
}
privateboolean isTypeRL(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){
returntrue;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){
returntrue;
}
} catch (Exception e) {
}
returnfalse;
}
private AVLNode getNoBalance(AVLNode node){
if(node.getRootNode()==null){
returnnull;
}else{
if(!isBalance(node.getRootNode())){
return node.getRootNode();
}else{
return getNoBalance(node.getRootNode());
}
}
}/**
* 查找一个节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:35
*/public AVLNode find(int value){
return findWith2(rootNode,value);
}
private AVLNode findWith2(AVLNode node,int value){
if(node==null){
returnnull;
}
System.out.println(node.getValue());
if(node.getValue()>value){
return findWith2(node.getLeftNode(),value);
}elseif(node.getValue()<value){
return findWith2(node.getRightNode(),value);
}else{
return node;
}
}
publicvoid midScan(AVLNode node){
if(node==null){
return;
}
midScan(node.getLeftNode());
System.out.println(node.getValue());
midScan(node.getRightNode());
}
public AVLNode getRootNode() {
return rootNode;
}
publicstaticvoid main(String[] args) {
int[] is = newint[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80
AVLTree tree = new AVLTree();
for(int i=0;i<is.length;i++){
tree.add(is[i]);
}
System.out.println(tree.getRootNode().getValue());
System.out.println("----------------------------");
tree.midScan(tree.getRootNode());
System.out.println(isBalance(tree.getRootNode()));
}
publicstaticint depth(AVLNode node){
if(node==null){
return 0;
}else{
int ld = depth(node.getLeftNode());
int rd = depth(node.getRightNode());
return 1 + (ld >rd ? ld : rd);
}
}
publicstaticboolean isBalance(AVLNode node){
if (node==null)
returntrue;
int dis = depth(node.getLeftNode()) - depth(node.getRightNode());
if (dis>1 || dis<-1 )
returnfalse;
elsereturn isBalance(node.getLeftNode()) && isBalance(node.getRightNode());
}
}class AVLNode{
privateint value;
private AVLNode leftNode;
private AVLNode rightNode;
private AVLNode rootNode;
publicint getValue() {
return value;
}
publicvoid setValue(int value) {
this.value = value;
}
public AVLNode getLeftNode() {
return leftNode;
}
publicvoid setLeftNode(AVLNode leftNode) {
this.leftNode = leftNode;
if(leftNode!=null){
leftNode.setRootNode(this);
}
}
public AVLNode getRightNode() {
return rightNode;
}
publicvoid setRightNode(AVLNode rightNode) {
this.rightNode = rightNode;
if(rightNode!=null){
rightNode.setRootNode(this);
}
}
public AVLNode getRootNode() {
return rootNode;
}
publicvoid setRootNode(AVLNode rootNode) {
this.rootNode = rootNode;
}
publicboolean hasSubNode(){
if(this.leftNode!=null||this.rightNode!=null){
returntrue;
}else{
returnfalse;
}
}
public AVLNode(){
}
public AVLNode(int value){
this.value = value;
}
}
原文：http://www.cnblogs.com/TomSnail/p/4379702.html
内容总结
以上是互联网集市为您收集整理的树——平衡二叉树插入和查找的JAVA实现全部内容，希望文章能够帮你解决树——平衡二叉树插入和查找的JAVA实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】