Java 代码实现平衡二叉树
最近一直在看数据结构的相关内容，对于平衡二叉树这一节，理论看起很简单，无非是判断结点的平衡因子是否绝对值小于2。在插入或者删除之后进行相应的旋转调整。
我已开始试着按照书上所讲的内容进行编程，但是书上的代码皆是伪代码，只是告诉你一个思路，按照书上是实现不出来的，所以我决定在已有理论的情况下，试着按照自己的想法编程。
因为在前面的博客中，我已经介绍过了一般的二叉树的插入、删除等操作，树结点的排列顺序也是左子树小于根节点，右子树大于根节点。
在平衡二叉树中，查找、遍都与之前的没有区别，不再做介绍。
在这里就在代码中简单的解释一下，具体的可以去看之前的博客。
在这里首先说一下对不平衡二叉树的调整，一共存在四种情况：LL，LR，RR，RL
LL旋转
/*
* 对最小不平衡子树进行LL旋转
* parent：最小不平衡子树的双亲
* preNode：最小不平衡子树的根节点
*/
public void tuneLL (AVLTreeNode preNode, AVLTreeNode parent) {
// 以current为中心进行旋转
AVLTreeNode current = preNode.left;
preNode.left = current.right;
current.right = preNode;
// 如果最小不平衡二叉树的双亲结点为空，说明整棵平衡二叉树都是不平衡的
// 旋转完成之后，对root结点重新进行赋值
if (parent == null) {
root = current;
} else {
// 判断最小不平衡子树是parent的左子树还是右子树
boolean isLeft = parent.left == preNode;
if (isLeft) {
parent.left = current;
} else {
parent.right = current;
}
}
// 重新调整树节点的高度
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right))+1;
current.height = Math.max(getHeight(current.left), preNode.height) + 1;
}
RR旋转
/*
* 对最小不平衡二叉树进行RR旋转
* 相应参数参照LL旋转
*/
public void tuneRR (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.right;
preNode.right = current.left;
current.left = preNode;
if (parent == null) {
root = current;
} else {
if (parent.left == preNode) {
parent.left = current;
} else {
parent.right = current;
}
}
// 重新调整结点的高度
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right))+1;
current.height = Math.max(preNode.height, getHeight(current.right))+1;
}
LR旋转
/*
* 对最小不平衡二叉树进行LR旋转
* 先左旋再右旋
* 具体参数以及解释参照以上旋转方法
*/
public void tuneLR (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.left;
AVLTreeNode node = current.right;
current.right = node.left;
node.left = current;
preNode.left = node.right;
node.right = preNode;
if (parent == null) {
root = node;
} else {
if (parent.left == preNode) {
parent.left = node;
} else {
parent.right = node;
}
}
// 重新调整结点的高度
// 在这里，三个结点都发生了调整，那么对应的高度也都需要重新调整
current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right)) + 1;
node.height = Math.max(current.height, preNode.height) + 1;
}
RL旋转
/*
* 对最小不平衡二叉树进行RL旋转
* 先右旋再左旋
* 参数说明同上
*/
public void tuneRL (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.right;
AVLTreeNode node = current.left;
current.left = node.right;
node.right = current;
preNode.right = node.left;
node.left = preNode;
if (parent == null) {
root = node;
} else {
if (parent.left == preNode) {
parent.left = node;
} else {
parent.right = node;
}
}
// 重新调整结点的高度
// 对三个结点进行调整
current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right)) + 1;
node.height = Math.max(current.height, preNode.height) + 1;
}
1、插入结点
基本思路：同样需要找到需要插入的位置，但是在这里还需要记录到达插入位置所经过的结点，在完成插入之后，根据这些结点，依次检查平衡因子是否符合平衡二叉树的要求。
在这里使用栈存储所经过的结点，之后依次弹栈，检查平衡因子。
/*
* 插入结点
*/
public void insertAVLNode (int data) {
// 对结点进行封装
AVLTreeNode node = new AVLTreeNode(data);
AVLTreeNode current = root;
AVLTreeNode preNode = null;
AVLTreeNode parent = null;
// 标记需要插入的位置是左结点还是右结点
boolean isLeft = false;
// 使用栈保存插入路径中经过的结点
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
// 平衡二叉树为空
if (root == null) {
root = node;
return;
} else { //平衡二叉树不为空
while (current != null) {
preNode = current;
stack.add(current);
if (current.data > data) {
current = current.left;
isLeft = true;
} else {
current = current.right;
isLeft = false;
}
}
// 退出循环是因为走到了空结点
// 进行实际的插入操作
if (isLeft) {
preNode.left = node;
} else {
preNode.right = node;
}
// 弹出栈 ， 并找到平衡因子不合适的结点
while (!stack.isEmpty()) {
preNode = stack.pop(); // 用于记录最小不平衡二叉树的根结点
// 之前弹过栈顶元素，当前栈很可能是空栈
// 取栈顶元素之前，需要判断栈是否为空
if (stack.isEmpty()) {
// 栈为空，说明刚刚取出的preNode是root，root的双亲不存在设置为空
parent = null;
} else {
parent = stack.peek();
}
// 调整 ： 先重新设置高度，再进行平衡因子判断，进而进行相应的旋转；
// 栈中的每个结点都需要查看一遍，因为每个结点都可能会发生不平衡，
// 同时，每个结点的高度都需要重新调整，以备下次操作使用。
rotateNode(preNode, parent);
}
}
}
rotateNode方法
/*
* 对指定结点进行调整
*/
public void rotateNode (AVLTreeNode current, AVLTreeNode parent) {
// 在判断平衡因子之前，先对当前结点更新高度
current.height = Math.max(getHeight(current.left), getHeight(current.right))+1;
// 对于LL和LR型旋转，只要不是LL型，其他的都可以看做是LR型
// 在这里是为了防止发生：结点的平衡因子是2，其孩子结点的平衡因子出现0的情况
// RR与RL也是类似的
if (getBalance(current) == 2) {
if (getBalance(current.left) == 1) { // LL
tuneLL(current, parent);
} else { // 非LL皆LR
tuneLR(current, parent);
}
} else if (getBalance(current) == -2) {
if (getBalance(current.right) == -1) { // RR
tuneRR(current, parent);
} else { // 非RR
tuneRL(current, parent);
}
}
}
getHeight（）与getBalance（）参考最后完整代码
2、删除结点
基本思路：首先也是需要找到所要删除的结点，在这个过程中，同样需要使用栈保存所经过的结点。完成删除后，依次弹栈，对不平衡的二叉树进行调整。
在这里有种特殊情况：当删除的结点的左右子树都存在时，那么需要找到删除结点的最小中序后继结点，并将其代替删除结点的位置，并将最小中序后继结点删除。这个过程是在删除结点的右子树上进行的，那么就有可能会造成该右子树的不平衡；所以，在找最小中序后继的时候，同样需要保存所经过的结点，完成最小后继结点的删除之后，对该右子树进行调整，使其成为平衡二叉子树。
因为在之前的其他情况下，栈顶元素是所要删除的结点的双亲结点，所以为了在编程上实现统一，在完成结点的替换（在这里就相当于删除）之后，先对该结点进行一次更新调整。
其他的情况只需要最后统一更新调整即可。
/*
* 删除结点
*/
public AVLTreeNode deleteNode (int data) {
// 平衡二叉树为空，直接返回null
if (root == null) {
return null;
} else {
// 栈stack用于保存所经过的结点
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode node = null;
AVLTreeNode current = root;
AVLTreeNode parent = null;
// 判断删除结点位于其双亲结点的左子树还是右子树
boolean isLeft = false;
while (current != null && current.data != data) {
stack.add(current);
parent = current;
if (current.data > data) {
current = current.left;
isLeft = true;
} else {
current = current.right;
isLeft = false;
}
}
// 判断退出循环的条件
if (current == null) { // 没有找到想要删除的结点
return null;
}
// current 指向需要删除的结点
if (current.left == null && current.right == null) { // 删除的结点是叶子结点
// 判断当前结点是否为空
if (current == root) {
root = null;
} else {
if (isLeft) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (current.left == null) { // 删除结点只有右孩子
if (current == root) {
root = current.right;
} else {
if (isLeft) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
} else if (current.right == null) { // 删除结点只有左孩子
if (current == root) {
root = current.left;
} else {
if (isLeft) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
} else {
// 删除的结点既有左孩子也有右孩子
// 需要找到当前结点的最小中序后继
AVLTreeNode succNode = getMinSuccNode(current);
succNode.left = current.left;
succNode.right = current.right;
if (current == root) {
root = succNode;
} else {
if (isLeft) {
parent.left = succNode;
} else {
parent.right = succNode;
}
// 删除结点存在左右孩子结点，那么在完成删除时，先对其进行一次调整
// 单独对其进行一次调整
rotateNode(succNode, parent);
}
}
// 开始旋转调整
if (stack.isEmpty()) { // 说明处理的是root结点，接下来对root结点进行调整即可
rotateNode(root, parent);
} else { // 处理的结点是一般的结点
while (!stack.isEmpty()) {
node = stack.pop();
if (stack.isEmpty()) {
parent = null;
} else {
parent = stack.peek();
}
rotateNode(node, parent);
}
}
return current;
}
}
得到当前结点的最小中序后继结点
/*
* 得到指定结点的最小中序后继
* 在这里是特殊情况：当前结点有右孩子，所以只需在右子树中找最左结点即可
*/
public AVLTreeNode getMinSuccNode (AVLTreeNode current) {
// 栈stack用于保存所经过的结点
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode oldCurrent = current;
AVLTreeNode node = null;
AVLTreeNode parent = current;
current = current.right;
// 在右子树中一直往左孩子寻找，直到为空结点
while (current.left != null) {
stack.add(current);
parent = current;
current = current.left;
}
// 找到最小中序后继，并将其在所在的子树中删除
if (current == parent.right) {
// 如果当前结点的最小中序后继就是该结点的右孩子，那么直接删除，
// 无需这一步调整当前结点右子树的高度
parent.right = current.right;
} else {
// 如果当前结点的最小后继是该结点右子树的最左边的孩子，那么将该孩子删除，
// 并在当前结点的右子树中调整高度并进行合适的旋转调整
parent.left = current.right;
// 栈顶保存了所需要的最小中序后继结点，先将其弹出
stack.pop();
while (!stack.isEmpty()) {
node = stack.pop();
if (stack.isEmpty()) {
parent = oldCurrent;
} else {
parent = stack.peek();
}
rotateNode(node, parent);
}
}
return current;
}
3、程序测试
/*
* main函数 测试
*/
public static void main (String[] args) {
AVLTree avlTree = new AVLTree();
// 4 2 1 测试LL型旋转 最小不平衡二叉树为整颗树
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(2);
// avlTree.insertAVLNode(1);
// 6 4 8 2 1 测试LL型旋转 最小不平衡二叉树是一般的树
// avlTree.insertAVLNode(6);
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(8);
// avlTree.insertAVLNode(2);
// avlTree.insertAVLNode(1);
// 测试RR型调整
// 4 6 7
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(6);
// avlTree.insertAVLNode(7);
// 4 2 6 7 8
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(2);
// avlTree.insertAVLNode(6);
// avlTree.insertAVLNode(7);
// avlTree.insertAVLNode(8);
// 测试LR型旋转
// 4 2 3
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(2);
// avlTree.insertAVLNode(3);
// 5 6 4 2 3
// avlTree.insertAVLNode(5);
// avlTree.insertAVLNode(6);
// avlTree.insertAVLNode(4);
// avlTree.insertAVLNode(2);
// avlTree.insertAVLNode(3);
// 测试RL型旋转
// 5 7 6
// avlTree.insertAVLNode(5);
// avlTree.insertAVLNode(7);
// avlTree.insertAVLNode(6);
// 4 2 5 7 6
avlTree.insertAVLNode(4);
avlTree.insertAVLNode(2);
avlTree.insertAVLNode(5);
avlTree.insertAVLNode(7);
avlTree.insertAVLNode(6);
avlTree.levelTraversal();
System.out.println();
avlTree.preTrasersal();
System.out.println();
avlTree.inTrasersal();
System.out.println();
avlTree.postTraversal();
// avlTree.deleteNode(2);
// avlTree.deleteNode(7);
// avlTree.deleteNode(6);
// avlTree.deleteNode(5);
// avlTree.deleteNode(2);
// avlTree.deleteNode(2);
//
// System.out.println();
// avlTree.levelTraversal();
// System.out.println();
// avlTree.preTrasersal();
// System.out.println();
// avlTree.inTrasersal();
// System.out.println();
// avlTree.postTraversal();
// if (avlTree.findNode(6) != null) {
// System.out.println(avlTree.findNode(6).data);
// }
}
在这里，为了验证程序的正确性，准备的测试用例很多，大家可以自行复制代码运行查看！
有什么问题随时交流学习！欢迎评论！
完整代码：
public class AVLTreeNode {
public int data;
public int height;
public AVLTreeNode left;
public AVLTreeNode right;
/*
* 构造函数
*/
public AVLTreeNode (int data) {
this.data = data;
height = 1;
left = null;
right = null;
}
/*
* 在这里将结点类设置成public，就不再需要设置set、get函数了
* 在类外直接就可以访问到
*/
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class AVLTree {
public AVLTreeNode root;
/*
* 构造函数
*/
public AVLTree () {
root = null;
}
/*
* 插入结点
*/
public void insertAVLNode (int data) {
// 对结点进行封装
AVLTreeNode node = new AVLTreeNode(data);
AVLTreeNode current = root;
AVLTreeNode preNode = null;
AVLTreeNode parent = null;
boolean isLeft = false;
// 使用栈保存插入路径中经过的结点
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
// 平衡二叉树为空
if (root == null) {
root = node;
return;
} else { //平衡二叉树不为空
while (current != null) {
preNode = current;
stack.add(current);
if (current.data > data) {
current = current.left;
isLeft = true;
} else {
current = current.right;
isLeft = false;
}
}
// 退出循环是因为走到了空结点
// 进行实际的插入操作
if (isLeft) {
preNode.left = node;
} else {
preNode.right = node;
}
// 弹出栈 ， 并找到平衡因子不合适的结点
while (!stack.isEmpty()) {
preNode = stack.pop(); // 最小不平衡二叉树的根结点
// 取栈顶元素之前，需要判断栈是否为空
if (stack.isEmpty()) {
parent = null;
} else {
parent = stack.peek();
}
// 调整
rotateNode(preNode, parent);
}
}
}
/*
* 删除结点
*/
public AVLTreeNode deleteNode (int data) {
if (root == null) {
return null;
} else {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode node = null;
AVLTreeNode current = root;
AVLTreeNode parent = null;
boolean isLeft = false;
while (current != null && current.data != data) {
stack.add(current);
parent = current;
if (current.data > data) {
current = current.left;
isLeft = true;
} else {
current = current.right;
isLeft = false;
}
}
// 判断退出循环的条件
if (current == null) { // 没有找到想要删除的结点
return null;
}
// current 指向需要删除的结点
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
} else {
if (isLeft) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (current.left == null) { // 删除结点只有右孩子
if (current == root) {
root = current.right;
} else {
if (isLeft) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
} else if (current.right == null) { // 删除结点只有左孩子
if (current == root) {
root = current.left;
} else {
if (isLeft) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
} else {
// 需要找到当前结点的最小中序后继
AVLTreeNode succNode = getMinSuccNode(current);
succNode.left = current.left;
succNode.right = current.right;
if (current == root) {
root = succNode;
} else {
if (isLeft) {
parent.left = succNode;
} else {
parent.right = succNode;
}
// 删除结点存在左右孩子结点，那么在完成删除时，先对其进行一次调整
rotateNode(succNode, parent);
}
}
// 开始旋转调整
if (stack.isEmpty()) { // 说明处理的是root结点，接下来对root结点进行调整即可
rotateNode(root, parent);
} else { // 处理的结点是一般的结点
while (!stack.isEmpty()) {
node = stack.pop();
if (stack.isEmpty()) {
parent = null;
} else {
parent = stack.peek();
}
rotateNode(node, parent);
}
}
return current;
}
}
/*
* 得到指定结点的最小中序后继
* 在这里是特殊情况：当前结点有右孩子，所以只需在右子树中找最左结点即可
*/
public AVLTreeNode getMinSuccNode (AVLTreeNode current) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode oldCurrent = current;
AVLTreeNode node = null;
AVLTreeNode parent = current;
current = current.right;
while (current.left != null) {
stack.add(current);
parent = current;
current = current.left;
}
// 找到最小中序后继，并将其在所在的子树中删除
if (current == parent.right) {
// 如果当前结点的最小中序后继就是该结点的右孩子，那么直接删除，
// 无需这一步调整当前结点右子树的高度
parent.right = current.right;
} else {
// 如果当前结点的最小后继是该结点右子树的最左边的孩子，那么将该孩子删除，
// 并在当前结点的右子树中调整高度并进行核实的旋转调整
parent.left = current.right;
// 栈顶保存了所需要的最小中序后继结点，先将其弹出
stack.pop();
while (!stack.isEmpty()) {
node = stack.pop();
if (stack.isEmpty()) {
parent = oldCurrent;
} else {
parent = stack.peek();
}
rotateNode(node, parent);
}
}
return current;
}
/*
* 对指定结点进行调整
*/
public void rotateNode (AVLTreeNode current, AVLTreeNode parent) {
current.height = Math.max(getHeight(current.left), getHeight(current.right))+1;
if (getBalance(current) == 2) {
if (getBalance(current.left) == 1) {
tuneLL(current, parent);
} else {
tuneLR(current, parent);
}
} else if (getBalance(current) == -2) {
if (getBalance(current.right) == -1) {
tuneRR(current, parent);
} else {
tuneRL(current, parent);
}
}
}
/*
* 查找结点
*/
public AVLTreeNode findNode (int data) {
if (root == null) {
return null;
} else {
AVLTreeNode current = root;
while (current != null) {
if (current.data == data) {
return current;
} else if (current.data > data) {
current = current.left;
} else {
current = current.right;
}
}
return null;
}
}
/*
* 层次遍历平衡二叉树
*/
public void levelTraversal () {
Queue<AVLTreeNode> queue = new LinkedList<AVLTreeNode>();
AVLTreeNode current = root;
if (root != null) {
queue.offer(current);
while (!queue.isEmpty()) {
current = queue.poll();
System.out.print(current.data + " ");
// 输出树的高度进行验证是否完成高度的更新
// System.out.println(current.data + " " + current.height);
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
}
}
/*
* 非递归前序遍历
*/
public void preTrasersal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
stack.add(current);
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.data + " ");
if (current.right != null) {
stack.add(current.right);
}
if (current.left != null) {
stack.add(current.left);
}
}
}
}
/*
* 非递归中序遍历
*/
public void inTrasersal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
while (current != null) {
stack.add(current);
current = current.left;
}
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.data + " ");
current = current.right;
while (current != null) {
stack.add(current);
current = current.left;
}
}
}
}
/*
* 非递归后序遍历
*/
public void postTraversal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
AVLTreeNode preNode = null;
while (current != null) {
stack.add(current);
current = current.left;
}
while (!stack.isEmpty()) {
current = stack.pop();
if (current.right == null || current.right == preNode) {
System.out.print(current.data + " ");
preNode = current;
} else {
stack.add(current);
current = current.right;
while (current != null) {
stack.add(current);
current = current.left;
}
}
}
}
}
/*
* 当前结点的平衡因子
* 左子树高度-右子树高度
*/
public int getBalance (AVLTreeNode node) {
if ((node == null) || (node.left == null && node.right == null)) {
return 0;
} else if (node.right != null && node.left == null) {
return node.right.height*(-1);
} else if (node.left != null && node.right == null) {
return node.left.height;
} else {
return node.left.height-node.right.height;
}
}
/*
* 当前结点的高度
*/
public int getHeight (AVLTreeNode node) {
if (node == null) {
return 0;
} else {
return node.height;
}
}
/*
* 对最小不平衡子树进行LL旋转
*/
public void tuneLL (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.left;
preNode.left = current.right;
current.right = preNode;
if (parent == null) {
root = current;
} else {
boolean isLeft = parent.left == preNode;
if (isLeft) {
parent.left = current;
} else {
parent.right = current;
}
}
// 重新调整树节点的高度
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right))+1;
current.height = Math.max(getHeight(current.left), preNode.height) + 1;
}
/*
* 对最小不平衡二叉树进行RR旋转
*/
public void tuneRR (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.right;
preNode.right = current.left;
current.left = preNode;
if (parent == null) {
root = current;
} else {
if (parent.left == preNode) {
parent.left = current;
} else {
parent.right = current;
}
}
// 重新调整结点的高度
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right))+1;
current.height = Math.max(preNode.height, getHeight(current.right))+1;
}
/*
* 对最小不平衡二叉树进行LR旋转
*/
public void tuneLR (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.left;
AVLTreeNode node = current.right;
current.right = node.left;
node.left = current;
preNode.left = node.right;
node.right = preNode;
if (parent == null) {
root = node;
} else {
if (parent.left == preNode) {
parent.left = node;
} else {
parent.right = node;
}
}
// 重新调整结点的高度
current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right)) + 1;
node.height = Math.max(current.height, preNode.height) + 1;
}
/*
* 对最小不平衡二叉树进行RL旋转
*/
public void tuneRL (AVLTreeNode preNode, AVLTreeNode parent) {
AVLTreeNode current = preNode.right;
AVLTreeNode node = current.left;
current.left = node.right;
node.right = current;
preNode.right = node.left;
node.left = preNode;
if (parent == null) {
root = node;
} else {
if (parent.left == preNode) {
parent.left = node;
} else {
parent.right = node;
}
}
// 重新调整结点的高度
current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
preNode.height = Math.max(getHeight(preNode.left), getHeight(preNode.right)) + 1;
node.height = Math.max(current.height, preNode.height) + 1;
}
}
转载：https://blog.csdn.net/m0_37683327/article/details/102478556
查看评论