[数据结构与算法]数据结构与算法

1.稀疏数组

/**
 * 将稀疏数组进行压缩
 * 处理方法：
 *      1. 记录数组一共有几行几列，有多少个不同的值。
 *      2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
 * 
 * 例子：
 * 
 * 稀疏数组：
 * 0    0   0   22  0   0   15
 * 0    11  0   0   0   17  0
 * 0    0   0   -6  0   0   0
 * 0    0   0   0   0   39  0       
 * 91   0   0   0   0   0   0
 * 0    0   28  0   0   0   0
 * 
 * 压缩后：
 * 行   列  值
 * 6    7   8   // 一共有几行几列以及几个非0值
 * 0    3   22
 * 0    6   15
 * 1    1   11
 * 1    5   17
 * 2    3   -6
 * 3    5   39
 * 4    0   91
 * 5    2   28
 */
public class SparseArray {
    public static void main(String[] args) {
        //创建一个二维数组
        int[][] charArray = new int[11][11];
        charArray[1][2] = 1;
        charArray[2][3] = 2;

        //输出原始的数组
        System.out.println("原始的二维数组：");
        for (int[] row : charArray) {
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //统计一共有多少个非0元素
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if(charArray[i][j] != 0){
                    sum++;
                }
            }
        }
        
        //压缩数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if(charArray[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = charArray[i][j];
                }
            }
        }

        //输出压缩数组
        System.out.println();
        System.out.println("转换后的稀疏数组为：");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);            
        }
        System.out.println();

        //恢复二维数组
        int[][] charArray2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            charArray2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("恢复后的二维数组：");
        for (int[] row : charArray2) {
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

2.队列

import java.util.Scanner;

/**
 * 环形队列
 * 实现思路：
 * 1. front指向队列的第一个元素。初始值front=0;
 * 2. rear指向队列的最后一个元素的后一个位置。希望空出一个空间做约定。初始值reaer=0。
 * 3. 队列满的条件：(rear + 1) % maxSize = front
 * 4. 队列空的条件：rear == front
 * 5. 队列中的有效数据的个数：(rear + maxSize - front) % maxSize
 */
public class ArrayQueue {
    public static void main(String[] args) {
        Queue queue = new Queue(3);
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop){
            System.out.println("s:显示队列");
            System.out.println("a:添加数据");
            System.out.println("g:取出数据");
            System.out.println("h:查头数据");
            System.out.println("e:退出程序");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数：");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是：%d", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int head = queue.headQueue();
                        System.out.printf("队列的头数据是：%d", head);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
            System.out.println("程序退出！");
        }
    }
}

//使用数组模拟队列
class Queue{
    private int maxSize; //最大容量
    private int front;  // 队列头
    private int rear;   //队列尾
    private int[] arr;  //用于存放数据

    //创建队列的构造器
    public Queue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
        front = 0;
        rear = 0;
    }

    //判断队列是否满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    //判断队列是否空
    public boolean isEmpty(){
        return rear == front;
    }

    //添加数据到队列
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列满了..");
            return;
        }        
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    //数据出队列
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列空，不能取数据");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //显式队列的所有数据
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列为空...");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    //求出队列有效数据个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //显式队列的头数据
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空...");
        }
        return arr[front];
    }
}

3.链表

3.1单向链表

/**
 * 单向链表的实现
 */
public class SingleLinkedList {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        LinkedList linkedList = new LinkedList();
        linkedList.add(hero1);
        linkedList.add(hero2);
        linkedList.add(hero3);
        linkedList.add(hero4);
        linkedList.list();
    }
}

class LinkedList{
    private HeroNode head = new HeroNode(0, "", "");
    private HeroNode tail = head;

    //添加操作
    public void add(HeroNode heroNode){
        tail.next = heroNode;
        tail = tail.next;
    }

