SNode newNode = new SNode(value);// 把新的节点左子树设置成当前节点的左子树 newNode.left = left;// 把新节点的右子树设置成当前节点的右子节点的左子树 newNode.right = right.left;// 把当前节点的值换为右子节点的值 value = right.value;// 把当前节点的右子树换成右子树的右子树 right = right.right;// 把当前节点的左子树设置成新节点 left = newNode;

}

5、应用案例-单旋转(右旋转)

1. 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}

2. 思路分析(示意图)

《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》开源

3)代码实现

// 右旋转 private v Java 开源项目【ali1024.coding.net/public/P7/Java/git】 oid rightRotate() {SNode newNode = new SNode(value);newNode.right = right;newNode.left = left.right;value = left.value;left = left.left;right = newNode;

}

6、应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转

不能完成平衡二叉树的转换。比如数列

int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.

int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树

1. 问题分析

2. 解决思路分析

1. 当符号右旋转的条件时

2. 如果它的左子树的右子树高度大于它的左子树的高度

3. 先对当前这个结点的左节点进行左旋转

4. 在对当前结点进行右旋转的操作即可

3. 代码实现[AVL 树的汇总代码(完整代码)]

package com.lin.avltree_0316;

import javax.security.auth.kerberos.KerberosKey;

public class AVLTreeDemo {

public static void main(String[] args) {// int[] arr = {4, 3, 6, 5, 7, 8};// int[] arr = {10, 12, 8, 9, 7, 6};int[] arr = {10, 11, 7, 6, 8, 9};

AVLTree avlTree = new AVLTree();for (int i = 0; i < arr.length; i++) {avlTree.add(new SNode(arr[i]));}

avlTree.infixOrder();

System.out.println("旋转之后：");System.out.println("树的高度：" + avlTree.getRoot().height());System.out.println("左子树的高度：" + avlTree.getRoot().leftHeight());System.out.println("右子树的高度：" + avlTree.getRoot().rightHeight());System.out.println("root = " + avlTree.getRoot());System.out.println("root.left = " + avlTree.getRoot().left);System.out.println("root.left.left = " + avlTree.getRoot().left.left);}}

class AVLTree{private SNode root;// 查找要删除的节点 public SNode getRoot() {return root;}public SNode searchDelNode(int value) {if(root == null) {return null;} else {return root.searchDelNode(value);}}// 查找要删除节点的父节点 public SNode searchParent(int value) {if(root == null) {return null;} else {return root.searchParent(value);}}/**

• @param node 传入的节点（当作二叉排序树的根节点）

• @return 返回的以 node 为根节点的二叉排序树的最小节点的值*/public int delRightTreeMin(SNode node) {SNode target = node;// 循环地查找左节点，就会找到最小值 while(target.left != null) {target = target.left;}delNode(target.value);// !!!!return target.value;// !!!!!}

// 删除节点 public void delNode(int value) {if(root == null) {return;} else {// 找删除节点 SNode targetNode = searchDelNode(value);// 没有找到 if(targetNode == null) {return;}// 如果发现当前这棵二叉树只有一个节点 if(root.left == null && root.right == null) {root = null;return;}// 去找到 targetNode 的父节点 SNode parent = searchParent(value);// 如果删除的节点是叶子节点 if(targetNode.left == null && targetNode.right == null) {// 判断 targetNode 是父节点的左子节点还是右子节点 if(parent.left != null && parent.left.value == value) {parent.left = null;} else if(parent.right != null && parent.right.value == value) {parent.right = null;}} else if(targetNode.left != null && targetNode.right != null) { // 有左右子节点 int delRightTreeMin = delRightTreeMin(targetNode.right);targetNode.value = delRightTreeMin;} else {// 只有一个子节点// 要删除的节点只有左节点 if(targetNode.left != null) {if(parent != null) {// 如果 targetNode 是 parent 的左子节点 if(parent.left.value == value) {parent.left = targetNode.left;} else {parent.right = targetNode.left;}} else {root = targetNode.left;}} else {// 要删除的节点有右子节点 if(parent != null) {if(parent.left.value == value) {parent.left = targetNode.right;} else {parent.right = targetNode.right;}} else {root = targetNode.right;}}}

}}// 中序遍历 public void infixOrder() {if(root == null) {System.out.println("空树！");} else {root.infixOrder();}}// 添加 public void add(SNode node) {if(root == null) {root = node;} else {root.add(node);}}

总结

我们总是喜欢瞻仰大厂的大神们，但实际上大神也不过凡人，与菜鸟程序员相比，也就多花了几分心思，如果你再不努力，差距也只会越来越大。

面试题多多少少对于你接下来所要做的事肯定有点帮助，但我更希望你能透过面试题去总结自己的不足，以提高自己核心技术竞争力。每一次面试经历都是对你技术的扫盲，面试后的复盘总结效果是极好的！