本專欄目錄
藍橋杯算法競賽大綱
數論相關(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;
}