二叉树的单旋分为： 左单旋 ， 右单旋
判断对二叉树进行平衡操作要按照后序遍历的顺序
让不平航二叉树变为平衡二叉树

单旋的一些名词

image.png
以上图进行左单旋为例（可以参考下面左单旋）
旋转节点：不平衡节点为旋转节点（上图节点2）
新根：旋转之后称为根节点的节点（上图节点5）
变化分支：父级节点发生变化的那个分支（上图节点3）
不变分支：父级节点不变的那个分支（上图节点6）

左单旋

如图这是某一节点不平衡
如果左边浅，右边深，进行左单旋
左单旋就是绕着旋转节点逆时针旋转
image.png
左单旋时：
旋转节点：当前不平衡节点
新根：右子树的根节点
变化分支：右子树的左子树
不变化分支：右子树的右子树
进行左单旋后的示意图

重点

进行左单旋：
1:找到新根
2：找到变化分支
3：当前旋转节点的右孩子为变化分支
4：新根的左孩子为旋转节点
5：返回一个新的根节点

重点

image.png
左单旋动画示意图
两个结合这看 图二由于软件限制没办法将节点2作为旋转节点
图1 图2
左单旋示意图.gif左单旋示意图2.gif

右单旋

如图这是某一节点不平衡
如果左边深，右边浅，进行右单旋
右单旋是以旋转节点进行顺时针旋转
image.png
右单旋时：
旋转节点：当前不平衡节点
新根：左子树的根节点
变化分支：旋转节点的左子树的右子树
不变分时：旋转节点的左子树的左子树
右单旋后示意图
进行右单旋
1:找到新根
2：找到变化分支
3：当前旋转节点的左孩子为变化分支
4：新根的右孩子为旋转节点
5：返回一个新的根节点
image.png
动态示意图
右单旋示意图.gif

代码实现左右单旋

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.left = null;
  5.         this.right = null;
  6.     }
  7. }
  9. let node2 = new Node('2')
  10. let node5 = new Node('5')
  11. let node3 = new Node('3')
  12. let node6 = new Node('6')
  13. // 左单旋
  14. // node2.right = node5;
  15. // node5.right = node6;
  16. // node5.left = node3;
  18. // 右单旋
  19. node6.left = node3;
  20. node3.left = node2;
  21. node3.right = node5;
  23. /**
  24.  * 判断是否为二叉平衡树
  25.  * 平衡二叉的满足条件
  26.  * 根节点的左子树与右子树的高度差不能超过1
  27.  * 这棵二叉树的每个子树的符合第一条
  28.  * @param {*} root 根节点
  29.  * @returns Boolean
  30.  */
  31. function isBalanceTree(root) {
  32.     if (!root) return true;
  33.     // 获取左右子树的深度
  34.     let left = getDeep(root.left);
  35.     let right = getDeep(root.right);
  36.     // 当左子树与右子树的深度差大于1说明不是二叉平衡树
  37.     if (Math.abs(left - right) > 1) return false;
  38.     // 遍历这个二叉树的每一个子树
  39.     else return isBalanceTree(root.left) && isBalanceTree(root.right);
  42. }
  43. /**
  44.  * 获取二叉树的深度
  45.  * @param {*} root 节点
  46.  * @returns Number 返回左右子树中最深的层数
  47.  */
  48. function getDeep(root) {
  49.     if (!root) return 0;
  50.     let left = getDeep(root.left);
  51.     let right = getDeep(root.right);
  52.     return Math.max(left, right) + 1;
  54. }
  55. /**
  56.  * 利用单旋将二叉不平衡树变为二叉平衡树
  57.  * @param {*} root 跟节点
  58.  * @returns 返回平衡之后的根节点
  59.  */
  60. function change(root) {
  61.     if (isBalanceTree(root)) return root; // 返回平衡之后的根节点
  62.     // 走到这说明不是二叉平衡树
  63.       // 判断平不平衡需要从下往上判断
  64.     // 判断对二叉树进行平衡操作要按照后序遍历的顺序
  65.     // 后序遍历 先左子树 后右子树 最后自己
  66.     // 为何进行后序遍历，当根节点不是二叉平衡树，可能对子树进行单旋操作就成为二叉平衡树
  67.     if (root.left != null) root.left = change(root.left); // change函数会返回平衡之后的跟节点，故需要接收返回的的根节点
  68.     if (root.right != null) root.right = change(root.right);// change函数会返回平衡之后的跟节点，故需要接收返回的的根节点
  69.     // 获取深度
  70.     let leftTree = getDeep(root.left);
  71.     let rightTree = getDeep(root.right);
  72.     // 判断那里不符合二叉平衡树的要求
  73.     if (Math.abs(leftTree - rightTree) < 2) return root;
  74.     if (leftTree < rightTree) { //左浅 右深 左单旋
  75.         return leftRotate(root)
  76.     } else if (leftTree > rightTree) { //左深 右浅 右单旋
  77.         return rightRotate(root)
  78.     }
  79. }
  80. /**
  81.  * 左单旋
  82.  * 旋转节点：不平衡的节点为旋转节点
  83.  * 新根：旋转节点的右子树的根节点
  84.  * @param {*} root 旋转节点
  85.  * @returns 新的根节点
  86.  */
  87. function leftRotate(root) {
  88.     // 找到新根
  89.     let newNode = root.right;
  90.     // 找到变化分支
  91.     let changeNode = newNode.left;
  92.     // 当前旋转节点的右孩子为变化分支
  93.     root.right = changeNode;
  94.     // 新根的左孩子为旋转节点
  95.     newNode.left = root;
  96.     // 返回新的根节点
  97.     return newNode;
  99. }
  100. /**
  101.  * 右单旋
  102.  * 旋转节点：不平衡的节点为旋转节点
  103.  * 新根：旋转节点的左子树的根节点
  104.  * @param {*} root 旋转节点
  105.  * @returns 新的根节点
  106.  */
  107. function rightRotate(root) {
  108.     // 找到新根
  109.     let newNode = root.left;
  110.     // 找到变化分支
  111.     let changeNode = newNode.right;
  112.     // 当前旋转节点的左孩子为变化分支
  113.     root.left = changeNode
  114.     // 新根的右孩子为旋转节点
  115.     newNode.right = root;
  116.     // 返回新的根节点
  117.     return newNode;
  119. }
  120. // 测试左单旋
  121. // let root = change(node2);
  122. // 测试右单旋
  123. let root = change(node6);
  124. console.log(root)

为何判断对二叉树进行平衡操作要按照后序遍历的顺序

如图
image.png
节点5 不符合二叉平衡树的条件
节点6 不符合二叉平衡树的条件
当我们对节点6进行左单旋
image.png
你会发现现在它符合二叉平衡树啦

重点

判断平不平衡需要从下往上判断
判断对二叉树进行平衡操作要按照后序遍历的顺序

重点