基础算法(图与树）

1、快速排序
最快时间复杂度为O(nlogn)

public class QuickSort {
    public static void quickSort(int a[], int l, int r) {
        if(l>r) {
            return;
        }
        int i = l; int j = r; int key = a[l];
        while (i < j) {
            while (i key) 
                j--;
            if(i<j) {
                a[i] = a[j];
                i++;
            }
            while(i<j && a[i] < key)
                i++;
            if(i<j) {
                a[j] = a[i];
                j--;
            }
        }
        a[i] = key;
        quickSort(a,i+1,r);
        quickSort(a,l,i-1);
    }
}

2、堆排序

public class HeaoSort {
    public static int[] heapSort(int[] arr) {
        // 调整堆要从最后一个非叶子节点开始
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //交换，再调整
        for (int i = arr.length-1; i > 0 ; i++) {
            swap(arr, 0, i); // 每次都交换二叉树的最后一个元素和第一个元素。保持二叉树最后一个元素为当前排序的最大值
            adjustHeap(arr, 0, i); // 交换之后进行从上往下依次调整
        }
        return arr;
    }
    // 交换元素
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    // 从上往下依次调整
    private static void adjustHeap(int[] arr, int i, int length) { 
        int temp = arr[i];
        for (int j = i*2+1; j < length; j = j*2+1) {
            if(j+1 < length && arr[j] < arr[j+1]){ // j始终指向较大的那个子节点
                j++;
            }
            if(arr[j] > temp) { // 子节点比父节点大，则交换
                arr[i] = arr[j];
                i = j; 
            } else {
                break; // 直到满足父节点大于子节点的状态，则跳出循环
            }
        }
        arr[i] = temp; 
    }
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

3、冒泡排序

public class BubbleSort {
    public static void main(String[] args) {
      int[] arr =  bubblesort(new int[]{9,6,2,3,4,1,5,0,7,8});
      for (Integer i: arr) {
          System.out.print(i + " ");
      }
    }
    public static int[] bubblesort(int[] arr) {
        int temp;
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 0; j < arr.length-i; j++) {
                if(arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
}

4、插入排序

public class InsertSort {
    public static void main(String[] args) {
       int[] arr = insertsort(new int[]{9,3,2,4,5,1,6,8,0,7});
        for (Integer i: arr) {
            System.out.println(i);
        }
    }
    public static int[] insertsort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        return arr;
    }
}

5、归并排序

public class MergeSort {
    public static void merge(int[] a, int left, int mid, int right) {
        int[] result = new int[a.length];
        int i = left, p1 = left, p2 = right;
        while(left = mid) {
            result[i++] = a[left] <= a[right] ? a[left++] : a[right--];
        }
        while(left <= mid) result[i++] = a[left++];
        while(right >= mid) result[i++] = a[right--];
        for (int j = p1; j <= p2; j++) {
            a[j] = result[j];
        }
    }
    public static void mergeSort(int[] a, int start, int end) {
        if(start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);
            mergeSort(a, mid+1, end);
            merge(a, start, mid, end);
        }
    }
    public static void main(String[] args) {
        int[] a = new int[]{8,4,5,6,2,3,1,7,9};
        mergeSort(a, 0, a.length);
        for (int e : a) {
            System.out.print(e + " ");
        }
    }
}

6、二叉树递归先序遍历

 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }

 public void PreorderRaversal(TreeNode node) {
        System.out.println(node.val);
        PreorderRaversal(node.left);
        PreorderRaversal(node.right);
    }

7、二叉树非递归先序遍历

 public void nonPreorderRaverersalRecursion(TreeNode node) {
        Stack stack = new Stack();
        TreeNode T = node;
        while(T != null || !stack.empty()) {
            while (T != null) {
                System.out.println(T.val);
                stack.push(T);
                T = T.left;
            }
            if(!stack.empty()) {
                T = stack.pop();
                T = T.right;
            }
        }
    }

8、二叉树递归中序遍历

 public void PreorderRaversal(TreeNode node) {
        PreorderRaversal(node.left);
        System.out.println(node.val);
        PreorderRaversal(node.right);
    }

9、二叉树非递归中序遍历

public void nonInorderTraversalRecursion(TreeNode node) {
        Stack stack = new Stack();
        TreeNode T = node;
        while(T != null || !stack.empty()) {
            while (T != null) {
                stack.push(T);
                T = T.left;
            }
            if(!stack.empty()) {
                T = stack.pop();
                System.out.println(T.val);
                T = T.right;
            }
        }
    }

10、二叉树递归后序遍历

public void PreorderRaversal(TreeNode node) {
        PreorderRaversal(node.right);
        PreorderRaversal(node.left);
        System.out.println(node.val);
    }

11、二叉树非递归后续遍历

 public void nonPostorderraversalRecursion(TreeNode node) {
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        TreeNode T = node;
        while(T != null || !stack1.empty()) {
            while (T != null) {
                stack2.push(T);
                stack1.push(T);
                T = T.right;
            }
            if(!stack1.empty()) {
                T = stack1.pop();
                T = T.left;
            }
        }
        while (!stack1.empty()) {
            T = stack1.pop();
            System.out.println(T.val);
        }
    }

12、二叉树层数遍历

public class LayerTraversal {
    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1, node3, node4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node = new TreeNode(0, node1, node2);
        layerTraversal(node);
    }
    public static void layerTraversal(TreeNode node) {
        Queue queue = new LinkedList();
        if (node != null) {
            queue.add(node);
            while(!queue.isEmpty()) {
                TreeNode temp = queue.poll();
                System.out.println(temp.val);
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
            }
        }
    }
}

