PS：本文为转载文章，原文可读性会更好，文末有原文链接。双旋转1、平衡二叉树1、1二叉树的右旋转第一篇平衡二叉树（Java实现）的时候，我们了解的比较多的是二叉树的左旋转，好了，这里先学习二叉树的右旋转；我们对一棵二叉树进行右旋，目的是让它成为一棵平衡二叉树，对吧？右旋的树需要满足如下条件：左子树的高度大于右子树的高度，并且这个值至少要为2。好了，现在来玩二叉树的右旋，假设我们得到一个序列数组={11,12,8,9,7,5}；根据我们在这篇文章中学到的关于二叉排序树（Java实现）的知识，如果将数组构造成一棵二叉排序树，那么就会得到如图1所示的二叉树；如图1所示，左子树的高度为3，右子树的高度为1，显然不是一棵要平衡的二叉树，左子树的高度大于右子树，这个值为2，所以我们需要将它向右旋转。下面我们分析一下图1中二叉树右旋的思路；(1)新建一个节点，这个新节点的值等于根节点的值，如图2所示；图（2）我们以根节点为当前节点，将新节点的左子树指向当前节点左子树的右子树，将新节点的右子树指向当前节点的右子树节点，则得到图3所示的结构图；图（3）将当前节点的值修改为当前节点左子树的值，得到如图4所示的结构图；图（4）将当前节点的左子树指向左子树的左子树（即红色数字8的左子树指向7节点），将当前节点的右子树指向新节点（即红色数字8的右子树指向红色数字11），则得到图5所示的结构图；图（5）此时红色数字8的节点作为新的根节点，而白色数字8的节点没有节点指向它，所以我们省略，我们简化结构图如图5、得到如图6所示的二叉树；图（6）中第一次右旋完成后，我们判断这棵二叉树是否是平衡二叉树，如果不是，则进行下一轮右旋；显然，图6中二叉树的左子树的高度和右子树的高度都是2，所以是一棵平衡二叉树。对比图1和图6，我们发现经过一轮右旋后，旧根节点的左子树变成了新根节点，新根节点的右子树变成了旧根节点。旧根节点的根节点，旧根节点左子树的右子树成为新根节点右子树的左子树；对于新根节点，将旧根节点作为新根节点的右子节点，将旧根节点的左子节点的右子节点作为新根节点右子节点的左子节点新的根节点。ok，我们现在为序列数组={11,12,8,9,7,5}构建二叉排序树，并进行右旋，现在用代码实现；(1)写一个节点类Node：packagecom.xiaoer.demo；公共类节点{私有节点leftNode;私有节点rightNode；privateintvalue;//返回左子树的高度publicintleftHeight(){intheight=leftNode==null?0:左节点。height();returnheight;}//返回右子树的高度publicintrightHeight(){intheight=rightNode==null?0:rightNode.height();returnheight;}//返回当前节点的高度publicintheight(){intheight=Math.max(leftNode==null?0:leftNode.height(),rightNode==null?0:rightNode.height())+1;returnheight;}publicNode(intvalue){super();this.value=value;}/**添加节点方法@paramisRotate表示是否旋转*/publicvoidaddNode(Nodenode,booleanisRotate){if(node==null){System.out.println("节点为空，请勿添加");return;}//判断传入节点的值是否小于当前节点的值if(node.value
