主要实现思路为左旋转和右旋转
代码
package com.atguigu.avlTreeDemo;
import java.util.Objects;
public class AvlTreeDemo {
public static void main(String[] args) {
//左旋转测试开始
//左旋转测试结束
//双旋转测试开始
int[] rightRotate = {10,11,7,6,8,9};
AvlTree rightTree = new AvlTree();
for (int num:rightRotate) {
rightTree.add(new Node(num));
}
System.out.println("右旋转测试数的中序遍历结果为");
rightTree.infixOrder();
System.out.println("树的根节点为" + rightTree.root + "n树的高度为" + rightTree.hight() +
"n树的左子树的高度为" +rightTree.leftHight() + "n树的右子树的高度为" + rightTree.rightHight());
//双旋转测试结束
}
}
class AvlTree{
public Node root;
public AvlTree() {
}
public AvlTree(Node root) {
this.root = root;
}
public void leftRotate(){
if (root == null){
return;
}
root.leftRotate();
}
//添加节点
public void add(Node node){
if (root == null) {
root = node;
} else {
root.add(node);
}
}
//树的高度
public int hight(){
return root == null?0:root.hight();
}
//树的左子树的高度
public int leftHight(){
return root == null?0:root.leftHight();
}
//树的左子树的高度
public int rightHight(){
return root == null?0:root.righttHight();
}
//删除节点
public void del(int values){
//查看待删除的节点是否存在
if (searchNode(values) == null){
System.out.println("待删除的节点不存在");
}else {
Node delNode = searchNode(values);//寻找到待删除的节点
Node parent = searchParent(values);
boolean flag1 = (delNode.left != null);
boolean flag2 = (delNode.right != null);
boolean flagpar = !(parent == null);
Node temp;
if (!flag1 && !flag2){//如果待删除的节点是叶子结点,没有子节点
if (parent == null){//待删除的是根节点
root =null;
}else {//有父节点
if (parent.left != null && parent.left.equals(delNode)){
parent.left = null;
}else if (parent.right != null && parent.right.values == values){
parent.right = null;
}
}
}else if ( (flag1 && !flag2 )//如果删除的节点有一个子节点
||(!flag1 && flag2)){//只有一个子节点
if (flag1 && !flagpar){//没有父节点且左边有一个子节点，即根节点
root = delNode.left;
}else if (flag1 && flagpar){//有父节点且左边有一个子节点
if (parent.left != null && parent.left.values == values){//目标节点是父节点的左子节点
parent.left = delNode.left;
}else if (parent.right != null && parent.right.values == values){//目标节点是父节点的左子节点
parent.right = delNode.left;
}
}else if (flag2 && !flagpar){//没有父节点且右边有一个子节点，即根节点
root = delNode.right;
}else if (flag2 && flagpar){//有父节点且右边有一个子节点
if (parent.left != null && parent.left.values == values){//目标节点是父节点的左子节点
parent.left = delNode.right;
}else if (parent.right != null && parent.right.values == values){//目标节点是父节点的左子节点
parent.right = delNode.right;
}
}
}else if (flag1 && flag2){//如果待删除的节点有两个子节点
//法二：从左边找最大的
temp = delNode.left.fingMax();
del(delNode.left.fingMax().values);
delNode.values = temp.values;
}
}
}
//查找等待删除的节点是否存在
public Node searchNode(int values){
if (root.values == values){
return root;
}else{
return root.search(values);
}
}
//查找待删除的节点的父节点
public Node searchParent(int values){
if (root.values == values){
return null;
}else {
return root.searchParents(values);
}
}
//中序遍历
public void infixOrder(){
if (root == null){
System.out.println("空树");
}else{
root.infixOrder();
}
}
}
class Node{
public int values;//节点对应的值
Node left;//左子节点
Node right;//右子节点
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return values == node.values;
}
public void leftRotate(){
Node newNode = new Node(values);
newNode.left = left;
newNode.right = right.left;
left = newNode;
this.values = right.values;
right = right.right;
}
public void rightRotate(){
Node newNode = new Node(values);
newNode.right = right;
newNode.left =left.right;
this.values = left.values;
right = newNode;
left = left.left;
}
//得到以该节点为根节点的子树的高度
public int hight(){
return Math.max((left == null? 1: left.hight() + 1),
(right == null? 1:right.hight() +1));
}
//得到该节点的左子树的子树高度
public int leftHight(){
return (left == null)? 0: left.hight();
}
//得到该节点的右子树的子树高度
public int righttHight(){
return (right == null)? 0: right.hight();
}
//寻找一个节点下面的最小的节点
public Node fingMin(){
if (this.left == null ){
return this;
}else {
return this.left.fingMin();
}
}
//寻找一个节点下面的最大的节点
public Node fingMax(){
if (this.right == null ){
return this;
}else {
return this.right.fingMax();
}
}
@Override
public int hashCode() {
return Objects.hash(values);
}
//查找待删除的节点是否存在
public Node search(int values){
if (this.values == values){
return this;
}else if (this.left != null && this.values > values){
return this.left.search(values);
}else if (this.right != null && this.values <= values){
return this.right.search(values);
}else {
return null;
}
}
//查找待删除节点的父节点
public Node searchParents(int values){
if (this.values == values){
return null;
}
if ((this.left != null && this.left.values == values) ||
this.right != null && this.right.values == values ){
return this;
}else if (this.left != null && this.values > values){
return this.left.searchParents(values);
}else if (this.right != null && this.values <= values){
return this.right.searchParents(values);
}else {
return null;
}
}
public Node(Node left) {
this.left = left;
}
public Node(int values) {
this.values = values;
}
//中序遍历
public void infixOrder(){
if (this.left != null){
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null){
this.right.infixOrder();
}
}
//添加节点的方法
public void add(Node node){
if (node == null){
return;
}else{
if (node.values < this.values){
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);
}
}
if (righttHight() - leftHight() > 1){//当添加完一个节点后，右子树的高度比左子树高出超过1以及以上，进行左旋转
if (right != null && right.leftHight() > right.righttHight()){
right.leftRotate();
}
leftRotate();
}else if (leftHight() - righttHight() > 1){//当添加完一个节点后，左子树的高度比左子树高出超过1以及以上，进行右旋转
if (left != null && left.righttHight() > left.leftHight()){
left.leftRotate();
}
rightRotate();
}
}
}
@Override
public String toString() {
return "Node{" +
"values=" + values +
'}';
}
}
