递归算法：自己调用自己
1.计算乘法1*2..... (n-1)*n的积
public static int getReult(int num){
if(num==0){
return 0;
}
if(num==1){
return 1;
}
return num*getReult(num-1);
}
2.100以内的阶乘
public static BigInteger sum(int i) {
if (i == 1) { return BigInteger.ONE; }
return BigInteger.valueOf(i).multiply(sum(i-1));
}
/**
* 计算从1+...num 的和
* 10000以内
* @param num
* @return
*/
public static int getSumReult(int num){
if(num==0){
return 0;
}
if(num==1){
return 1;
}
return num+getSumReult(num-1);
}
/***
* 二分法查找：二分查找 二分查找也称折半查找（Binary
* Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，
* 而且表中元素按关键字有序排列。
*/
public static int findTag(int a[], int tag) {
int start=0;
int end=a.length;
for (int i = 0; i < a.length; i++) {
int mid=(start+end)/2;
if(tag==a[mid]){
return mid;
}
if(tag>a[mid]){
start=mid+1;
}
if(tag<a[mid]){
end=mid-1;
}
}
return -1;//没有找到
}
/**
* 选择排序
* @param numbers
* @return
*/
public static int[] selectSortNew(int[] numbers){
int tempData;
for(int i = 0; i < numbers.length; i++){
int k = i;假设k的下标的值最小
for (int j = numbers.length-1; j >i; j--){
if (numbers[k] > numbers[j]){
k = j;
}
}
tempData = numbers[i];
numbers[i]=numbers[k];
numbers[k]=tempData;
}
return numbers;
}
public static void main(String[] args) {
int a[] = { 21,35,56,57,90,78,101};
int b[] = selectSortNew(a);
System.out.println(Arrays.toString(b));
}
/**
* 快速排序
* @param numbers
* @param start
* @param end
* @return
*/
public static int[] quickSortNew(int[] numbers, int start, int end) {
if (start < end) {
int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）
int temp; // 记录临时中间值
int i = start, j = end;
do {
while ((numbers[i] < base) && (i < end))
i++;
while ((numbers[j] > base) && (j > start))
j--;
if (i <= j) {
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j)
quickSortNew(numbers, start, j);
if (end > i)
quickSortNew(numbers, i, end);
}
return numbers;
}
public static void main(String[] args) {
int a[] = { 21,35,56,57,90,78,101};
int b[] = quickSortNew(a,0,6);
System.out.println(Arrays.toString(b));
}
// 冒泡排序算法 效率低
public static int[] BubbleSortInt(int[] array) {
int temp;
for (int i = 0; i < array.length; i++) {
for (int j = array.length - 1; j > i; j--) {
if (array[j - 1] > array[j]) {
// 如果前面一个数大于后面一个数则交换
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
public static void main(String[] args) {
int a[] = { 21,35,56,57,90,78,101};
int b[] = BubbleSortInt(a);
System.out.println(Arrays.toString(b));
}
}
/*
* 直接插入排序 1、首先比较数组的前两个数据，并排序；
* 2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
* 3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；
* 4、直至把最后一个元素放入适当的位置。
* 直接插入排序是稳定的。直接插入排序的平均时间复杂度为O(n2)。
*/
public static int[] sortChaRu(int[] arr) {
int tmp;
//无须序列
for(int i = 1; i < arr.length; i++) {
// 待插入数据
tmp = arr[i];
int j;
//有序序列
for(j = i - 1; j >= 0; j--) {
// 判断是否大于tmp，大于则后移一位
if(arr[j] > tmp) {
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = tmp;
}
return arr;
}
public static void main(String[] args) {
int a[] = { 21,35,56,57,90,78,101};
int b[] = sortChaRu(a);
System.out.println(Arrays.toString(b));
}
String数组中取出相同的字符串
把数组A的数据作为map的key和value， 然后用B的数据取值，不为NULL，说明相同Map接口 Map提供了一种映射关系，其中的元素是以键值对（key-value）的形式存储的，能够实现根据key快速查找value；Map中的键值对以Entry类型的对象实例形式存在；建（key值）不可重复，value值可以重复，一个value值可以和很多key值形成对应关系，每个建最多只能映射到一个值。
Map支持泛型，形式如：Map<K,V> Map中使用put(K key,V value)方法添加， HashMap类 HashMap是Map的一个重要实现类，也是最常用的，基于哈希表实现 HashMap中的Entry对象是无序排列的
Key值和value值都可以为null，但是一个HashMap只能有一个key值为null的映射（key值不可重复）
public static List<String> getSameElementByMap(String[] strArr1, String[] strArr2) {
// HashMap key值 不可重复 Key值和value值都可以为null
HashMap<String, Object> map = new HashMap<String, Object>();
// 数组A中的元素放入Map中
for (String string1 : strArr1) {
map.put(string1, string1);
}
List<String> list = new ArrayList<String>();
// 用数组B元素做为Key来取值，如为NULL则说明相同
for (String string2 : strArr2) {
Object j = map.get(string2);
if (j != null) {
list.add(string2);
// System.out.println("数组AB中相同的元素： "+j.toString());
} }
return list;
}
测试例子：
public static void main(String[] args) {
String[] strArr1 = { "21002023","21002030","21002225","21002389","21002393","21002396"};
String[] strArr2 = { "21002023","21002030","21002225","21002389","21002393","21002396",
"21002012","21002222","21002407"};
System.out.println(getSameElementByMap(strArr1, strArr2).toString());
int res1=getReult(12);
System.out.println(res1);
BigInteger res=sum(12);
System.out.println(res);
int sun=getSumReult(10000);
System.out.println(sun);
}
}
两个大于1000的数的乘积
public class NumDividEqual {
public char[] A;
public char[] B;
int n;
/**
* 将数组均分为两份，分别存入数组A和数组B中；
* @param input
*/
public NumDividEqual(char[] input){
n = input.length/2;
A = new char[n];
B = new char[n];
for(int i = 0; i<n;i++){
A[i] = input[i];
}
for(int i = 0; i<n;i++){
B[i] = input[i + n];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
package com.hyhl.test;
import java.util.Arrays;
public class BigIntMult {
/**
* 将字符数组倒序排列
* @param input
* @return
*/
public char[] reverse(char[] input) {
char[] output = new char[input.length];
for (int i = 0; i < input.length; i++) {
output[i] = input[input.length - 1 - i];
}
return output;
}
/**
* 将大整数平均分成两部分
* @param input
* @return
*/
public NumDividEqual partition(char[] input) {
return new NumDividEqual(input);
}
/**
* 求两数组中较大数组的长度，如果其长度为奇数则+1变偶
* @param num1
* @param num2
* @return
*/
public int calLength(char[] num1, char[] num2) {
int len = num1.length > num2.length ? num1.length : num2.length;
if (len == 1)
return 1;
len += len & 1;
return len;
}
/**
* 除去数字前面多余的0
* @param input
* @return
*/
public static char[] trimPrefix(char[] input) {
char[] ret = null;
for (int i = 0; i < input.length; i++) {
if (ret == null && input[i] == '0')
continue;
else {
if (ret == null) {
ret = new char[input.length - i];//出去数字前面多余的0
}
ret[i - (input.length - ret.length)] = input[i];
}
}
if (ret == null)
return new char[] { '0' };
return ret;
}
/**
* 数组如果长度不足n，则在数组前面补0，使长度为n。
* @param input 输入数组要求数字的最高位存放在数组下标最小位置
* @param n
* @return
*/
public static char[] format(char[] input, int n) {//；
if (input.length >= n) {
return input;
}
char[] ret = new char[n];
for (int i = 0; i < n - input.length; i++) {
ret[i] = '0';
}
for (int i = 0; i < input.length; i++) {
ret[n - input.length + i] = input[i];
}
return ret;
}
/**
* 大整数尾部补0。相当于移位，扩大倍数
* @param input
* @param n
* @return
*/
public char[] addTail(char[] input, int n) {//
char[] ret = new char[input.length + n];
for (int i = 0; i < input.length; i++) {
ret[i] = input[i];
}
for (int i = input.length; i < ret.length; i++) {
ret[i] = '0';
}
return ret;
}
/**
* 大整数加法
* @param num1
* @param num2
* @return
*/
public char[] add(char[] num1, char[] num2) {
int len = num2.length > num1.length ? num2.length : num1.length;
int carry = 0;//进位标识
num1 = format(num1, len);
num2 = format(num2, len);
char[] ret = new char[len + 1];
for (int i = len - 1; i >= 0; i--) {
int tmp = num1[i] + num2[i] - 96;
tmp += carry;
if (tmp >= 10) {
carry = 1;
tmp = tmp - 10;
} else {
carry = 0;
}
ret[len - i - 1] = (char) (tmp + 48);
}
ret[len] = (char) (carry + 48);//最后一次，最高位的进位
return trimPrefix(reverse(ret));
}
/**
* 大整数减法：
* @param num1 被减数，大整数乘法中只有一个减法(A+B)(C+D)-(AC+BD)=AC+BC>0,因此參數num1>num2且都为正
* @param num2 减数
* @return
*/
public static char[] sub(char[] num1, char[] num2) {
int lenMax = num1.length > num2.length ? num1.length : num2.length;
char[] newNum1 = Arrays.copyOf(format(num1, lenMax), lenMax);//字符串前面补0，使两串长度相同
char[] newNum2 = Arrays.copyOf(format(num2, lenMax), lenMax);
for(int i=0;i<lenMax;i++){//when num1-num2<0 return
if((newNum1[i]=='0' && newNum1[i]=='0') || newNum1[i] == newNum2[i]){//newNum1 is bigger;
continue;
}
else if(newNum1[i] < newNum2[i]){//不滿足參數num1>num2；
System.out.println("The Parameter in sub(A,B).A MUST Bigger Than B!");
System.exit(0);
}
else break;
}
for(int i=lenMax-1;i>=0;i--){
if(newNum1[i] < newNum2[i]){//result < 0
newNum1[i] = (char) (newNum1[i] + '0' + 10 - newNum2[i]);
newNum1[i-1] = (char) (newNum1[i-1] - 1);
}
else{
newNum1[i] = (char) (newNum1[i] + '0' - newNum2[i]);
}
}
return trimPrefix(newNum1);
}
/**
* 大整数乘法
* @param num1
* @param num2
* @return
*/
public char[] mult(char[] num1, char[] num2) {
char[] A, B, C, D, AC, BD, AjB, CjD, ACjBD, AjBcCjD, SUM;
int N = calLength(num1, num2);//求两数组中较大数组的长度，如果长度为奇数则+1变偶，方便二分成两部分
num1 = format(num1, N);//数组高位存整数的高位数；数字前面补0，使长度为n；
num2 = format(num2, N);
if (num1.length > 1) {
NumDividEqual nu1 = partition(num1);//将大整数平均分成两部分
NumDividEqual nu2 = partition(num2);
A = nu1.A;
B = nu1.B;
C = nu2.A;
D = nu2.B;
AC = mult(A, C);//分治求大整数乘法
BD = mult(B, D);
AjB = add(A,B);
CjD = add(C,D);
ACjBD = add(AC,BD);
AjBcCjD = mult(AjB, CjD);
char[] tmp1 = addTail(sub(AjBcCjD, ACjBD), N / 2);//尾部补0，相当于移位
char[] tmp2 = add(addTail(AC, N), BD);
SUM = add(tmp1, tmp2);
char[] test = trimPrefix(SUM);//除去结果前面多余的0
return test;
} else {
Integer ret = (num1[0] - 48) * (num2[0] - 48);
return ret.toString().toCharArray();
}
}
public static void main(String[] args) {
String st1 = "16874631564134797979843343322342245222344533334432223345224432212";
String st2 = "1646816547674468877974513161584444444221333498800000998898383818191292098887773999919";
char[] a = st1.toCharArray();
char[] b = st2.toCharArray();
BigIntMult bg = new BigIntMult();
//大整数乘法
char[] ret = bg.mult(a, b);
System.out.println(ret);
}
}
算法：
插入排序的时间复杂度为：O(N^2)
希尔排序的时间复杂度为：平均为：O(N^3/2) 最坏： O(N^2)
归并排序时间复杂度为： O(NlogN) 空间复杂度为: O(N)
1.堆排序
public int[] heapSort(int[] array) {
// 初始建堆，array[0]为第一趟值最大的元素
array = buildMaxHeap(array);
for (int i = array.length - 1; i > 1; i--) {
// 将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// 整理，将剩余的元素整理成堆
adjustDownToUp(array, 0, i);
}
return array;
}
// 构建大根堆：将array看成完全二叉树的顺序存储结构
private int[] buildMaxHeap(int[] array) {
// 从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
for (int i = (array.length - 2) / 2; i >= 0; i--) {
adjustDownToUp(array, i, array.length);
}
return array;
}
// 将元素array[k]自下往上逐步调整树形结构
private void adjustDownToUp(int[] array, int k, int length) {
int temp = array[k];
for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { // i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
if (i < length && array[i] < array[i + 1]) { // 取节点较大的子节点的下标
i++; // 如果节点的右孩子>左孩子，则取右孩子节点的下标
}
if (temp >= array[i]) { // 根节点 >=左右子女中关键字较大者，调整结束
break;
} else { // 根节点 <左右子女中关键字较大者
array[k] = array[i]; // 将左右子结点中较大值array[i]调整到双亲节点上
k = i; // 【关键】修改k值，以便继续向下调整
}
}
array[k] = temp; // 被调整的结点的值放人最终位置
}
6.希尔排序
希尔排序(缩小增量法)属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序, 从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去， 进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生： h = 3 * h +1反过来程序需要反向计算h序列，应该使用h=(h-1)/3
*/
public static int[] shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
return data;
}
- 7. /**
* 归并排序 分而治之(divide - conquer);
* 每个递归过程涉及三个步骤
* 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列,每个子序列包括 n/2 个元素.
* 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
* 第三, 合并: 合并两个排好序的子序列,生成排序结果.
* （1）稳定性 归并排序是一种稳定的排序。
* （2）存储结构要求 可用顺序存储结构。也易于在链表上实现。
* （3）时间复杂度对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
* （4）空间复杂度 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
* 注意：若用单链表做存储结构，很容易给出就地的归并排序
*/
public static int[] mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
// 左右归并
merge(a, low, mid, high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int x = 0; x < temp.length; x++) {
a[x + low] = temp[x];
}
}
------------------------5种查找------------------------------------------------------------------
线性查找分为：顺序查找、折半查找。
查找有两种形态：
分为：破坏性查找，比如有一群mm，我猜她们的年龄，第一位猜到了是23+，此时这位mm已经从我脑海里面的mmlist中remove掉了。哥不找23+的，所以此种查找破坏了原来的结构。非破坏性查找， 这种就反之了，不破坏结构。
顺序查找：这种非常简单，就是过一下数组，一个一个的比，找到为止。
1 // 顺序查找
public static int SequenceSearch(int[] array, int key) {
for (int i = 0; i < array.length; i++) {
// 查找成功，返回序列号
if (key == array[i])
return i;
}
// 未能查找，返回-1
return -1;
}
2. 折半查找 长度必须是奇数
第一： 数组必须有序，不是有序就必须让其有序，大家也知道最快的排序也是NLogN
第二： 这种查找只限于线性的顺序存储结构。
public static int BinarySearchNew(int[] array, int tag) {
int frist = 0;
int end = array.length;
for (int i = 0; i < array.length; i++) {
int middle = (frist + end) / 2;
if (tag == array[middle]) {
// 正好相等 则返回查询结果
return middle;
}
if (tag > array[middle]) {
// 大于 middle
frist = middle + 1;
}
if (tag < array[middle]) {
// 下于 middle
end = middle - 1;
}
}
return -1;
}
线性查找时间复杂度：O(n);
折半无序（用快排活堆排）的时间复杂度：O(NlogN)+O(logN);
折半有序的时间复杂度：O(logN);
3其实常用的做哈希的手法有“五种”：
第一种：”直接定址法“：很容易理解，key=Value+C； 这个“C"是常量。Value+C其实就是一个简单的哈希函数。
第二种：“除法取余法”： 很容易理解， key=value%C;解释同上。
第三种：“数字分析法”：比如有一组value1=112233，value2=112633，value3=119033， 针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。
第四种：“平方取中法”。
第五种：“折叠法”：比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160， 然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的目地。
解决冲突常用的手法也就2种：
第一种：开放地址法。
所谓”开放地址“，其实就是数组中未使用的地址。也就是说，在发生冲突的地方，后到的那个元素（可采用两种方式:①线性探测，②函数探测）向数组后寻找"开放地址“然后把自己插进入。
第二种：链接法。原理就是在每个元素上放一个”指针域“，在发生冲突的地方，后到的那个元素将自己的数据域抛给冲突中的元素，此时冲突的地方就形成了一个链表。
设计函数采用：除法取余法。
冲突方面采用:开放地址线性探测法。
5二叉排序树查找
1. 概念:
<1> 其实很简单，若根节点有左子树，则左子树的所有节点都比根节点小。若根节点有右子树，则右子树的所有节点都比根节点大。
<2> 如图就是一个”二叉排序树“，然后对照概念一比较比较
/**
* 二叉排序树
* 采用广度优先法则来遍历排序二叉树得到的不是有序序列，
* 采用中序遍历来遍历排序二叉树才可以得到有序序列。
*
*/
public class SortedBinTree <T extends Comparable>{
static class Node {
Object data;
Node parent;
Node left;
Node right;
public Node(Object data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString() {
return "[data=" + data + "]";
}
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj.getClass() == Node.class) {
Node target = (Node) obj;
return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent;
}
return false;
}
}
private Node root;
// 两个构造器用于创建排序二叉树
public SortedBinTree() {
root = null;
}
public SortedBinTree(T o) {
root = new Node(o, null, null, null);
}
// 添加节点
public void add(T ele) {
// 如果根节点为null
if (root == null) {
root = new Node(ele, null, null, null);
} else {
Node current = root;
Node parent = null;
int cmp = 0;
// 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
do {
parent = current;
cmp = ele.compareTo(current.data);
// 如果新节点的值大于当前节点的值
if (cmp > 0) {
// 以右子节点作为当前节点
current = current.right;
} else {
// 如果新节点的值小于当前节点的值
// 以左节点作为当前节点
current = current.left;
}
}
while (current != null);
// 创建新节点
Node newNode = new Node(ele, parent, null, null);
// 如果新节点的值大于父节点的值
if (cmp > 0) {
// 新节点作为父节点的右子节点
parent.right = newNode;
} else {
// 如果新节点的值小于父节点的值
// 新节点作为父节点的左子节点
parent.left = newNode;
}
}
}
// 删除节点
public void remove(T ele) {
// 获取要删除的节点
Node target = getNode(ele);
if (target == null) {
return;
}
// 左、右子树为空
if (target.left == null && target.right == null) {
// 被删除节点是根节点
if (target == root) {
root = null;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 将target的父节点的left设为null
target.parent.left = null;
} else {
// 将target的父节点的right设为null
target.parent.right = null;
}
target.parent = null;
}
} else if (target.left == null && target.right != null) {
// 左子树为空，右子树不为空
// 被删除节点是根节点
if (target == root) {
root = target.right;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向target的右子树
target.parent.left = target.right;
} else {
// 让target的父节点的right指向target的右子树
target.parent.right = target.right;
}
// 让target的右子树的parent指向target的parent
target.right.parent = target.parent;
}
} else if (target.left != null && target.right == null) {
// 左子树不为空，右子树为空
// 被删除节点是根节点
if (target == root) {
root = target.left;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向target的左子树
target.parent.left = target.left;
} else {
// 让target的父节点的right指向target的左子树
target.parent.right = target.left;
}
// 让target的左子树的parent指向target的parent
target.left.parent = target.parent;
}
} else {
// 左、右子树都不为空
// leftMaxNode用于保存target节点的左子树中值最大的节点
Node leftMaxNode = target.left;
// 搜索target节点的左子树中值最大的节点
while (leftMaxNode.right != null) {
leftMaxNode = leftMaxNode.right;
}
// 从原来的子树中删除leftMaxNode节点
leftMaxNode.parent.right = null;
// 让leftMaxNode的parent指向target的parent
leftMaxNode.parent = target.parent;
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向leftMaxNode
target.parent.left = leftMaxNode;
} else {
// 让target的父节点的right指向leftMaxNode
target.parent.right = leftMaxNode;
}
leftMaxNode.left = target.left;
leftMaxNode.right = target.right;
target.parent = target.left = target.right = null;
}
}
// 根据给定的值搜索节点
public Node getNode(T ele) {
// 从根节点开始搜索
Node p = root;
while (p != null) {
int cmp = ele.compareTo(p.data);
// 如果搜索的值小于当前p节点的值
if (cmp < 0) {
// 向左子树搜索
p = p.left;
} else if (cmp > 0) {
// 如果搜索的值大于当前p节点的值
// 向右子树搜索
p = p.right;
} else {
return p;
}
}
return null;
}
// 广度优先遍历
public List<Node> breadthFirst() {
Queue<Node> queue = new ArrayDeque<Node>();
List<Node> list = new ArrayList<Node>();
if (root != null) {
// 将根元素入“队列”
queue.offer(root);
}
while (!queue.isEmpty()) {
// 将该队列的“队尾”的元素添加到List中
list.add(queue.peek());
Node p = queue.poll();
// 如果左子节点不为null，将它加入“队列”
if (p.left != null) {
queue.offer(p.left);
}
// 如果右子节点不为null，将它加入“队列”
if (p.right != null) {
queue.offer(p.right);
}
}
return list;
}
//二叉排序的查询
public static void main(String[] args) {
SortedBinTree<Integer> tree = new SortedBinTree<Integer>();
// 添加节点
tree.add(5);
tree.add(20);
tree.add(10);
tree.add(3);
tree.add(8);
tree.add(15);
tree.add(30);
System.out.println(tree.breadthFirst());
// 删除节点
tree.remove(20);
System.out.println(tree.breadthFirst());
}
}
值的注意的是：二叉排序树同样采用“空间换时间”的做法。
突然发现，二叉排序树的中序遍历同样可以排序数组，呵呵，不错！
PS: 插入操作：O(LogN)。 删除操作：O(LogN)。 查找操作：O(LogN）。