引言
前两篇文章中，我们学习了二叉树的结构、性质、实现以及应用，它的操作时间复杂度为O(lgn),但注意这个复杂度从严格意义上来说不太准确，在某一棵子树子树的深度远远大于另外一颗子树时，查找效率会上升到O(n),如下面的情况:
二叉树特例-单枝二叉树(图片来自泽坚博客).png
从上图可以看出，按照排序数组构建二叉树时，它变成了单向的二叉树，本质和链表没什么区别，操作复杂度为O(n)。这个问题该如何解决呢?我们引入"子树平衡"这一性质，来保证左右的叶子节点不会"埋"的太深，这种树被称为平衡二叉树。
平衡二叉树具有如下性质:
1.具备二叉排序树的所有性质；
2.左右子树的高度相差绝对值不大于1;
3.左右子树均为平衡二叉树.
本文我们规定叶子节点的高度为0，空节点高度为-1，父节点高度为左右子树中较大高度+1。
二叉树的失衡情况分析
当左右子树的高度相差大于等于2时，表示该根节点失衡，共有四种失衡情况:
① 左子树的左子树高度-左子树的右子树高度>=2,简称为LL型;
②左子树的右子树高度-左子树的左子树高度>=2,简称LR型;
③右子树的左子树高度-右子树的右子树高度>=2,简称为RL型;
④ 右子树的右子树高度-右子树的左子树高度>=2,简称RR型;
其中① 和④ 为一对，需要做但旋转；②和③为一对，需要做双旋转。下面详细分析。
先看看节点结构,和搜索树相比，多了高度字段，用于平衡性判断。
package tree.avltree;
/**
* Created by chenming on 2018/6/5
* 平衡二叉树节点,多了高度字段
*/
public class AVLNode<T extends Comparable> {
public AVLNode<T> left;//左结点
public AVLNode<T> right;//右结点
public T data;
public int height;//当前结点的高度
public AVLNode(T data) {
this(null, null, data);
}
public AVLNode(AVLNode<T> left, AVLNode<T> right, T data) {
this(left, right, data, 0);
}
public AVLNode(AVLNode<T> left, AVLNode<T> right, T data, int height) {
this.left = left;
this.right = right;
this.data = data;
this.height = height;
}
/**
* 判断是否为叶子结点
*
* @return
*/
public boolean isLeaf() {
return this.left == null && this.right == null;
}
}
LL型单旋
LL型单旋如下图图1:
LL单旋.png
当x的左子树w的左子树高度为2，而x的右子树高度为1，导致x节点失衡，需要以x为中心做右旋操作，结构变成图2，w变成根节点，x变成w的右子树，w的右子树挂载到x的左边，二叉树重新平衡。旋转操作后，只需要更新w与x的高度即可。LL右旋代码如下:
/**
* 向左子树的左节点插入元素,执行右旋操作
*
* @param x
* @return
*/
private AVLNode<T> singleRotateLeft(AVLNode<T> x) {
AVLNode<T> w = x.left;
x.left = w.right;
w.right = x;
//重新计算x w的高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
w.height = Math.max(height(w.left), x.height) + 1;
return w;
}
RR型单旋
RR型号单旋如下图1:
RR型单旋.png
RR型与LL型正好对称，x的右子树导致失衡，需要将x左旋，旋转后结构如图2.x为根节点，w为x的左子树，x的左子树挂载到w的右子树上。此时，树重新获得平衡。然后更新w和x的高度即可。代码如下:
/**
* 向右子树的右节点插入元素,执行左旋操作
*
* @param w
* @return
*/
private AVLNode<T> singleRotateRight(AVLNode<T> w) {
AVLNode<T> x = w.right;
w.right = x.left;
x.left = w;
//重新计算x/w的高度
w.height = Math.max(height(w.left), height(w.right)) + 1;
x.height = Math.max(height(x.left), w.height) + 1;
//返回新的根结点
return x;
}
RL和LR双旋转
对于RL和LR，仅仅做单旋转无法恢复平衡，看下图:
LR双旋操作.png
Y的高度为2，仅做LL单旋的话，如图2，无法恢复平衡，此时需要双旋转实现平衡，先处理好w子树，将Y做左旋转，然后再对Y做右旋转.操作流程如下图:
LR双旋转.png
先将y以w为中心做右旋，然后将y以x为中心做右旋。双旋后的结构如图3,根节点为y,它的子树被拆分到两个子树w和x上，实现树的"扁平化"。由于是基于单旋操作，代码实现比较简单:
/**
* 往左子树的右孩子插入节点,左右双旋
*/
private AVLNode<T> doubleRotateWithLeft(AVLNode<T> x) {
//w先进行右右单旋转
x.left = singleRotateRight(x.left);
//x进行左左但旋
return singleRotateLeft(x);
}
相对应的LR双旋转操作流程如下图:
RL双旋.png
旋转原理和LR一样，这里不再废话了，大家看图就能明白。代码:
/**
* 右左旋转(RL旋转)
*
* @param x
* @return
*/
private AVLNode<T> doubleRotateWithRight(AVLNode<T> x) {
//先进行LL旋转
x.right = singleRotateLeft(x.right);
//再进行RR旋转
return singleRotateRight(x);
}
好了，本篇最核心的内容分析完毕，下面分析平衡二叉树的构建和删除操作，遵循下面两条原则:
1>判断平衡性,如果不平衡需要走2>
2>分析操作节点属于哪种旋转类型;
3>操作完成后，别忘记更新新节点高度.
平衡二叉树的构建
/**
* 平衡二叉树的插入操作
*
* @param data
* @param p
* @return
*/
private AVLNode<T> insert(T data, AVLNode<T> p) {
if (p == null) {
p = new AVLNode<>(data);
} else if (data.compareTo(p.data) < 0) {//向左子树寻找插入位置{
p.left = insert(data, p.left);
if (height(p.left) - height(p.right) == 2) {//子树高度差为2,需要平衡
if (data.compareTo(p.left.data) < 0) {//往左边插入LL单旋转
p = singleRotateLeft(p);
} else {
p = doubleRotateWithLeft(p);//往左边插入LR双旋转
}
}
} else if (data.compareTo(p.data) > 0) {//向右子树寻找插入位置
p.right = insert(data, p.right);
if (height(p.right) - height(p.left) == 2) {
if (data.compareTo(p.right.data) < 0) {
//进行RL双旋转
p = doubleRotateWithRight(p);
} else {
//进行RR单旋
p = singleRotateRight(p);
}
}
}
//重新计算节点高度
if (p != null) {
p.height = Math.max(height(p.left), height(p.right)) + 1;
}
return p;
}
平衡二叉树的插入操作是在搜索二叉树的基础上，判断插入后的新节点的平衡性，如果不平衡，则判断是四种情况的哪一种，做相应操作，最后更新旋转后的新根节点的高度。
平衡二叉树的删除操作
平衡二叉树的删除相对搜索二叉树的删除更为复杂(搜索二叉树的删除操作也不简单，哭了。。),这里平衡二叉树的删除有一个特征:待删除节点左子树高度大于右子树高度，则找在左子树中寻找前驱节点替换当前节点后，它仍为平衡二叉树，反之则用右子树的后继节点替换它。和插入操作类似，做递归删除后需要判断删除后新节点的平衡性，如果不平衡则判断是四种情况的哪一种，做相应操作，最后更新新子树的高度即可。删除代码不做详细解释了，比较复杂，代码注释应该比较清晰了。下面的代码在搜索二叉树的基础上，借鉴了这篇博客中删除节点的思路https://www.cnblogs.com/Camilo/p/3917041.html,目前亲测有效，如有误人子弟，欢迎打脸，还望见谅！
删除节点代码:
/**
* 非平衡二叉树的删除步骤:
* ① 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
* ②如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的
* 父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
* ③如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，
* 并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。
* 采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，
* 又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
* 平衡二叉树的删除方法在之前的基础上需要考虑下面两点
* ① 当前待删除节点左子树高度大于右子树高度，则找在左子树中寻找前驱节点替换当前节点
* ② 删除操作执行后，别忘了重新更新根节点高度，然后根据左右子树的高度判断平衡性，根据前面分析的四种情况进行旋转
*
* @param data
* @param rootNode 当前操作节点
* @return
*/
public AVLNode<T> removeAvlNode(T data, AVLNode<T> rootNode) {
if (data == null) {
return rootNode;
}
if (rootNode == null) {
return rootNode;//没有找到
}
int compareResult = data.compareTo(rootNode.data);
if (compareResult < 0) {//左子树递归删除
rootNode.left = removeAvlNode(data, rootNode.left);
// 高度计算，判断是否失衡
//删除后，修改树的高度,左子树删除，
rootNode.height = Math.max(height(rootNode.left), height(rootNode.right)) + 1;
//左子树删除后，判断是否失衡
if (height(rootNode.right) - height(rootNode.left) == 2) {
//调整右子树
if (height(rootNode.right.left) > height(rootNode.right.right)) {
//右子树的左子树导致失衡，则进行右左双旋转
rootNode = doubleRotateWithRight(rootNode);
} else {
//右子树的右子树导致失衡，则进行右右单旋转
rootNode = singleRotateRight(rootNode);
}
}
} else if (compareResult > 0) {//右子树递归删除
rootNode.right = removeAvlNode(data, rootNode.right);
//高度计算，判断是否失衡
//删除后，修改树的高度
rootNode.height = Math.max(height(rootNode.left), height(rootNode.right)) + 1;
//右子树删除后，判断rootNode是否失衡
if (height(rootNode.left) - height(rootNode.right) == 2) {
//调整右子树
if (height(rootNode.left.left) > height(rootNode.left.right)) {
//左子树的左子树导致失衡，则进行左左单旋转
rootNode = singleRotateLeft(rootNode);
} else {
//左子树的右子树导致失衡，则进行左右单旋转
rootNode = doubleRotateWithLeft(rootNode);
}
}
} else if (rootNode.left != null && rootNode.right != null) {//俩孩子节点
//当待删除结点左子树的高度大于右子树的高度时，用*T的前驱结点pre代替*T，
//再将结点pre从树中删除。这样可以保证删除结点后的树仍为二叉平衡树。
if (height(rootNode.left) > height(rootNode.right)) {//找前驱节点替换
rootNode.data = findMax(rootNode.left).data;
rootNode.left = removeAvlNode(rootNode.data, rootNode.left);
} else {//后继节点替换
//右子树的最小值替换当前节点值
rootNode.data = findMin(rootNode.right).data;
//移除用于替换的点
rootNode.right = removeAvlNode(rootNode.data, rootNode.right);
}
} else {//只有一个孩子节点或者叶子节点的情况,次处返回的节点返回给上次递归，用于父节点链接该节点
rootNode = (rootNode.left != null) ? rootNode.left : rootNode.right;
}
return rootNode;
}
/**
* 查找最小值结点
*
* @param p
* @return
*/
private AVLNode<T> findMin(AVLNode<T> p) {
if (p == null)//结束条件
return null;
else if (p.left == null)//如果没有左结点,那么t就是最小的
return p;
return findMin(p.left);
}
/**
* 查找最大值结点
*
* @param p
* @return
*/
private AVLNode<T> findMax(AVLNode<T> p) {
if (p == null)
return null;
else if (p.right == null)//如果没有右结点,那么t就是最大的
return p;
return findMax(p.right);
}
/**
* @param p
* @return
*/
public int height(AVLNode<T> p) {
return p == null ? -1 : p.height;
}
完整代码
除了插入元素和删除，其他方法与搜索二叉树基本一样，不再说明。
package tree.avltree;
import queue.Queue;
import tree.BinaryNode;
import tree.Tree;
/**
* Created by chenming on 2018/6/5
*/
public class AVLTree<T extends Comparable> implements Tree<T> {
public AVLNode<T> mRoot;//为了测试用，mRoot先暴露出去
/**
* 向左子树的左节点插入元素,执行右旋操作
*
* @param x
* @return
*/
private AVLNode<T> singleRotateLeft(AVLNode<T> x) {
AVLNode<T> w = x.left;
x.left = w.right;
w.right = x;
//重新计算x w的高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
w.height = Math.max(height(w.left), x.height) + 1;
return w;
}
/**
* 向右子树的右节点插入元素,执行左旋操作
*
* @param w
* @return
*/
private AVLNode<T> singleRotateRight(AVLNode<T> w) {
AVLNode<T> x = w.right;
w.right = x.left;
x.left = w;
//重新计算x/w的高度
w.height = Math.max(height(w.left), height(w.right)) + 1;
x.height = Math.max(height(x.left), w.height) + 1;
//返回新的根结点
return x;
}
/**
* 往左子树的右孩子插入节点,左右双旋
*/
private AVLNode<T> doubleRotateWithLeft(AVLNode<T> x) {
//w先进行右右单旋转
x.left = singleRotateRight(x.left);
return singleRotateLeft(x);
}
/**
* 右左旋转(RL旋转)
*
* @param x
* @return
*/
private AVLNode<T> doubleRotateWithRight(AVLNode<T> x) {
//先进行LL旋转
x.right = singleRotateLeft(x.right);
//再进行RR旋转
return singleRotateRight(x);
}
@Override
public void insert(T data) {
mRoot = insert(data, mRoot);
}
/**
* 平衡二叉树的插入操作
*
* @param data
* @param p
* @return
*/
private AVLNode<T> insert(T data, AVLNode<T> p) {
if (p == null) {
p = new AVLNode<>(data);
} else if (data.compareTo(p.data) < 0) {//向左子树寻找插入位置{
p.left = insert(data, p.left);
if (height(p.left) - height(p.right) == 2) {//子树高度差为2,需要平衡
if (data.compareTo(p.left.data) < 0) {//往左边插入LL单旋转
p = singleRotateLeft(p);
} else {
p = doubleRotateWithLeft(p);//往左边插入LR双旋转
}
}
} else if (data.compareTo(p.data) > 0) {//向右子树寻找插入位置
p.right = insert(data, p.right);
if (height(p.right) - height(p.left) == 2) {
if (data.compareTo(p.right.data) < 0) {
//进行RL双旋转
p = doubleRotateWithRight(p);
} else {
//进行RR单旋
p = singleRotateRight(p);
}
}
}
//重新计算节点高度
if (p != null) {
p.height = Math.max(height(p.left), height(p.right)) + 1;
}
return p;
}
/**
* 删除操作
*
* @param data
*/
@Override
public void remove(T data) {
// mRoot = remove(mRoot, data);
mRoot = removeAvlNode(data, mRoot);
}
/**
* 非平衡二叉树的删除步骤:
* ① 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
* ②如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的
* 父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
* ③如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，
* 并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。
* 采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，
* 又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
* 平衡二叉树的删除方法在之前的基础上需要考虑下面两点
* ① 当前待删除节点左子树高度大于右子树高度，则找在左子树中寻找前驱节点替换当前节点
* ② 删除操作执行后，别忘了重新更新根节点高度，然后根据左右子树的高度判断平衡性，根据前面分析的四种情况进行旋转
*
* @param data
* @param rootNode 当前操作节点
* @return
*/
public AVLNode<T> removeAvlNode(T data, AVLNode<T> rootNode) {
if (data == null) {
return rootNode;
}
if (rootNode == null) {
return rootNode;//没有找到
}
int compareResult = data.compareTo(rootNode.data);
if (compareResult < 0) {//左子树递归删除
rootNode.left = removeAvlNode(data, rootNode.left);
// 高度计算，判断是否失衡
//删除后，修改树的高度,左子树删除，
rootNode.height = Math.max(height(rootNode.left), height(rootNode.right)) + 1;
//左子树删除后，判断是否失衡
if (height(rootNode.right) - height(rootNode.left) == 2) {
//调整右子树
if (height(rootNode.right.left) > height(rootNode.right.right)) {
//右子树的左子树导致失衡，则进行右左双旋转
rootNode = doubleRotateWithRight(rootNode);
} else {
//右子树的右子树导致失衡，则进行右右单旋转
rootNode = singleRotateRight(rootNode);
}
}
} else if (compareResult > 0) {//右子树递归删除
rootNode.right = removeAvlNode(data, rootNode.right);
//高度计算，判断是否失衡
//删除后，修改树的高度
rootNode.height = Math.max(height(rootNode.left), height(rootNode.right)) + 1;
//右子树删除后，判断rootNode是否失衡
if (height(rootNode.left) - height(rootNode.right) == 2) {
//调整右子树
if (height(rootNode.left.left) > height(rootNode.left.right)) {
//左子树的左子树导致失衡，则进行左左单旋转
rootNode = singleRotateLeft(rootNode);
} else {
//左子树的右子树导致失衡，则进行左右单旋转
rootNode = doubleRotateWithLeft(rootNode);
}
}
} else if (rootNode.left != null && rootNode.right != null) {//俩孩子节点
//当待删除结点左子树的高度大于右子树的高度时，用*T的前驱结点pre代替*T，
//再将结点pre从树中删除。这样可以保证删除结点后的树仍为二叉平衡树。
if (height(rootNode.left) > height(rootNode.right)) {//找前驱节点替换
rootNode.data = findMax(rootNode.left).data;
rootNode.left = removeAvlNode(rootNode.data, rootNode.left);
} else {//后继节点替换
//右子树的最小值替换当前节点值
rootNode.data = findMin(rootNode.right).data;
//移除用于替换的点
rootNode.right = removeAvlNode(rootNode.data, rootNode.right);
}
} else {//只有一个孩子节点或者叶子节点的情况,次处返回的节点返回给上次递归，用于父节点链接该节点
rootNode = (rootNode.left != null) ? rootNode.left : rootNode.right;
}
return rootNode;
}
/**
* 查找最小值结点
*
* @param p
* @return
*/
private AVLNode<T> findMin(AVLNode<T> p) {
if (p == null)//结束条件
return null;
else if (p.left == null)//如果没有左结点,那么t就是最小的
return p;
return findMin(p.left);
}
/**
* 查找最大值结点
*
* @param p
* @return
*/
private AVLNode<T> findMax(AVLNode<T> p) {
if (p == null)
return null;
else if (p.right == null)//如果没有右结点,那么t就是最大的
return p;
return findMax(p.right);
}
/**
* @param p
* @return
*/
public int height(AVLNode<T> p) {
return p == null ? -1 : p.height;
}
@Override
public boolean isEmpty() {
return mRoot == null;
}
@Override
public int size() {
return size(mRoot);
}
/**
* 递归计算左右子树的和,再加上当前节点
*
* @param currentNode
* @return
*/
public int size(AVLNode<T> currentNode) {
if (currentNode == null) {
return 0;
}
int leftSize = size(currentNode.left);
int rightSize = size(currentNode.right);
return leftSize + rightSize + 1;
}
@Override
public int height() {
return mRoot == null ? 0 : mRoot.height;
}
@Override
public String preOrder() {
return preOrder(mRoot);
}
/**
* 前序遍历,先遍历节点,再遍历左子树，最后遍历右子树
*
* @return
*/
public String preOrder(AVLNode<T> root) {
StringBuilder sb = new StringBuilder();
if (root != null) {
sb.append(root.data + ", ");
sb.append(preOrder(root.left));
sb.append(preOrder(root.right));
}
return sb.toString();
}
@Override
public String inOrder() {
return inOrder(mRoot);
}
/**
* 递归中序遍历
*
* @param root
* @return
*/
public String inOrder(AVLNode<T> root) {
StringBuilder sb = new StringBuilder();
if (root != null) {
sb.append(inOrder(root.left));
sb.append(root.data + ", ");
sb.append(inOrder(root.right));
}
return sb.toString();
}
@Override
public String postOrder() {
return postOrder(mRoot);
}
/**
* 递归中序遍历
*
* @param root
* @return
*/
public String postOrder(AVLNode<T> root) {
StringBuilder sb = new StringBuilder();
if (root != null) {
sb.append(postOrder(root.left));
sb.append(postOrder(root.right));
sb.append(root.data + ", ");
}
return sb.toString();
}
/**
* 层遍历:关键在于队列保存节点的两个孩子节点,每次迭代做如下操作:
* 1.将非空子节点入队
* 2.输出队列头节点
*
* @return
*/
@Override
public String levelOrder() {
return levelOrder(mRoot);
}
/**
* 层遍历
*
* @param node
* @return
*/
public String levelOrder(AVLNode<T> node) {
StringBuilder sb = new StringBuilder();
Queue<AVLNode<T>> queue = new Queue<>();
while (node != null) {
sb.append(node.data + ", ");
AVLNode<T> leftNode = node.left;
AVLNode<T> rightNode = node.right;
//同层的子节点入队
if (leftNode != null) {
queue.enquene(leftNode);
}
if (rightNode != null) {
queue.enquene(rightNode);
}
node = queue.dequeue();//遍历下个节点
}
return sb.toString();
}
@Override
public T findMin() {
return findMin(mRoot).data;
}
@Override
public T findMax() {
return findMax(mRoot).data;
}
@Override
public BinaryNode findNode(T data) {
//@see SearchTree中的实现
//return findNode(T data, mRoot)
return null;
}
/**
* 递归查找元素
*
* @param data
* @param currentNode
* @return
*/
public AVLNode findNode(T data, AVLNode<T> currentNode) {
if (currentNode == null) {
return null;
}
int compareResult = data.compareTo(currentNode.data);
if (compareResult == 0) {
return currentNode;
}
if (compareResult > 0) {
currentNode = findNode(data, currentNode.right);//移动node指针
} else if (compareResult < 0) {
currentNode = findNode(data, currentNode.left);
}
return currentNode;
}
@Override
public boolean contains(T data) {
return contains(data, mRoot);
}
/**
* 递归实现包含
*
* @param data
* @param tree
* @return
*/
public boolean contains(T data, AVLNode<T> tree) {
if (data == null) {
return false;
}
if (tree == null) {
return false;
}
int compareResult = data.compareTo(tree.data);
if (compareResult == 0) {
return true;
} else if (compareResult > 0) {
return contains(data, tree.right);
} else if (compareResult < 0) {
return contains(data, tree.left);
}
return false;
}
@Override
public void clear() {
mRoot = null;
}
}
最后献上测试代码:
@Test
public void testAVLTree() {
Integer[] avlArr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
AVLTree<Integer> avlTree = new AVLTree<>();
for (int i = 0; i < avlArr.length; i++) {
avlTree.insert(avlArr[i]);
}
System.out.println("=====平衡二叉树输出=====");
dumpAvlTree(avlTree.mRoot);//树结构打印测试
avlTree.remove(6);
System.out.println("=====平衡二叉树深度=====");
System.out.println(avlTree.height());
System.out.println("=====平衡二叉树大小=====");
System.out.println(avlTree.size());
System.out.println("=====平衡二叉树删除元素后输出=====");
dumpAvlTree(avlTree.mRoot);
System.out.println("=====平衡二叉树深度=====");
System.out.println(avlTree.height());
}
/**
* 打印AVL树信息
*
* @param root
*/
public void dumpAvlTree(AVLNode<Integer> root) {
if (root == null) {
return;
}
StringBuilder sb = new StringBuilder();
sb.append(root.data);
sb.append("(");
if (root.left != null && root.right != null) {
sb.append(root.left.data + "-" + root.left.height);
sb.append(" , ");
sb.append(root.right.data + "-" + root.right.height);
} else if (root.left != null) {
sb.append(root.left.data + "-" + root.left.height);
sb.append(" , ");
} else if (root.right != null) {
sb.append(" , ");
sb.append(root.right.data + "-" + root.right.height);
}
sb.append(")");
System.out.println(sb.toString());
dumpAvlTree(root.left);
dumpAvlTree(root.right);
}
测试结果如下：
10101.png
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
