一、介绍
二、思路
三、代码
/**
* @Description 平衡二叉树
* 说明：当前节点的(左子节点的高度-右子节点的高度) > 1 说明此棵树为不平衡二叉树
* @Author Meng
* @Versions
* @Date 2021-07-29-15:33
*/
public class AVLTreeDemo {
public static void main(String[] args) {
// int[] array = {4, 3, 6, 5, 7, 8};
// int[] array = {1,2,3,4,5};
int[] array = {10, 11, 7, 6, 8, 9};
AVLTree avlTree = new AVLTree();
// 构造BST树
for (int i : array) {
avlTree.add(new Node(i));
}
// 中序遍历
avlTree.infixSort(avlTree.getRoot());
Node root = avlTree.getRoot();
System.out.println("整棵树的高度：" + root.height());
System.out.println("左子树的高度：" + root.leftHeight());
System.out.println("右子树的高度：" + root.rightHeight());
System.out.println("根节点：" + root);
System.out.println("左子节点：" + root.left);
System.out.println("右子节点点：" + root.right);
}
}
/**
* 平衡二叉树
*/
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
/**
* 中序遍历
*
* @param node 根节点
*/
public void infixSort(Node node) {
if (node == null) {
return;
} else {
node.infixSort();
}
}
/**
* 删除的结点
*
* @param value 待删除的节点
* @return
*/
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
/**
* 查找父结点
*
* @param value 查找 value的父节点
* @return 返回value的父节点
*/
public Node parentSearch(int value) {
if (root == null) {
return null;
} else {
return root.parentSearch(value);
}
}
/**
* 删除node 为根结点的二叉排序树的最小结点
*
* @param node 传入的结点(当做二叉排序树的根结点)
* @return 返回的 以node 为根结点的二叉排序树的最小结点的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
//循环的查找左子节点，就会找到最小值
while (target.left != null) {
target = target.left;
}
//这时 target就指向了最小结点
//删除最小结点
delNode(target.value);
return target.value;
}
/**
* 删除节点
*
* @param value 需要删除的节点
*/
public void delNode(int value) {
if (root == null) {
return;
} else {
// 删除的节点
Node targetNode = search(value);
if (targetNode == null) {
System.out.println("没有找到要删除的节点~~~");
return;
}
// 若根节点没有左子节点和右子节点，那么也就不会有父节点了，直接将根节点置为null
if (root.left == null && root.right == null) {
root = null;
return;
}
// 待删除节点的父节点
Node parentNode = parentSearch(value);
// 若待删除的节点时叶子节点---叶子节点下面没有其他节点
if (targetNode.left == null && targetNode.right == null) {
if (parentNode.left != null && parentNode.left.value == value) {
parentNode.left = null;
}
if (parentNode.right != null && parentNode.right.value == value) {
parentNode.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
int i = delRightTreeMin(targetNode.right);
targetNode.value = i;
} else { // 待删除的节点有左子节点或右子节点
// 若待删除的节点是parentNode的左节点
if (parentNode.left.value == targetNode.value) {
// 且待删除的节点有左子节点
if (targetNode.left != null) {
parentNode.left = targetNode.left;
}
// 或者待删除节点有右子节点
if (targetNode.right != null) {
parentNode.left = targetNode.right;
}
}
// 若待删除的节点是parentNode的右节点
if (parentNode.right.value == targetNode.value) {
// 且待删除的节点有左子节点
if (targetNode.left != null) {
parentNode.right = targetNode.left;
}
// 或者待删除节点有右子节点
if (targetNode.right != null) {
parentNode.right = targetNode.right;
}
}
}
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* 搜索vale对应节点的父节点
*
* @param value 要找到的结点的值
* @return 返回的是要删除的结点的父结点，如果没有就返回null
*/
public Node parentSearch(int value) {
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
if (this.left != null && value < this.value) {
return this.left.parentSearch(value);
} else if (this.right != null && value > this.value) {
return this.right.parentSearch(value);
} else {
return null;
}
}
}
/**
* 搜索节点
*
* @param value 具体的值
* @return
*/
public Node search(int value) {
if (this.value == value) {
return this;
}
if (this.value > value) {
if (this.left != null) {
return this.left.search(value);
} else {
return null;
}
} else if (this.value < value) {
if (this.right != null) {
return this.right.search(value);
} else {
return null;
}
} else {
return null; // 表示没有找到
}
}
/**
* 二叉排序树添加节点
*
* @param node
*/
public void add(Node node) {
// 判断传进来的节点是否为空
if (node == null) {
return;
}
if (this.value > node.value) {
// 向左子树找插入位置
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
if(rightHeight() - leftHeight() > 1) {
//如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if(right != null && right.leftHeight() > right.rightHeight()) {
//先对右子结点进行右旋转
right.rightRotate();
//然结点后在对当前进行左旋转
leftRotate(); //左旋转..
} else {
//直接进行左旋转即可
leftRotate();
}
return ; //必须要!!!
}
//当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
if(leftHeight() - rightHeight() > 1) {
//如果它的左子树的右子树高度大于它的左子树的高度
if(left != null && left.rightHeight() > left.leftHeight()) {
//先对当前结点的左结点(左子树)->左旋转
left.leftRotate();
//再对当前结点进行右旋转
rightRotate();
} else {
//直接进行右旋转即可
rightRotate();
}
}
}
/**
* 将整棵树左旋转
*/
public void leftRotate(){
// 创建一个和根节点一样的新节点
Node newNode = new Node(this.value);
// 将newNode.left 指向 根节点的左子节点
newNode.left = this.left;
// 将newNode.right 指向当前节点的 右子节点 的 左子节点
newNode.right = this.right.left;
// 将当前节点的值 替换成 当前节点的右子节点的值
this.value = this.right.value;
// 将当前节点的左子节点指向新节点
this.left = newNode;
// 将当前节点的右子节点指向当前节点的右子节点的右子节点
this.right = this.right.right;
}
/**
* 将整棵树右旋转
*/
public void rightRotate(){
// 创建一个和根节点一样的新节点
Node newNode = new Node(this.value);
// 将newNode.right 指向 根节点的右子节点
newNode.right = this.right;
// 将newNode.left 指向当前节点的 左子节点 的 右子节点
newNode.left = this.left.right;
// 将当前节点的值 替换成 当前节点的左子节点的值
this.value = this.left.value;
// 将当前节点的右子节点指向新节点
this.right = newNode;
// 将当前节点的左子节点指向当前节点的左子节点的左子节点
this.left = this.left.left;
}
/**
* 当前节点左子树的高度
*
* @return
*/
public int leftHeight() {
if (this.left != null) {
return this.left.height();
} else {
return 0;
}
}
/**
* 当前节点右子树的高度
*
* @return
*/
public int rightHeight() {
if (this.right != null) {
return this.right.height();
} else {
return 0;
}
}
/**
* 返回 以该结点为根结点的树的高度
*/
public int height() {
Node target = this;
int count = 0;
// 遍历当前节点的左子树
while (target.left != null) {
target = target.left;
count++;
}
target = this;
int count1 = 0;
while (target.right != null) {
target = target.right;
count1++;
}
return Math.max(count, count1) + 1;
}
/*public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}*/
/**
* 中序遍历
*/
public void infixSort() {
// 先遍历左子树
if (this.left != null) {
this.left.infixSort();
}
System.out.println(this);
// 在遍历右子树
if (this.right != null) {
this.right.infixSort();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
京公网安备 11010502036488号