本专栏目录
蓝桥杯算法竞赛大纲
数论相关（Java）
枚举相关（Java）
对象排序（Java）
字符串相关（Java）
排序相关算法（Java）
记忆化搜索（Java）
树论相关（Java）
图论相关（Java）
堆（Java）
贪心（Java）
文章目录
- 二叉搜索树
- 二叉搜索树的结构AC1
- 二叉搜索树的结构AC2
- 前中后层序遍历
- 是否完全二叉搜索树
- 完全二叉树的层序遍历
- 玩转二叉树
- 线段树
- 线段树LazyTag
- AVLTree
- ST表
- 公共祖先问题
- 构建BST的两种方式和构建AVL的一种方式
二叉搜索树
package 树论;
import java.util.Scanner;
public class _二叉搜索树 {
static int n;
static int[] arr;
static int c1=0,c2=0;
static boolean flag1=false,flag2=false;
public static void main(String[] args) {
// 给定一个整数键值序列，现请你编写程序，
// 判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n];
Node root = null;
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
arr[i] = x;
root = insert(root, x);
}
preOrder(root);
if (!flag1){
System.out.println("YES");
postOrder(root);
return;
}
preMirrOrder(root);
if (!flag2){
System.out.println("YES");
postMirrOrder(root);
return;
}
System.out.println("NO");
}
// 后序镜像遍历
static boolean f2 = false;
public static void postMirrOrder(Node root) {
if (root.r!=null) postMirrOrder(root.r);
if (root.l!=null) postMirrOrder(root.l);
if (!f2){
System.out.print(root.data);
f2 = true;
}else {
System.out.print(" " + root.data);
}
}
// 前序镜像遍历 + 验证
public static void preMirrOrder(Node root) {
if (flag2 || arr[c2++]!=root.data){
flag2 = true;
return;
}
if (root.r!=null) preMirrOrder(root.r);
if (root.l!=null) preMirrOrder(root.l);
}
// 后序遍历
static boolean f1 = false;
public static void postOrder(Node root) {
if (root.l!=null) postOrder(root.l);
if (root.r!=null) postOrder(root.r);
if (!f1){
System.out.print(root.data);
f1 = true;
}else {
System.out.print(" " + root.data);
}
}
// 前序遍历 + 验证
public static void preOrder(Node root) {
if (flag1 || arr[c1++]!=root.data){
flag1 = true;
return;
}
if (root.l!=null){
preOrder(root.l);
}
if (root.r!=null){
preOrder(root.r);
}
}
// 构建二叉搜索树(BST)
public static Node insert(Node root, int x) {
if (root == null){
root = new Node();
root.data = x;
return root;
}
if (x < root.data){
root.l = insert(root.l, x);
}else {
root.r = insert(root.r, x);
}
return root;
}
static class Node{
Node l,r;
int data;
}
} 二叉搜索树的结构AC1
package 树论;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class _二叉搜索树的结构AC1 {
static int n,m;
static Map<Integer, Integer> layers = new HashMap<>(); // 层数
static Map<Integer, Integer> par = new HashMap<>(); // 父节点
static Map<Integer, Integer> lor = new HashMap<>(); // 左0还是右1子树
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Node root = new Node();
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
insert(root, x, 0);
}
m = scan.nextInt();
scan.nextLine();
for (int i = 0; i < m; i++) {
String line = scan.nextLine();
String[] strArr = line.split(" ");
if (line.contains("root")){
int x = Integer.parseInt(strArr[0]);
if (isExit(x) && x == root.data){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("siblings")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[2]);
if (par.get(a)!=null&&par.get(b)!=null&&par.get(a)-par.get(b)==0){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("level")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[2]);
if (isExit(a)&&isExit(b)&&layers.get(a)-layers.get(b)==0){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("parent")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[5]);
if (isExit(a)&&par.get(b)!=null&&par.get(b)-a==0){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("left")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[6]);
if (par.get(a)!=null&&isExit(b)&&par.get(a)-b==0&&lor.get(a)==0){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("right")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[6]);
if (par.get(a)!=null&&isExit(b)&&par.get(a)-b==0&&lor.get(a)==1){
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
}
public static boolean isExit(int x){
if (layers.get(x)==null){
return false;
}
return true;
}
static boolean flag = false;
public static void insert(Node root, int x, int layer){
if (!flag){
flag = true;
root.data = x;
layers.put(root.data,1);
return;
}
if (x<root.data){
if (root.l==null){
root.l = new Node();
root.l.data = x;
par.put(x, root.data);
layers.put(x, layer);
lor.put(x, 0);
return;
}
insert(root.l, x, layer+1);
}else {
if (root.r==null){
root.r = new Node();
root.r.data = x;
par.put(x, root.data);
layers.put(x, layer);
lor.put(x, 1);
return;
}
insert(root.r, x, layer+1);
}
}
static class Node{
Node r,l;
int data=-1;
}
} 二叉搜索树的结构AC2
package 树论;
import java.util.Scanner;
public class _二叉搜索树的结构AC2 {
static int n,m;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Node root = new Node();
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
insert(root, x, 1);
}
m = scan.nextInt();
scan.nextLine();
for (int i = 0; i < m; i++) {
String line = scan.nextLine();
String[] strArr = line.split(" ");
if (line.contains("root")){
int x = Integer.parseInt(strArr[0]);
if (x == root.data){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("siblings")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[2]);
Node na = find(root,a);
Node nb = find(root,b);
if (na!=null&&nb!=null&&na.parent!=null&&nb.parent!=null&&nb.parent==na.parent){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("level")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[2]);
Node na = find(root,a);
Node nb = find(root,b);
if (na!=null&&nb!=null&&na.depth==nb.depth){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("parent")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[5]);
Node na = find(root,a);
Node nb = find(root,b);
if (na!=null&&nb!=null&&nb.parent==na){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("left")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[6]);
Node na = find(root,a);
Node nb = find(root,b);
if (na!=null&&nb!=null&&nb.l==na){
System.out.println("Yes");
}else {
System.out.println("No");
}
}else if (line.contains("right")){
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[6]);
Node na = find(root,a);
Node nb = find(root,b);
if (na!=null&&nb!=null&&nb.r==na){
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}
}
public static Node find(Node root, int x){
if (root==null) return null;
if (x == root.data) return root;
if (x < root.data){
return find(root.l,x);
}else {
return find(root.r, x);
}
}
static boolean flag = false;
public static void insert(Node root, int x, int layer){
if (!flag){
flag = true;
root.data = x;
root.depth = 0;
root.parent = null;
return;
}
if (x<root.data){
if (root.l==null){
root.l = new Node();
root.l.data = x;
root.l.parent = root;
root.l.depth = layer;
return;
}
insert(root.l, x, layer+1);
}else {
if (root.r==null){
root.r = new Node();
root.r.data = x;
root.r.parent = root;
root.r.depth = layer;
return;
}
insert(root.r, x, layer+1);
}
}
static class Node{
Node r,l,parent;
int data,depth;
}
} 前中后层序遍历
package 树论;
import java.util.Scanner;
public class _前中后层序遍历 {
static int n;
static int[] postArr;
static int[] midArr;
public static void main(String[] args) {
// 给定一棵二叉树的后序遍历和中序遍历,输出其层序遍历的序列
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
postArr = new int[n+1];
midArr = new int[n+1];
for (int i = 1; i <= n; i++) {
postArr[i] = scan.nextInt();
}
for (int i = 1; i <= n; i++) {
midArr[i] = scan.nextInt();
}
Node root = buildTree(1,n,1,n);
levelOrder(root);
}
// 树的层序遍历
private static void levelOrder(Node root) {
Node[] Q = new Node[n];
int front = -1;
int rear = -1;
Q[++rear] = root;
while (front!=rear){
Node node = Q[++front];
if (node==root) System.out.print(node.data);
else System.out.print(" " + node.data);
if (node.l != null) Q[++rear] = node.l;
if (node.r != null) Q[++rear] = node.r;
}
}
public static Node buildTree(int m1, int e1, int m2, int e2){
if (m1 > e1 || m2 > e2){
return null;
}
// 后序遍历的最后一个元素是根
int x = postArr[e1];
Node root = new Node();
root.data = x;
// 在中序遍历中查找root
for (int i = m2; i <= e2; i++) {
if (midArr[i]==x){
//左子树长度
int k = i - m2;
root.l = buildTree(m1,m1+k-1,m2,i-1);
root.r = buildTree(m1+k,e1-1,i+1,e2);
break;
}
}
return root;
}
static class Node{
Node r,l;
int data;
}
} 是否完全二叉搜索树
package 树论;
import java.util.Scanner;
public class _是否完全二叉搜索树 {
static int n;
static int max = 0;
public static void main(String[] args) {
// 将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），
// 你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Node root = null;
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
root = insert(root, x);
}
levelOrder(root);
System.out.println();
dfs(root, 1);
if (max == n) System.out.println("YES");
else System.out.println("NO");
}
public static void dfs(Node root, int v){
if (v>max) max = v;
if (root.l!=null) dfs(root.l, v*2);
if (root.r!=null) dfs(root.r, v*2+1);
}
public static void levelOrder(Node root) {
Node[] Q = new Node[n];
int front = -1;
int rear = -1;
Q[++rear] = root;
boolean flag = true;
while (front!=rear){
Node node = Q[++front];
if (flag){
System.out.print(node.data);
flag = false;
}else {
System.out.print(" " + node.data);
}
if (node.l!=null) Q[++rear] = node.l;
if (node.r!=null) Q[++rear] = node.r;
}
}
public static Node insert(Node root, int x) {
if (root == null){
root = new Node();
root.data = x;
return root;
}
if (x > root.data){
root.l = insert(root.l, x);
}else {
root.r = insert(root.r, x);
}
return root;
}
static class Node{
Node r,l;
int data;
}
} 完全二叉树的层序遍历
package 树论;
import java.util.Scanner;
public class _完全二叉树的层序遍历 {
static int n;
static int[] arr;
static int[] brr;
static int c = 1;
public static void main(String[] args) {
// 给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n+1];
brr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = scan.nextInt();
}
postOrder(1);
System.out.print(brr[1]);
for (int i = 2; i <= n; i++) {
System.out.print(" " + brr[i]);
}
}
public static void postOrder(int v) {
if (v>n){
return;
}
postOrder(v*2);
postOrder(v*2 + 1);
brr[v] = arr[c++];
}
} 玩转二叉树
package 树论;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class _玩转二叉树 {
static int[] midArr;
static int[] preArr;
static int n;
static boolean flag = false;
static class Node{
Node l;
Node r;
int data;
}
public static void main(String[] args) {
// 给定一棵二叉树的中序遍历和前序遍历，
// 请你先将树做个镜面反转，再输出反转后的层序遍历的序列。
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
midArr = new int[n+1];
preArr = new int[n+1];
for (int i = 1; i <= n; i++) {
midArr[i] = scan.nextInt();
}
for (int i = 1; i <= n; i++) {
preArr[i] = scan.nextInt();
}
Node root = fn(1,n,1,n);
levelOrder(root);
}
private static void levelOrder(Node root) {
List<Node> ls = new ArrayList<>();
ls.add(root);
while (!ls.isEmpty()){
Node node = ls.remove(0);
if (!flag){
flag = true;
System.out.print(node.data);
}else {
System.out.print(" " + node.data);
}
if (node.l!=null) ls.add(node.l);
if (node.r!=null) ls.add(node.r);
}
}
private static Node fn(int preS, int preE, int midS, int midE) {
if (preS>preE || midS>midE){
return null;
}
int x = preArr[preS];
Node root = new Node();
root.data = x;
for (int i = midS; i <= midE; i++) {
if (midArr[i]==x){
int k = i - midS; // 左子树长度
// 镜像构造
root.r = fn(preS+1,preS+k, midS, i-1);
root.l = fn(preS+k+1,preE, i+1, midE);
}
}
return root;
}
} 线段树
package 树论;
public class _线段树 {
static int[] arr = {1, 3, 5, 7, 9, 11};
static int[] tree = new int[1000005];
static int n = 6;
public static void main(String[] args) {
buildTree(0, 0, n-1);
for (int i = 0; i <= 14; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
updateTree(0, 0, n-1, 4, 6);
for (int i = 0; i <= 14; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
// 查找原数组中索引为[2, 5] 区间的和
int sum = queryTree(0, 0, n-1, 2, 5);
System.out.println(sum);
}
/**
* 区间查询合
* @param node tree中的下标
* @param start arr数组中的下标
* @param end
* @param L 带查询的区间是[L, R]
* @param R
* @return
*/
private static int queryTree(int node, int start, int end, int L, int R) {
if (end < L || start > R){ // 如果[L, R] 和 [start, end] 没有交集
return 0;
}else if (L<=start && R >= end){ // 如果 [L, R] 区间包含 [start, end]
return tree[node];
}else if (start==end){ // 如果查找单点则直接返回值
return tree[node];
}
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
int sum_left = queryTree(left_node, start, mid, L, R);
int sum_right = queryTree(right_node, mid+1, end, L, R);
return sum_left + sum_right;
}
// 单点更新 arr[idx] = val
public static void updateTree(int node, int start, int end, int idx, int val){
if (start==end){
// 当查找到单点时,更新
tree[node] = val;
arr[idx] = val;
return;
}
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = left_node + 1;
if (idx <= mid){ // 如果idx在arr的左边,则在tree的左子树查找更新
updateTree(left_node, start, mid, idx, val);
}else {
updateTree(right_node, mid+1, end, idx, val);
}
// 更新父节点
tree[node] = tree[left_node] + tree[right_node];
}
/**
*
* @param node tree中的下标
* @param start arr中的下标 表示区间 [start, end]
* @param end
*/
public static void buildTree(int node, int start, int end){
if (start==end){
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
// tree中子树下标
int left_node = 2 * node + 1;
int right_node = left_node + 1;
// 分别建左右子树
buildTree(left_node, start, mid);
buildTree(right_node, mid+1, end);
tree[node] = tree[left_node] + tree[right_node];
}
} 线段树LazyTag
package 树论;
import java.util.Scanner;
// http://poj.org/problem?id=3468
public class _线段树LazyTag {
static long[] tree;
static long[] tags;
static long[] nums;
static int n, m;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
nums = new long[n+1];
tree = new long[4*n+1];
tags = new long[4*n+1];
for (int i = 1; i <= n; i++) {
nums[i] = scan.nextInt();
}
buildTree(0, 1, n);
for (int i = 0; i < m; i++) {
String s = scan.next();
if (s.equals("Q")){
int L = scan.nextInt();
int R = scan.nextInt();
long sum = query(0, 1, n, L, R);
System.out.println(sum);
}else {
int L = scan.nextInt();
int R = scan.nextInt();
int val = scan.nextInt();
updateTree(0, 1, n, L, R, val);
}
}
}
public static void buildTree(int node, int start, int end){
if (start==end){
tree[node] = nums[start];
return;
}
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
buildTree(left_node, start, mid);
buildTree(right_node, mid+1, end);
pushUP(node);
}
public static long query(int node, int start, int end, int L, int R) {
if (L<=start && end <= R){
return tree[node];
}else if (L>end || R < start){
return 0;
}else if (start==end){
return tree[node];
}
// 下放后才能查询
if (tags[node]!=0){
pushDown(node, start, end);
}
int mid = (start + end) / 2;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
long sum_left = query(left_node, start, mid, L, R);
long sum_right = query(right_node, mid+1, end, L, R);
return sum_left + sum_right;
}
public static void updateTree(int node, int start, int end, int L, int R, int val) {
if (L <= start && end <= R){
// 如果[start,end] 在待查询的区间 [L, R] 内, 则进行LazyTag标记后返回
tree[node] += (end - start + 1) * val;
tags[node] += val;
return;
}
// 更新前如果当前节点有LazyTag标记,则先下放
if (tags[node]!=0){
pushDown(node, start, end);
}
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
// [L, R] 和 [start, mid] 有交集, 则去左边更新
if (L <= mid){
updateTree(left_node, start, mid, L, R, val);
}
// [L, R] 和 [mid + 1, end] 有交集, 则去右边更新
if (mid + 1 <=R){
updateTree(right_node, mid+1, end, L, R, val);
}
// 更新节点的值
pushUP(node);
}
// 根据父节点的LazyTag标记,更新子节点的值,并且给子节点打标记
public static void pushDown(int idx, int start, int end){
long val = tags[idx];
int mid = (start + end) / 2;
int left_node = idx * 2 + 1;
int right_node = idx * 2 + 2;
tree[left_node] += (mid - start + 1) * val;
tree[right_node] += (end - (mid + 1) + 1) * val;
tags[left_node] += val;
tags[right_node] += val;
tags[idx] = 0;
}
// 根据子节点的值更新父节点的值
public static void pushUP(int idx){
tree[idx] = tree[idx*2+1] + tree[idx*2+2];
}
} AVLTree
package 树论;
import java.util.Scanner;
public class _AVLTree {
static class Node{
int data;
Node left,right;
}
static int n;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Node root = null;
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
root = insert(root, x);
}
levelOrder(root);
}
public static void levelOrder(Node root){
Node[] Q = new Node[n];
int rear = -1;
int front = -1;
Q[++rear] = root;
while (rear!=front){
Node node = Q[++front];
System.out.print(node.data + " ");
if (node.left!=null) {
Q[++rear] = node.left;
}
if (node.right!=null) {
Q[++rear] = node.right;
}
}
}
public static Node rotateRightLeft(Node root){
root.right = rotateRight(root.right);
root = rotateLeft(root);
return root;
}
public static Node rotateLeftRight(Node root){
root.left = rotateLeft(root.left);
root = rotateRight(root);
return root;
}
public static Node rotateLeft(Node root){ // 左旋
Node right = root.right;
root.right = right.left;
right.left = root;
return right;
}
public static Node rotateRight(Node root){ // 右旋
Node left = root.left;
root.left = left.right;
left.right = root;
return left;
}
public static int getHeight(Node root){
if (root==null) return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// 构建AVL
public static Node insert(Node root, int x){
if (root == null){
root = new Node();
root.data = x;
return root;
}
if (x < root.data){
root.left = insert(root.left, x);
if (getHeight(root.left)-getHeight(root.right)>=2){
// 如果高度差是因为x插入了左子树的右子树造成的,则左右旋
if (x > root.left.data){
root = rotateLeftRight(root);
}else { // 否则只右旋
root = rotateRight(root);
}
}
}else {
root.right = insert(root.right, x);
if (getHeight(root.right)-getHeight(root.left)>=2){
// 如果高度差是因为x插入了右子树的左子树造成的,则右左旋
if (x<root.right.data){
root = rotateRightLeft(root);
}else { // 否则只左旋
root = rotateLeft(root);
}
}
}
return root;
}
} ST表
package 树论;
import java.util.Scanner;
public class _ST表 {
static int n,m;
static int[][] dp; // dp[i][j] 表示区间 [i, i+2^j-1], 即下标从i开始,长度为2^j的区间
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
dp = new int[n][(int)Math.log(n)+5];
// 预处理
for (int i = 0; i < n; i++) {
dp[i][0] = scan.nextInt();
}
for (int j = 1; j <= Math.log(n); j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
// 长度一半的两个相邻区间的最大/最小值
dp[i][j] = Math.min(dp[i][j-1], dp[i + (1 << (j - 1))][j-1]);
}
}
int l, r;
for (int i = 0; i < m; i++) {
l = scan.nextInt();
r = scan.nextInt();
if (i==m-1){
System.out.print(query(l-1, r-1));
}else {
System.out.print(query(l-1, r-1) + " ");
}
}
}
public static int query(int l, int r) {
// 待求的区间长度
int len = r - l + 1;
int j = (int)Math.log(len);
// max/min([l, l+2^j-1], [r-2^j+1, r])
return Math.min(dp[l][j], dp[r - (1 << j) + 1][j]);
}
} 公共祖先问题
static class Node{
Node r,l,parent;
int data,depth;
}
增加一个parent字段,然后查找到后反搜标记,最后看是否有重复标记的
并查集有可能也可以解决 构建BST的两种方式和构建AVL的一种方式
BST
(一) 一般用于公共父节点问题
static boolean flag = false;
public static void insert(Node root, int x, int layer){
if (!flag){
flag = true;
root.data = x;
root.depth = 0;
root.parent = null;
return;
}
if (x<root.data){
if (root.l==null){
root.l = new Node();
root.l.data = x;
root.l.parent = root;
root.l.depth = layer;
return;
}
insert(root.l, x, layer+1);
}else {
if (root.r==null){
root.r = new Node();
root.r.data = x;
root.r.parent = root;
root.r.depth = layer;
return;
}
insert(root.r, x, layer+1);
}
}
(二)
public static Node insert(Node root, int x) {
if (root == null){
root = new Node();
root.data = x;
return root;
}
if (x < root.data){
root.l = insert(root.l, x);
}else {
root.r = insert(root.r, x);
}
return root;
}
AVL
// 构建AVL
public static Node insert(Node root, int x){
if (root == null){
root = new Node();
root.data = x;
return root;
}
if (x < root.data){
root.left = insert(root.left, x);
if (getHeight(root.left)-getHeight(root.right)>=2){
// 如果高度差是因为x插入了左子树的右子树造成的,则左右旋
if (x > root.left.data){
root = rotateLeftRight(root);
}else { // 否则只右旋
root = rotateRight(root);
}
}
}else {
root.right = insert(root.right, x);
if (getHeight(root.right)-getHeight(root.left)>=2){
// 如果高度差是因为x插入了右子树的左子树造成的,则右左旋
if (x<root.right.data){
root = rotateRightLeft(root);
}else { // 否则只左旋
root = rotateLeft(root);
}
}
}
return root;
}