13、二叉树深度优先搜索（先序遍历）
14、二叉树广度优先搜素（层次遍历）
15、求二叉树的高度 ；

public class GetHigh {
    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3, node5, node6);
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1, node3, node4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node = new TreeNode(0, node1, node2);
        System.out.println(gethigh(node));
    }
    public static int gethigh(TreeNode node) {
        if (node != null) {
            return gethigh(node.left) > gethigh(node.right) ? gethigh(node.left) + 1: gethigh(node.right) + 1;
        } else {
            return 0;
        }
    }
}

16、求二叉树的叶子节点的个数 ；

public class NumberOfLeafNodes {
    public static void main(String[] args) {
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6, node7, node8);
        TreeNode node3 = new TreeNode(3, node5, node6);
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1, node3, node4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node = new TreeNode(0, node1, node2);
        int number = getNumberOfLeafNodes(node);
        System.out.println(number);
    }
    private static int flag = 0;
    public static int getNumberOfLeafNodes(TreeNode node) {
        if(node != null) {
            if(node.left == null && node.right == null)  flag++;
            getNumberOfLeafNodes(node.left);
            getNumberOfLeafNodes(node.right);
        }
        return flag;
    }
}

17、求二叉树第k层的节点个数 ；

public class NumberOfKLayerNode {
    public static int numberOfKLayerNode(TreeNode node, int k) {
        if(node == null || k < 0) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        int left = numberOfKLayerNode(node.left, k-1);
        int right = numberOfKLayerNode(node.right, k-1);
        return left + right;
    }
}

18、判断一个节点是否在一棵二叉树中 ；

 public static boolean judgeNode(TreeNode node, TreeNode temp) {
        if(node == null || temp == null) return false;
        if(node == temp) return true;
        return judgeNode(node.left, temp) || judgeNode(node.right, temp);
    }

19、求二叉树的镜像；

  public static void binaryTreeImage(TreeNode node) {
        if(node != null) {
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            binaryTreeImage(node.left);
            binaryTreeImage(node.right);
        }
    }

20、判断两颗二叉树是否相等；

 public static boolean binaryTreeIsSame(TreeNode node1, TreeNode node2) {
        if(node1 != null && node2 != null) {
           if(node1 == node2) {
               return true;
           } else {
               return false;
           }
        }
        return binaryTreeIsSame(node1.left, node2.left) && binaryTreeIsSame(node1.right, node2.right);
    }

21、从二叉树中查找结点

