如何使用Java來實現平衡二叉樹AVL?代碼詳解,高級Java工程師面試技術

Android我愛死你了 2021-09-20 04:46:34 阅读数:740

使用 java 平衡 二叉 avl
// 返回左子樹的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 返回右子樹的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
// 返回 以該結點為根結點的樹的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//左旋轉方法
private void leftRotate() {
//創建新的結點,以當前根結點的值
Node newNode = new Node(value);
//把新的結點的左子樹設置成當前結點的左子樹
newNode.left = left;
//把新的結點的右子樹設置成帶你過去結點的右子樹的左子樹
newNode.right = right.left;
//把當前結點的值替換成右子結點的值
value = right.value;
//把當前結點的右子樹設置成當前結點右子樹的右子樹
right = right.right;
//把當前結點的左子樹(左子結點)設置成新的結點
left = newNode;
}
//右旋轉
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的結點
/**
*
* @param value
* 希望删除的結點的值
* @return 如果找到返回該結點,否則返回null
*/
public Node search(int value) {
if (value == this.value) { // 找到就是該結點
return this;
} else if (value < this.value) {// 如果查找的值小於當前結點,向左子樹遞歸查找
// 如果左子結點為空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小於當前結點,向右子樹遞歸查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除結點的父結點
/**
*
* @param value
* 要找到的結點的值
* @return 返回的是要删除的結點的父結點,如果沒有就返回null
*/
public Node searchParent(int value) {
// 如果當前結點就是要删除的結點的父結點,就返回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小於當前結點的值, 並且當前結點的左子結點不為空
if (value < this.value && this.left != null) {
return this.left.searchParent(value); // 向左子樹遞歸查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); // 向右子樹遞歸查找
} else {
return null; // 沒有找到父結點
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
// 添加結點的方法
// 遞歸的形式添加結點,注意需要滿足二叉排序樹的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判斷傳入的結點的值,和當前子樹的根結點的值關系
if (node.value < this.value) {
// 如果當前結點左子結點為null
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 infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}

最後

本人也收藏了一份Java面試核心知識點來應付面試,借著這次機會可以送給我的讀者朋友們

目錄:

如何使用Java來實現平衡二叉樹AVL?代碼詳解,高級Java工程師面試技術_Java

Java面試核心知識點

 CodeChina開源項目:【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】

一共有30個專題,足够讀者朋友們應付面試啦,也節省朋友們去到處搜刮資料自己整理的時間!

如何使用Java來實現平衡二叉樹AVL?代碼詳解,高級Java工程師面試技術_Java_02

Java面試核心知識點

已經有讀者朋友靠著這一份Java面試知識點指導拿到不錯的offer了

如何使用Java來實現平衡二叉樹AVL?代碼詳解,高級Java工程師面試技術_後端_03

版权声明:本文为[Android我愛死你了]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210920044633595W.html