数据结构基础

准备重新学习一下基础部分的数据结构，这次准备从后往前学

1. 快速排序

import java.util.Arrays;

public class QuickSort{
    public static void quickSort(int[] arr,int left,int right) {
        if(left > right || arr.length < 2)
            return;
        int base = arr[left]; //首先选择左边作为基准数
        int i = left;
        int j = right;

        while(i<j){
            while(i<j && arr[j]>=base) //从右边开始，在右面找到比基准数小的就停下
                j--;
            while(i<j && arr[i]<=base) //再从左边找，在左面找到比基准数大的就停下
                i++;
            swap(arr,i,j); //交换这两个值
            //然后继续找，直到i和j相遇
        }
        swap(arr,left,i); //交换base与相遇的位置（i=j）的值
        //交换后以新base为中间值，划分成两个数组。新base左边<=base；新base右边>=base；
        quickSort(arr, left, i-1); //左右两边分别递归
        quickSort(arr, i+1, right); //重复这个过程
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //for test
    public static void main(String[] args) {
        int[] arr = {5,3,4,6,2,8,1,9,7};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}

2. 堆排序

import java.util.Arrays;

public class HeapSort{

    /**
     * parent = (i-1)/2
     * c1 = 2*i+1
     * c2 = 2*i+2
     * 
     * @param tree 排序数组，表示堆
     * @param n 堆的节点数
     * @param i 操作的节点编号
     */
    private static void heapify(int[] tree,int n,int i){
        if(i >= n){
            return;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if(c1 < n && tree[c1] > tree[max])
            max = c1;
        if(c2 < n && tree[c2] > tree[max])
            max = c2;
        if(max != i){
            swap(tree,max,i);
            heapify(tree, n, max); //调整完上层节点，下层堆顺序肯定也要变啊，所以还得重新调整
        }
    }

    /**
     * 从最后一个结点的父节点开始，自下而上构建堆
     * @param tree
     * @param n
     */
    private static void buildHeap(int[] tree,int n){
        int last_node = n - 1;
        int parent = (last_node - 1)/2;
        for (int i = parent; i >= 0; i--) {
            heapify(tree, n, i); 
        }
    }

    /**
     * 每次都用第一个结点（最大值）和最后一个结点交换，
     * 然后去掉交换后的最后一个结点（最大值），重新构建大顶堆，再与新堆的最后一个交换
     * @param tree
     * @param n
     */
    public static void heapSort(int[] tree,int n){
        buildHeap(tree, n);
        for (int i = n - 1; i >= 0 ; i--) {
            swap(tree, i, 0);
            heapify(tree, i, 0); //这里设计成i，因为i一直在递减，就相当于砍掉了最后一个结点（即交换后的结点）
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //for test
    public static void main(String[] args) {
        // int[] tree = {4,10,3,5,1,2};
        int[] tree = {4,10,2,5,1,3};

        // int[] tree = {2,5,3,1,10,4,8,6,7,9};
        // heapify(tree, tree.length, 0);
        // buildHeap(tree, tree.length);
        heapSort(tree, tree.length);
        System.out.println(Arrays.toString(tree));    
    }
}

3.二叉树的遍历

import java.util.Stack;

public class BinaryTree{
    //递归遍历
    //先序
    public static void preOrder(Node head){
        if(head != null){
            System.out.print(head.value + " ");
            preOrder(head.left);
            preOrder(head.right);
        }
    }
    //后序
    public static void postOrder(Node head){
        if(head != null){
            postOrder(head.left);
            postOrder(head.right);
            System.out.print(head.value + " ");
        }
    }
    //中序
    public static void inOrder(Node head){
        if(head != null){
            inOrder(head.left);
            System.out.print(head.value + " ");
            inOrder(head.right);
        }
    }

    //非递归遍历
    //先序
    public static void preOrderUnRecrsion(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while(!stack.isEmpty()){
                head = stack.pop();
                System.out.print(head.value + " ");
                if(head.right != null){
                    stack.push(head.right);
                }
                if(head.left != null){
                    stack.push(head.left);
                }
            }
        }
    }
    //后序
    public static void postOrderUnRecrsion(Node head){
        if(head != null){
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(head);
            while(!s1.isEmpty()){
                head = s1.pop();
                s2.push(head);
                if(head.left != null){
                    s1.push(head.left);
                }
                if(head.right != null){
                    s1.push(head.right);
                }
            }
            while(!s2.isEmpty()){
                System.out.print(s2.pop().value + " ");
            }
        }
    }
    //中序
    public static void inOrderUnRecrsion(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
    }


    //for test
    /**
     * 构建二叉树
     *         1
     *      2      3
     *   4    5  6    7
     */
    public static Node createBinaryTree(){
        Node nodeA = new Node(1);
        Node nodeB = new Node(2);
        Node nodeC = new Node(3);
        Node nodeD = new Node(4);
        Node nodeE = new Node(5);
        Node nodeF = new Node(6);
        Node nodeG = new Node(7);

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;

        return nodeA;
    }

    //for test
    public static void main(String[] args) {
        Node head = createBinaryTree();

        System.out.print("递归遍历,先序：");
        preOrder(head);
        System.out.println();
        System.out.print("递归遍历,中序：");
        inOrder(head);
        System.out.println();
        System.out.print("递归遍历,后序：");
        postOrder(head);
        System.out.println();
        System.out.print("非递归遍历,先序：");
        preOrderUnRecrsion(head);
        System.out.println();
        System.out.print("非递归遍历,中序：");
        inOrderUnRecrsion(head);
        System.out.println();
        System.out.print("非递归遍历,后序：");
        postOrderUnRecrsion(head);
        System.out.println();
    }
}

class Node{
    public int value;
    public Node left;
    public Node right;

    public Node(int data){
        this.value = data;
    }
}