public class FindNode {
    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node3 = new TreeNode(3, node5, node6);
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1, node3, node4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node = new TreeNode(0, node1, node2);
        TreeNode temp = findNode(node, 2);
        System.out.println(temp.val);
    }
    public static TreeNode findNode(TreeNode node, int aim) {
        TreeNode value = null;
        if(node != null) {
            if (node.val == aim) {
                value = node;
            } else {
                if(value == null) {
                    value = findNode(node.left, aim);
                }
                if(value == null) {
                    value = findNode(node.right, aim);
                }
            }
        }
        return value;
    }
}

22、构建二叉树

 public static TreeNode createTree(int[] aim) {
        TreeNode node = new TreeNode(aim[0]);
        Queue queue = new LinkedList();
        queue.add(node);
        for (int i = 1; i < aim.length-1; i++) {
            if(!queue.isEmpty()) {
                TreeNode temp = queue.poll();
                TreeNode left = new TreeNode(aim[i]);
                TreeNode right = new TreeNode(aim[++i]);
                temp.left = left;
                temp.right = right;
                queue.add(left);
                queue.add(right);
            }
        }
        return node;
    }

23、kruskal算法求最小生成树
24、prim算法求最小生成树
25、检查一颗二叉树是否平衡

public class IsBalanceTree {
    public static void main(String[] args) {
        TreeNode node4 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2, node3, null);
        TreeNode node1 = new TreeNode(1,node2,node4);
        TreeNode root = new TreeNode(0, node1, null);

        IsBalanceTree isBalanceTree = new IsBalanceTree();
        Boolean bool = isBalanceTree.isBalanceTree(root);
        System.out.println(root.val);
        System.out.println(bool);
    }

    // 左右节点的高度不超过1
    public int calculate(TreeNode root, int tap) {
        if(root == null) return 0;
        int left = calculate(root.left, tap);
        int right = calculate(root.right, tap);
        tap = left >= right ? left - right : right - left;
        root.val = tap;
        return left > right? left + 1 : right +1;
    }

    public boolean isBalanceTree(TreeNode node) {
        if(node == null) return true;
        isBalanceTree(node.left);
        isBalanceTree(node.right);
        calculate(node, 0);
       return node.val > 1 ? false : true;
    }
}

26、图的遍历

有圈的是图，边没有指向性的图叫做无向图，边具有指向性的图叫做有向图，没有圈的连接图叫做树，没有圈的非连接图叫做森林。
图可以分为有向图和无向图，一般用G=(V,E)来表示图。经常用邻接矩阵或者邻接表来描述一副图。
图的遍历可分为广度优先搜索（BFS）和深度优先搜索（DFS）。

1）邻接表的定义

// 简单的无向图节点表示
// 邻接表
public class GraphNode<T> {
    T data;
    List<GraphNode<T>> neighborList;
    boolean visited;

    public GraphNode(T data) {
        this.data = data;
        neighborList = new ArrayList<GraphNode<T>>();
        visited = false;
    }

    public boolean equals(GraphNode<T> node){
        return this.data.equals(node.data);
    }

    public void restoreVisited() {
        restoreVisited(this);
    }

    private void restoreVisited(GraphNode<T> node) {
        if(node.visited) {
            node.visited = false;
        }

        List<GraphNode<T>> neighbors = node.neighborList;
        for (int i = 0; i < neighbors.size(); i++) {
            restoreVisited(neighbors.get(i));
        }
    }
}

2）邻接表实现图的深度优先遍历和广度优先遍历

package leetcode.graph;

import java.util.*;

public class SearchGraph<T> {
    StringBuffer  searchDFS = new StringBuffer();
    StringBuffer searchBFS = new StringBuffer();

    // 深度优先遍历
    public void searchDFS(GraphNode<T> root) {
        if(root == null)
            return;

        if(searchDFS.length() > 0) {
            searchDFS.append("->");
        }
        root.visited = true;
        searchDFS.append(root.data.toString());

        for (GraphNode<T> node : root.neighborList) {
            if(!node.visited) {
                searchDFS(node);
            }
        }
    }

    // 广度优先遍历
    public void setSearchBFS(GraphNode<T> root) {
        Queue queue = new LinkedList();
        queue.add(root);
        searchBFS.append(root.data.toString());
        while(!queue.isEmpty()) {
            GraphNode<T> node = (GraphNode<T>) queue.poll();
            for (GraphNode<T> elem : node.neighborList) {
                    if(!elem.visited) {
                        searchBFS.append("->");
                        searchBFS.append(elem.data.toString());
                        elem.visited = true;
                        queue.add(elem);
                    }
            }
        }
    }