    //按照顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false; // 是否已经存在此编号
        while(true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no > heroNode.no){
                break;
            }else if(temp.next.no == heroNode.no){ // 编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.printf("准备插入的英雄编号%d已经存在了", heroNode.no);
        }else{
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //显示链表
    public void list(){
        if(head.next == null){
            System.out.println("俩表为空");
            return;
        }
        HeroNode temp = head.next;
        while(true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //根据编号修改信息
    public void update(HeroNode heroNode){
        if(head.next == null){
            System.out.println("链表为空..");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while(true){
            if(temp == null){ // 链表已经遍历完毕
                break;
            }
            if(temp.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        }else{
            System.out.printf("未找到该编号%d", heroNode.no);
        }
    }

    //删除节点
    public void delete(int no){
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }else{
            System.out.printf("在链表中不存在编号%d", no);
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode[no=" + no + ",name=" + name + ",nickName=" + nickName + "]";
    }
}

3.2双向链表

/**
 * 双向链表的实现
 */
public class DoubleLinkedList {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        LinkedList linkedList = new LinkedList();
        linkedList.add(hero1);
        linkedList.add(hero2);
        linkedList.add(hero3);
        linkedList.add(hero4);
        linkedList.list();
    }
}

class LinkedList{
    private HeroNode head = new HeroNode(0, "", "");
    private HeroNode tail = head;

    //添加操作
    public void add(HeroNode heroNode){
        tail.next = heroNode;
        heroNode.pre = tail;
    }

    //显示链表
    public void list(){
        if(head.next == null){
            System.out.println("俩表为空");
            return;
        }
        HeroNode temp = head.next;
        while(true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //根据编号修改信息
    public void update(HeroNode heroNode){
        if(head.next == null){
            System.out.println("链表为空..");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到该节点
        while(true){
            if(temp == null){ // 链表已经遍历完毕
                break;
            }
            if(temp.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        }else{
            System.out.printf("未找到该编号%d", heroNode.no);
        }
    }

    //删除节点
    public void delete(int no){
        if(head.next == null){
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while(true){
            if(temp == null){
                break;
            }
            if(temp.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.pre.next = temp.next;
            if(temp.next != null){ // 删除最后一个节点的话下边这个就不需要了
                temp.next.pre = temp.pre;   
            }            
        }else{
            System.out.printf("在链表中不存在编号%d", no);
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;
    public HeroNode pre;

    public HeroNode(int no, String name, String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode[no=" + no + ",name=" + name + ",nickName=" + nickName + "]";
    }
}

3.3环形单向链表

/**
 * 环形单向链表的实现
 */
public class CircleLinkedList {
    public static void main(String[] args) {
        LinkedList_circle linkedList = new LinkedList_circle();
        linkedList.add(5);
        linkedList.show();
    }
}

class LinkedList_circle{
    private Boy first = null;

    //添加
    public void add(int nums){
        if(nums < 1){
            System.out.println("nums的值不正确");
            return;
        }
        Boy currentBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if(i == 1){
                first = boy;
                first.setNext(first);
                currentBoy = first;
            }else{
                currentBoy.setNext(boy);
                boy.setNext(first);
                currentBoy = boy;
            }            
        }
    }

    //遍历
    public void show(){
        if(first == null){
            System.out.println("没有任何boy");
            return;
        }
        Boy curBoy = first;
        while(true){
            System.out.printf("小孩的编号%d\n", curBoy.getNo());
            if(curBoy.getNext() == first){
                break;
            }
            curBoy = curBoy.getNext();
        }
    }
}

//创建一个Boy类
class Boy{
    private int no;
    private Boy next;
    public Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
    public Boy getNext() {
        return next;
    }
}

4.栈

import java.util.Scanner;

import javax.lang.model.element.Element;

/**
 * 栈的实现
 */
public class ArrayStack {
    public static void main(String[] args) {
        /**
        Stack_Array stack = new Stack_Array(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);    
        while(loop){
            System.out.println("show:显示栈");
            System.out.println("push:入栈");
            System.out.println("pop:出栈");
            System.out.println("exit:退出");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.show();
                    break;
                case "push":
                    System.out.println("请输入一个数:");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据是:%d", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    System.out.println("指令有误.");
                    break;
            }
        }
         */
        
        //实现计算器
        String expression = "3+2*6-2";
        //创建两个栈，一个数栈一个符号栈
        Stack_Array numStack = new Stack_Array(10);
        Stack_Array operStack = new Stack_Array(10);
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';
        String keepNum = "";//用于拼接多位数
        while(true){
            ch = expression.substring(index, index + 1).charAt(0);
            if(operStack.isOper(ch)){
                if(!operStack.isEmpty()){
                    if(operStack.priority(ch) <= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        numStack.push(res);
                        operStack.push(ch);
                    }
                }else{
                    operStack.push(ch);
                }
            }else{
                //numStack.push(ch - 48);
                //处理多位数
                keepNum += ch;
                if(index == expression.length() - 1){
                    numStack.push(Integer.parseInt(keepNum));
                }else{
                    if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))){
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            }
            index++;
            if(index >= expression.length()){
                break;
            }
        }

        while(true){
            if(operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf("表达式%s = %d", expression, numStack.pop());
    }
}

class Stack_Array{
    private int maxSize;  //最大容量
    private int[] stack;  //数组模拟栈
    private int top = -1; //栈顶，初始化为-1

    public Stack_Array(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //栈满
    public boolean isFull(){
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int value){
        if(isFull()){
            System.out.println("栈满.");
            return;
        }
        top++;
        stack[top] =  value;
    }

    //出栈
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈空.");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //遍历栈
    public void show(){
        if(isEmpty()){
            System.out.println("栈空.");
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    //运算符等级
    public int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;
        }
    }

    //判断是不是一个运算符
    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1, int num2, int oper){
        int res = 0;
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

    //返回栈顶的值
    public int peek(){
        return stack[top];
    }
}

5.排序算法

5.1冒泡排序

import java.util.Arrays;

/**
 * 冒泡排序的实现
 * 
 * 通过对排序序列从前向后(从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换，
 * 使值较大的元素逐渐从前向后移动。
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        System.out.println("冒泡排序前数组：" + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("冒泡排序后数组：" + Arrays.toString(arr));
    }

    public static void bubbleSort(int [] arr){
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if(!flag){
                break;
            }else{
                flag = false;
            }
        }
    }
}

5.2选择排序

import java.util.Arrays;

/**
 * 选择排序
 * 
 * 第一次从arr[0]~arr[n-1]选取最小值，与arr[0]交换
 * 第二次从arr[1]~arr[n-1]选取最小值，与arr[1]交换
 * ....
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        System.out.println("选择排序之前：" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("选择排序之后：" + Arrays.toString(arr));
    }

    public static void selectSort(int[] arr){
        int min = 0;
        int index;
        for (int i = 0; i < arr.length; i++) {
            min = arr[i];
            index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(min > arr[j]){
                    min = arr[j];
                    index = j;
                }
            }
            arr[index] = arr[i];
            arr[i] = min;
        }
    }
}

5.3插入排序

import java.util.Arrays;

/**
 * 插入排序
 * 
 * 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表只包含一个元素
 * 无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排
 * 序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之称为
 * 新的有序表
 * 
 * 例子：
 * 初始 (17) 3 25 14 20 9
 * 1    (3,17) 25 14 20 9
 * 2    (3, 17, 25) 14 20 9
 * 3    (3, 14, 17, 25) 20 9
 * 4    (3, 14, 17, 20, 25) 9
 * 5    (3, 9, 14, 17, 20, 25)
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {17, 3, 25, 14, 20, 9};
        System.out.println("插入排序前的数组："+ Arrays.toString(arr));
        insertSort(arr);
        System.out.println("插入排序后的数组："+ Arrays.toString(arr));
    }

    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] =arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;
        }
    }
}

5.4希尔排序

import java.util.Arrays;

/**
 * 希尔排序
 * 
 * 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减小，每组包含的关键词越来越多，当增量减至1时，
 * 整个文件恰被分成一组，算法便被终止。
 * 
 * 例子
 * 原始数组：8 9 1 7 2 3 5 4 6 0
 * 第一轮：
 *      分组：[8 3] [9 5] [1 4] [7 6] [2 0]
 *      排序：3 5 1 6 0 8 9 4 7 2
 * 第二轮：
 *      分组：[3 1 0 9 7] [5 6 8 4 2]
 *      排序：0 2 1 4 3 5 7 6 9 8
 * 第三轮：
 *      分组：[0 2 1 4 3 5 7 6 9 8]
 *      排序：0 1 2 3 4 5 6 7 8 9
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("排序前："+ Arrays.toString(arr));
        shellSort2(arr);
        System.out.println("排序后："+ Arrays.toString(arr));
    }

    //交换式希尔排序
    public static void shellSort(int[] arr){
        int temp = 0;
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j - i; k >= 0; k -= i) {
                    if(arr[k] > arr[k + i]){
                        temp = arr[k];
                        arr[k] = arr[k + i];
                        arr[k + i] = temp;
                    }
                }
            }
        }
    }

    //移位式希尔排序
    public static void shellSort2(int[] arr){
        for (int i = arr.length / 2; i > 0; i/=2) {            
            for (int k = i; k < arr.length; k++) {
                int j = k;
                int temp = arr[j];
                while(j - i >= 0 && temp < arr[j - i]){
                    arr[j] = arr[j - i];
                    j -= i;
                }
                arr[j] = temp;
            }
        }
    }
}

5.5快速排序

import java.util.Arrays;

/**
 * 快速排序
 * 
 * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比
 * 另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排
 * 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * 
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        System.out.println("快速排序前数组为：" + Arrays.toString(arr));
        qucikSort(arr, 0, arr.length - 1);
        System.out.println("快速排序后数组为：" + Arrays.toString(arr));
    }

    public static void qucikSort(int[] arr, int left, int right){
        int l = left;  //左下标
        int r = right; //右下标
        int temp = 0;
        int pivot = arr[(left + right) / 2]; // 获得中轴值
        while(l < r){
            while(arr[l] < pivot){ // 找到左边比中轴值小的
                l += 1;
            }
            while(arr[r] > pivot){  // 找到右边比中轴值大的
                r -= 1;
            }
            if(l >= r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            if(arr[l] == pivot){
                r -= 1;
            }
            if(arr[r] == pivot){
                l += 1;
            }
        }
        if(l == r){
            l += 1;
            r -= 1;
        }
        if(left < r){
            qucikSort(arr, left, r);
        }
        if(right > l){
            qucikSort(arr, l, right);
        }
    }
}

5.6归并排序

import java.util.Arrays;

/**
 * 归并排序
 * 
 * 利用归并的思想实现的排序方法，该算法采用经典的分治策略
 * 分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案修补再一起，即分而治之。
 * 
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 6, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        System.out.println("归并排序前的数组是：" + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("归并排序后的数组是：" + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            //左递归分解
            mergeSort(arr, left, mid, temp);
            //右递归分解
            mergeSort(arr, mid + 1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = left;  //左边有序序列的初始索引
        int j = mid + 1;  //右边有序序列的初始索引
        int t = 0;  //temp数组的索引
        
        while(i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else{
                temp[t] = arr[j];
                j++;
                t++;
            }
        }

        //左边的有剩余
        while(i <= mid){
            temp[t] = arr[i];
            i++;
            t++;
        }

        //右边有剩余
        while(j <= right){
            temp[t] = arr[j];
            j++;
            t++;
        }

        //每次不是将所有都拷贝到temp中
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}

5.7基数排序

import java.util.Arrays;

/**
 * 基数排序(桶排序)
 * 
 * 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
 * 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直
 * 到最高位排序完成以后，数列就变成一个有序序列。
 * 
 * 桶0 1 2 3 4 5 6 7 8 9
 * 第一轮：取个位数放到对应桶
 * 第二轮：取十位数放到对应桶
 * 第三轮：取千位数放到对应桶
 * ....
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    public static void radixSort(int[] arr){
        //定义桶
        int[][] bucket = new int[10][arr.length];
        //记录每个桶中的数据
        int[] bucketElementCounts = new int[10];
        //计算最大的数以及它的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //数据放进桶里边
        for (int i = 0; i < maxLength; i++) {
            for (int j = 0; j < arr.length; j++) {
                //获取到每一位的值
                int digitOfElement = arr[j] / (int)Math.pow(10, i) % 10;
                //将该为对应的值放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            //将数据放入到原数组当中
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if(bucketElementCounts[k] != 0){ // 桶中数据不为0
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "轮：" + Arrays.toString(arr));
        }
    }
}

5.8堆排序

package Sort;

import java.util.Arrays;

/**
 * 堆排序
 * 基本思想：
 *  1.将待排序序列构造成一个大顶堆
 *  2.此时,整个序列的最大值就是堆顶的根节点
 *  3.将其与末尾元素进行交换，此时末尾成为最大值
 *  4.然后将剩余n-1个元素重新构成一个堆
 * 
 * 大顶堆：该节点的值大于其左右子节点的值【升序】
 * 小顶堆：该节点的值小于其左右子节点的值【降序】
 * 
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void headSort(int[] arr) {
        int temp = 0;
        System.out.println("堆排序!!!");

        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }

    //调整为大顶堆
    /**
     * 
     * @param arr 待调整数组
     * @param i 非叶子节点的索引
     * @param length 要调整元素的个数(在不断的减少)
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if(k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if(arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        arr[i] = temp;
    }   
}

6.查找算法

6.1二分查找

package Search;
/**
 * 二分查找的前提是该数组是有序的
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int index = binarySearch(arr, 0, arr.length, 1234);
        System.out.println("索引为：" + index);
    }

    /**
     * 
     * @param arr 数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 要查找的值
     * @return 找到返回下标，没找到返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal){
        if(left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if(findVal > midVal){
            return binarySearch(arr, mid + 1, right, findVal);
        }else if(findVal < midVal){
            return binarySearch(arr, left, mid - 1, findVal);
        }else{
            return mid;
        }
    }
}

6.2插值查找

package Search;

/**
 * 插值查找
 * 类似于二分查找，不同的是插值查找每次从自适应mid处开始查找
 * int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left])
 * 
 * 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
 * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        int index = insertValueSearch(arr, 0, args.length, 30);
        System.out.println("索引为：" + index);
    }

    public static int insertValueSearch(int[] arr, int left, int right, int findVal){
        if(left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){
            return -1;
        }
        //关键点
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if(findVal > midVal){
            return insertValueSearch(arr, mid + 1, right, findVal);
        }else if(findVal < midVal){
            return insertValueSearch(arr, left, mid - 1, findVal);
        }else{
            return mid;
        }
    }
}

7.哈希表

package HashTable;

import java.util.Scanner;

import jdk.nashorn.internal.ir.EmptyNode;

/**
 * 哈希表的实现：数组+链表
 */
public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hTab = new HashTab(7);
        String key = "";
        Scanner sc = new Scanner(System.in);
        while(true){
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("exit:退出系统");
            key = sc.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = sc.nextInt();
                    System.out.println("输入姓名");
                    String name = sc.next();
                    Emp emp = new Emp(id, name);
                    hTab.add(emp);
                    break;
                case "list":
                    hTab.list();
                    break;
                case "find":
                    System.out.println("输入查找的id");
                    id = sc.nextInt();
                    hTab.findEmpById(id);
                    break;
                case "exit":
                    sc.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

//  雇员
class Emp {
    public int id;
    public String name;
    public Emp next;
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

//链表
class EmpLikedList {
    private Emp head; //头指针

    //添加雇员
    public void add(Emp emp){
        if(head == null){
            head = emp;
            return;
        }
        Emp curEmp = head;
        while(true){
            if(curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
        curEmp.next = emp;
    }

    //遍历雇员
    public void list(int no){
        if(head == null){
            System.out.println("第"+ (no + 1) +"链表信息为空.");
            return;
        }
        System.out.println("第"+ (no + 1) +"链表的信息为：");
        Emp curEmp = head;
        while(true){
            System.out.printf("=> id = %d, name=%s\t'", curEmp.id, curEmp.name);
            if(curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    //根据id查找雇员
    public Emp findEmpById(int id){
        if(head == null){
            System.out.println("链表为空");
            return null;
        }
        Emp  curEmp = head;
        while(true){
            if(curEmp.id == id){
                break;
            }
            if(curEmp.next == null){
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }
}

//创建hashTab
class HashTab{
    private EmpLikedList[] empLikedLists;
    private int size;

    public HashTab(int size) {
        this.size = size;
        empLikedLists = new EmpLikedList[size];
        for (int i = 0; i < size; i++) {
            empLikedLists[i] = new EmpLikedList();
        }
    }

    //添加
    public void add(Emp emp){
        int empLikedListNo = hashFun(emp.id);
        empLikedLists[empLikedListNo].add(emp);
    }

    //散列函数
    public int hashFun(int id){
        return id % size;
    }

    //遍历所有的链表
    public void list(){
        for (int i = 0; i < size; i++) {
            empLikedLists[i].list(i);
        }
    }

    //根据输入id查找雇员
    public void findEmpById(int id){
        int empLikedListNo = hashFun(id); 
        Emp emp = empLikedLists[empLikedListNo].findEmpById(id);
        if(emp != null){
            System.out.printf("在第%d找到雇员id = %d\n", (empLikedListNo + 1), id);
        }else{
            System.out.println("没有找到该雇员信息.");
        }
    }
}

8.二叉树

8.1 二叉树链表实现

package Tree;
/**
 * 二叉树的前序，中序，后序遍历及查找
 */
public class BinaryTree {
    public static void main(String[] args) {
        Tree tree = new Tree();
        HeroNode node1 = new HeroNode(1, "zhangsan");
        HeroNode node2 = new HeroNode(2, "lis");
        HeroNode node3 = new HeroNode(3, "wanger");
        HeroNode node4 = new HeroNode(4, "mazi");
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        tree.setRoot(node1);

        //前序遍历
        tree.preOrder();

        //中序遍历
        tree.infixOrder();

        //后序遍历
        tree.postOrder();
    }
}

//二叉树
class Tree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空.");
        }
    }

    //中序遍历
    public void infixOrder() {
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空.");
        }
    }

    //后序遍历
    public void postOrder() {
        if(this.root != null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空.");
        }
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        if(root != null){
            return root.preOrderSearch(no);
        }else{
            return null;
        }
    }
    
    //中序查找
    public HeroNode infixOrderSearch(int no){
        if(root != null){
            return root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    //后序查找
    public HeroNode postOrderSearch(int no){
        if(root != null){
            return root.postOrderSearch(no);
        }else{
            return null;
        }
    }

    //删除结点
    public void delNode(int no){
        if(root != null){
            if(root.getNo() == no){
                root = null;
            }else{
                root.delNode(no);   
            }            
        }else{
            System.out.println("空树，不能删除.");
        }
    }
}

//创建HeroNode结点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public HeroNode getLeft() {
        return left;
    }
    public void setLeft(HeroNode left) {
        this.left = left;
    }
    public HeroNode getRight() {
        return right;
    }
    public void setRight(HeroNode right) {
        this.right = right;
    }
    
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + "]";
    }
    
    //先序遍历
    public void preOrder() {
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder() {
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if(this.left != null){
            this.left.postOrder();
        }
        if(this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.no == no){
            return this;
        }
        HeroNode node = null;
        if(this.left != null){
            node = this.left.preOrderSearch(no);
        }
        if(node != null){
            return node;
        }
        if(this.right != null){
            node = this.right.preOrderSearch(no);
        }
        return node;
    }

    //中序查找
    public HeroNode infixOrderSearch(int no){
        HeroNode node = null;
        if(this.left != null){
            node = this.left.infixOrderSearch(no);
        }
        if(node != null){
            return node;
        }
        if(this.no == no){
            return this;
        }
        if(this.right != null){
            node = this.right.infixOrderSearch(no);
        }
        return node;
    }

    //后序查找
    public HeroNode postOrderSearch(int no){
        HeroNode node = null;
        if(this.left != null){
            node = this.left.postOrderSearch(no);
        }
        if(node != null){
            return node;
        }
        if(this.right != null){
            node = this.right.postOrderSearch(no);
        }
        if(this.no == no){
            return this;
        }
        return node;
    }

    //递归删除
    public void delNode(int no){
        //左节点不为空，且左节点等于要删除的值
        if(this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        //右节点不为空，且右节点等于要删除的值
        if(this.right != null && this.right.no == no){
            this.right = null;
            return;
        }
        //递归删除
        if(this.left != null){
            this.left.delNode(no);
        }
        if(this.right != null){
            this.right.delNode(no);
        }
    }
}

8.2顺序存储二叉树

package Tree;
/**
 * 顺序存储二叉树【数组的形式】
 * 特点：
 *  1.顺序二叉树通常只考虑完全二叉树
 *  2.第n个元素的左子节点为2*n+1
 *  3.第n个元素的右子节点为2*n+2
 *  4.第n个元素的父节点为(n-1)/2
 *  5.n:表示二叉树中的第几个元素(按0开始编号)
 */
public class ArrBinaryTree {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        arrTree tree = new arrTree(arr);
        tree.preOrder();
    }
}

class arrTree{
    private int[] arr;

    public arrTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder() {
        this.preOrder(0);
    }
    
    //顺序存储前序遍历
    public void preOrder(int index){
        if(arr == null || arr.length == 0){
            System.err.println("数组为空，不能遍历.");
        }
        System.out.println(arr[index]);
        if((index * 2 + 1) < arr.length){
            preOrder(2 * index + 1);
        }
        if((index * 2 + 2) < arr.length){
            preOrder(2 * index + 2);
        }
    }
}

8.3线索化二叉树

package Tree;
/**
 * 线索化二叉树的实现
 */
public class ThreadBinaryTree {
    public static void main(String[] args) {
        ThreadHeroNode root = new ThreadHeroNode(1, "tom");
        ThreadHeroNode node2 = new ThreadHeroNode(3, "jack");
        ThreadHeroNode node3 = new ThreadHeroNode(6, "smith");
        ThreadHeroNode node4 = new ThreadHeroNode(8, "mary");
        ThreadHeroNode node5 = new ThreadHeroNode(10, "king");
        ThreadHeroNode node6 = new ThreadHeroNode(14, "dim");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadTree tree = new ThreadTree();
        tree.setRoot(root);
        tree.threadNodes();

        ThreadHeroNode leftNode = node5.getLeft();
        System.out.println("10号的前驱节点是：" + leftNode);
        ThreadHeroNode rightNode = node5.getRight();
        System.out.println("10号的后继节点是：" + rightNode);

        System.out.println("使用线索化的方式遍历线索化二叉树");
        tree.threadList();
    }
}

//二叉树
class ThreadTree {
    private ThreadHeroNode root;
    //保存前一个节点
    private ThreadHeroNode pre = null;

    public void setRoot(ThreadHeroNode root) {
        this.root = root;
    }

    public void threadNodes(){
        this.threadNodes(root);
    }
    //中序线索化二叉树
    public void threadNodes(ThreadHeroNode node){
        if(node == null){
            return;
        }
        //1.线索化左子树
        threadNodes(node.getLeft());
        //2.线索化当前节点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //3.线索化右子树
        threadNodes(node.getRight());
    }

    //遍历线索化二叉树
    public void threadList(){
        ThreadHeroNode node = root;
        while(node != null){
            while(node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }
}

//创建HeroNode结点
class ThreadHeroNode {
    private int no;
    private String name;
    private ThreadHeroNode left;
    private ThreadHeroNode right;

    private int leftType;//0表示左子树，1表示前驱节点
    private int rightType;//0表示右子树，1表示后继节点

    public int getLeftType() {
        return leftType;
    }
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
    public int getRightType() {
        return rightType;
    }
    public void setRightType(int rightType) {
        this.rightType = rightType;
    }
    public ThreadHeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public ThreadHeroNode getLeft() {
        return left;
    }
    public void setLeft(ThreadHeroNode left) {
        this.left = left;
    }
    public ThreadHeroNode getRight() {
        return right;
    }
    public void setRight(ThreadHeroNode right) {
        this.right = right;
    }
    
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + "]";
    }
 }

8.4二叉排序树

package Tree;

public class BinarySortTree {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BST bst = new BST();
        for (int i = 0; i < arr.length; i++) {
            bst.add(new BstNode(arr[i]));
        }

        //中序遍历二叉树
        System.out.println("中序遍历二叉树");
        bst.infixOrder();
    }
}

class BST {
    private BstNode root;

    //查找要删除的结点
    public BstNode search(int value) {
        if(root == null) {
            return null;
        }else {
            return root.search(value);
        }
    }

    //查找父节点
    public BstNode searchParent(int value) {
        if(root == null) {
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    //编写方法
    /**
     * 
     * @param node  传入的节点(当做二叉排序树的根节点)
     * @return  返回以Node为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(BstNode node) {
        BstNode 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 {
            BstNode targetNode = search(value);
            //没有找到该节点
            if(targetNode == null) {
                return;
            }
            //没有父节点
            if(root.left == null && root.right == null) {
                root = null;
                return;
            }
            //查找targetNode的父节点
            BstNode parent = searchParent(value);
            //如果要删除的节点是叶子节点
            if(targetNode.left == null && targetNode.right == null) {
                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 minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            }else { // 删除只有一颗子树的节点
                //删除的节点有左子节点
                if(targetNode.left != null) {
                    if(parent!=null){
                        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 add(BstNode node) {
        if(root == null) {
            root = node;
        }else {
            root.add(node);
        }
    }

    //中序遍历
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        }else {
            System.out.println("二叉排序树为空，不能遍历.");
        }
    }
}

class BstNode {
    int value;
    BstNode left;
    BstNode right;
    
    public BstNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "BstNode [value=" + value + "]";
    }

    //添加节点
    public void add(BstNode node) {
        if(node == null) {
            return;
        }
        if(node.value < this.value) {
            if(this.left == null) {
                this.left = node;
            }else {
                this.left.add(node);
            }
        }else {
            if(this.right == null) {
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

    //查找要删除的节点
    public BstNode search(int value) {
        if(value == this.value) {
            return this;
        }else if(value < this.value) {
            if(this.left == null) {
                return null;
            }
            return this.left.search(value);
        }else{
            if(this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找要删除的节点的父节点
    public BstNode searchParent(int value) {
        if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            //当前结点是要删除的结点的父结点，就返回
            return this;
        }else{
            //当前查找的值小于当前结点的值
            if(value < this.value && this.left != null) {
                return this.left.searchParent(value);
            }else if(value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            }else{
                return null;
            } 
        }
    }

}