数据结构-平衡二叉树Java实现
2024-09-03 21:12:25
1,Node.java
package com.cnblogs.mufasa.BalanceBinaryTree;
public class Node {
Node parent;
Node leftChild;
Node rightChild;
int val;
public Node(Node parent, Node leftChild, Node rightChild,int val) {
super();
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.val = val;
}
public Node(int val){
this(null,null,null,val);
}
public Node(Node node,int val){
this(node,null,null,val);
}
}
图1 Node.java结构图
2,BalanceBinaryTree.java
package com.cnblogs.mufasa.BalanceBinaryTree; import java.util.LinkedList;
import java.util.Queue; public class BalanceBinaryTree {
private final static int LEFT=0;
private final static int RIGHT=1;
private Node root;
private int size;
public BalanceBinaryTree(){
super();
} //LL型非平衡树，右旋转
public Node rightRotation(Node node){
System.out.println(node.val+"右旋");
if(node != null){
Node leftChild = node.leftChild;// 用变量存储node节点的左子节点
node.leftChild = leftChild.rightChild;// 将leftChild节点的右子节点赋值给node节点的左节点
if(leftChild.rightChild != null){// 如果leftChild的右节点存在，则需将该右节点的父节点指给node节点
leftChild.rightChild.parent = node;
}
leftChild.parent = node.parent;
if(node.parent == null){// 即表明node节点为根节点
this.root = leftChild;
}else if(node.parent.rightChild == node){// 即node节点在它原父节点的右子树中
node.parent.rightChild = leftChild;
}else if(node.parent.leftChild == node){
node.parent.leftChild = leftChild;
}
leftChild.rightChild = node;
node.parent = leftChild;
return leftChild;
}
return null;
} //RR型非平衡树，左旋
public Node leftRotation(Node node){
System.out.println(node.val+"左旋");
if(node != null){
Node rightChild = node.rightChild;
node.rightChild = rightChild.leftChild;
if(rightChild.leftChild != null){
rightChild.leftChild.parent = node;
}
rightChild.parent = node.parent;
if(node.parent == null){
this.root = rightChild;
}else if(node.parent.rightChild == node){
node.parent.rightChild = rightChild;
}else if(node.parent.leftChild == node){
node.parent.leftChild = rightChild;
}
rightChild.leftChild = node;
node.parent = rightChild; }
return null;
} //添加新元素
public boolean put(int val){
return putVal(root,val);
}
private boolean putVal(Node node,int val){
if(node == null){// 初始化根节点
node = new Node(val);
root = node;
size++;
return true;
}
Node temp = node;
Node p;
int t;
/**
* 通过do while循环迭代获取最佳节点，
*/
do{
p = temp;
t = temp.val-val;
if(t > 0){
temp = temp.leftChild;
}else if(t < 0){
temp = temp.rightChild;
}else{
temp.val = val;//插入数值有相同数据，不符合要求
return false;
}
}while(temp != null); Node newNode = new Node(p, val);
if(t > 0){
p.leftChild = newNode;
}else if(t < 0){
p.rightChild = newNode;
}
rebuild(p);// 使二叉树平衡的方法，优化平衡
size++;
return true;
} //平衡二叉树优化节点
private void rebuild(Node p){
while(p != null){
if(calcNodeBalanceValue(p) == 2){// 说明左子树高，需要右旋或者 先左旋后右旋
fixAfterInsertion(p,LEFT);// 调整操作
}else if(calcNodeBalanceValue(p) == -2){// 说明右子树高
fixAfterInsertion(p,RIGHT);
}
p = p.parent;
}
} //计算二叉树平衡因子①
private int calcNodeBalanceValue(Node node){
if(node != null){
return getHeightByNode(node);
}
return 0;
} //计算二叉树平衡因子②
public int getHeightByNode(Node node){
if(node == null){//多余
return 0;
}
return getChildDepth(node.leftChild)-getChildDepth(node.rightChild);
} // 计算node节点的高度，递归调用
public int getChildDepth(Node node){
if(node == null){
return 0;
}
return 1+Math.max(getChildDepth(node.leftChild),getChildDepth(node.rightChild));
} /**
* 调整树结构，先后顺序需要换一下，先判断LR型和RL型进行二次旋转
* @param p
* @param type
*/
private void fixAfterInsertion(Node p, int type) {
if(type == 0){//需要右旋或者 先左旋后右旋
final Node leftChild = p.leftChild;
if(leftChild.rightChild != null){// 先左旋后右旋
leftRotation(leftChild);
rightRotation(p);
}else if(leftChild.leftChild != null){//右旋
rightRotation(p);
} }else{
final Node rightChild = p.rightChild;
if(rightChild.leftChild != null){// 先右旋，后左旋
rightRotation(p);
leftRotation(rightChild);
}else if(rightChild.rightChild != null){// 左旋
leftRotation(p);
}
}
} //删除元素
public boolean delete(int val){
Node node = getNode(val);//搜索这个节点的数值
if(node == null){
return false;
}
boolean flag = false;
Node p = null;
Node parent = node.parent;
Node leftChild = node.leftChild;
Node rightChild = node.rightChild;
//以下所有父节点为空的情况，则表明删除的节点是根节点
if(leftChild == null && rightChild == null){//没有子节点
if(parent != null){
if(parent.leftChild == node){
parent.leftChild = null;
}else if(parent.rightChild == node){
parent.rightChild = null;
}
}else{//不存在父节点，则表明删除节点为根节点
root = null;
}
p = parent;
node = null;
flag = true;
}else if(leftChild == null && rightChild != null){// 只有右节点
if(parent != null && parent.val > val){// 存在父节点，且node位置为父节点的左边
parent.leftChild = rightChild;
}else if(parent != null && parent.val < val){// 存在父节点，且node位置为父节点的右边
parent.rightChild = rightChild;
}else{
root = rightChild;
}
p = parent;
node = null;
flag = true;
}else if(leftChild != null && rightChild == null){// 只有左节点
if(parent != null && parent.val > val){// 存在父节点，且node位置为父节点的左边
parent.leftChild = leftChild;
}else if(parent != null && parent.val < val){// 存在父节点，且node位置为父节点的右边
parent.rightChild = leftChild;
}else{
root = leftChild;
}
p = parent;
flag = true;
}else if(leftChild != null && rightChild != null){// 两个子节点都存在
Node successor = getSuccessor(node);// 这种情况，一定存在后继节点
int temp = successor.val;
boolean delete = delete(temp);
if(delete){
node.val = temp;
}
p = successor;
successor = null;
flag = true;
}
if(flag){
rebuild(p);
}
return flag;
} /**
* 搜索节点
* @param val
* @return
*/
public Node getNode(int val){
Node temp = root;
int t;
do{//直接使用循环遍历的方法
t = temp.val-val;
if(t > 0){
temp = temp.leftChild;
}else if(t < 0){
temp = temp.rightChild;
}else{
return temp;
}
}while(temp != null);
return null;
} //获取后继节点
private Node getSuccessor(Node node){
if(node.rightChild != null){
Node rightChild = node.rightChild;
while(rightChild.leftChild != null){
rightChild = rightChild.leftChild;
}
return rightChild;
}
Node parent = node.parent;
while(parent != null && (node == parent.rightChild)){
node = parent;
parent = parent.parent;
}
return parent;
} /**
* 平衡二叉树节点遍历
* @param type 0前序，1中序，2后续，3层序
*/
public void print(int type){
if(type==0){//前序
printPre(root);
}else if(type==1){
printMid(root);
}else if(type==2){
printEnd(root);
}else if(type==3){
printLevel(root);
}
} //前序遍历
private void printPre(Node root){
if(root != null){
System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
printPre(root.leftChild);
printPre(root.rightChild);
}
} //中序遍历
private void printMid(Node root){
if(root != null){
printMid(root.leftChild);
System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
printMid(root.rightChild);
}
} //后序遍历
private void printEnd(Node root){
if(root != null){
printEnd(root.leftChild);
printEnd(root.rightChild);
System.out.println(root.val);// 位置在中间，则中序，若在前面，则为先序，否则为后续
}
} //层次遍历
private void printLevel(Node root){
if(root == null){
return;
}
Queue<Node> queue = new LinkedList<>();
Node temp = null;
queue.add(root);
while(!queue.isEmpty()){
temp = queue.poll();
System.out.print("节点值："+temp.val+",平衡值:"+calcNodeBalanceValue(temp)+"\n");
if(temp.leftChild != null){
queue.add(temp.leftChild);
}
if(temp.rightChild != null){
queue.add(temp.rightChild);
}
}
}
}
图2，BalanceBinaryTree.java结构图
3,JavaDemo.java
package com.cnblogs.mufasa.BalanceBinaryTree;
public class JavaDemo {
public static void main(String[] args) {
BalanceBinaryTree bbt=new BalanceBinaryTree();
// bbt.put(10);
// bbt.put(9);
// bbt.put(11);
// bbt.put(7);
// bbt.put(12);
// bbt.put(8);
// bbt.put(38);
// bbt.put(24);
// bbt.put(17);
// bbt.put(4);
// bbt.put(3);
bbt.put(11);
bbt.put(7);
bbt.put(15);
bbt.put(4);
bbt.put(9);
bbt.put(10);
bbt.print(3);
}
}
4，特别鸣谢
https://www.cnblogs.com/qm-article/p/9349681.html
最新文章
- 简易的IOS位置定位服务
- ocLazyLoad angular 按需加载
- Android简易数据存储之SharedPreferences
- bug 发表文章不显示图片
- mvcAPI （入门 3）(源码)
- zabbix通过sendmail进行邮箱警报
- 查找所有含有表名（abc）的存储过程 执行脚本
- Delphi XE7中新并行库
- Bootstrapping (compilers) - Wikipedia, the free encyclopedia
- IPSec VPN实验
- awk使用学习
- 转载：MySQL看这一篇就够了
- go tcp
- IIS7.0上传在大小限制
- Java基础——网络编程（三）
- 【linux基础】区块选择VisualBlock
- Kubernetes服务发现之Service详解
- leetcode110
- C#中的类
- axiso 生产环境跨域配置（可用）