    // 创建邻接表
    public GraphNode setup() {
        GraphNode root = new GraphNode(0);
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);
        GraphNode node5 = new GraphNode(5);

        List<GraphNode> neighborList = Arrays.asList(node1, node2, node3, node4);
        root.neighborList = neighborList;
        List<GraphNode> neighborList2 = Arrays.asList(node4, node5);
        node1.neighborList = neighborList2;
        List<GraphNode> neighborList3 = Arrays.asList(node1, node4);
        node3.neighborList = neighborList3;
        return root;
    }

    public static void main(String[] args) {
        SearchGraph searchGraph = new SearchGraph();
        GraphNode root = searchGraph.setup();
        searchGraph.searchDFS(root);
        System.out.println(searchGraph.searchDFS);
        GraphNode root1 = searchGraph.setup();
        searchGraph.setSearchBFS(root1);
        System.out.println(searchGraph.searchBFS);
    }
}

3） 邻接矩阵的定义

// 邻接矩阵表示法
public class MGraph {
    int vexs; // 图中的节点数
    char data[]; // 存放节点数据
    int[][] weight; // 存放边
    boolean[] visit; // 记录节点是否访问过

    public MGraph(int vexs) {
        this.vexs = vexs;
        this.data = new char[vexs];
        this.weight = new int[vexs][vexs];
    }
}

4） 邻接矩阵实现图的深度优先遍历和广度优先遍历

public class GraphMetrix {
    //  创建图的邻接矩阵
    public void CreateGraph(MGraph graph, int vexs, char data[], int[][] weight){
        graph.visit = new boolean[vexs];
        for (int i = 0; i < vexs; i++) {
            graph.data[i] = data[i];
            graph.visit[i] = false;
            for (int j = 0; j < vexs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    //获取当前节点K的第一个邻接顶点的位置
    public int GetFirst(MGraph graph, int k) {
        if(k < 0 || k > graph.vexs -1) {
            return -1;
        }
        for (int i = 0; i < graph.vexs; i++) {
            if(graph.weight[k][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    // 获取当前节点K的第t个邻接顶点下一个邻接顶点的位置
    public int GetNext(MGraph graph, int k, int t) {
        if(k < 0 || k > graph.vexs - 1 || t < 0 || t > graph.vexs -1) {
            return -1;
        }
        for (int i = t+1; i < graph.vexs; i++) {
            if(graph.weight[k][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    // 递归方式深度遍历图的邻接矩阵, k表示图的起始点
    public void DFSGraph(MGraph graph, int k) {
        graph.visit[k] = true;
        System.out.print(graph.data[k] + " ");
        int u = GetFirst(graph, k);
        while(u != -1) {
            if(graph.visit[u] == false) {
                DFSGraph(graph, u);
            }
            u = GetNext(graph, k, u);
        }
    }

    // 递归方式广度优先遍历邻接矩阵
    public void BFSGraph(MGraph graph, int k) {
        Queue<Integer> queue = new LinkedList();
        if(graph.visit[k] == false) {
            graph.visit[k] = true;
            queue.add(k);
        }
        while(!queue.isEmpty()) {
            k = queue.poll();
            System.out.print(graph.data[k] + " ");
            int u = GetFirst(graph, k);
            while(u != -1) {
                if(graph.visit[u] == false) {
                    graph.visit[u] = true;
                    queue.add(u);
                }
                u = GetNext(graph, k, u);
            }
        }
    }

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E'};
        int vexs = data.length;
        int[][] weight = new int[][] {
                {0,1,0,0,1},
                {1,0,1,1,0},
                {0,1,0,0,0},
                {0,1,0,0,1},
                {1,0,0,1,0}
        };

        MGraph graph = new MGraph(vexs);
        GraphMetrix graphMetrix = new GraphMetrix();
        graphMetrix.CreateGraph(graph, vexs, data, weight);
        graphMetrix.DFSGraph(graph, 0);
        graphMetrix.BFSGraph(graph, 0);
    }
}

27、dijkstra求最短路径
28、floyd求最短路径