Datawhale 系列数据结构

这一部分内容大多参考网上前辈的分享，由于，当时没有保存浏览记录，所以找不到链接。如果侵权，联系我删除，或者加您的原帖链接在头部。谢谢！！！

Task5.1树

5.1.1实现一个二叉查找树（支持插入，删除，查找操作）

public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根结点

    @SuppressWarnings("hiding")
    public class BSTNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        BSTNode<T> left;    // 左孩子
        BSTNode<T> right;    // 右孩子
        BSTNode<T> parent;    // 父结点

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public T getKey() {
            return key;
        }

        public String toString() {
            return "key:"+key;
        }
    }

    public BSTree() {
        mRoot=null;
    }

    /*
     * 前序遍历"二叉树"
     */
    private void preOrder(BSTNode<T> tree) {
        if(tree != null) {
            System.out.print(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /*
     * 中序遍历"二叉树"
     */
    private void inOrder(BSTNode<T> tree) {
        if(tree != null) {
            inOrder(tree.left);
            System.out.print(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }


    /*
     * 后序遍历"二叉树"
     */
    private void postOrder(BSTNode<T> tree) {
        if(tree != null)
        {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key+" ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }


    /*
     * (递归实现)查找"二叉树x"中键值为key的节点
     */
    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x==null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }

    public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }

    /*
     * (非递归实现)查找"二叉树x"中键值为key的节点
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (x!=null) {
            int cmp = key.compareTo(x.key);

            if (cmp < 0) 
                x = x.left;
            else if (cmp > 0) 
                x = x.right;
            else
                return x;
        }

        return x;
    }

    public BSTNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /* 
     * 查找最小结点：返回tree为根结点的二叉树的最小结点。
     */
    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.left != null)
            tree = tree.left;
        return tree;
    }

    public T minimum() {
        BSTNode<T> p = minimum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }
     
    /* 
     * 查找最大结点：返回tree为根结点的二叉树的最大结点。
     */
    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.right != null)
            tree = tree.right;
        return tree;
    }

    public T maximum() {
        BSTNode<T> p = maximum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }

    /* 
     * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null)
            return minimum(x.right);

        // 如果x没有右孩子。则x有以下两种可能：
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y!=null) && (x==y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }
     
    /* 
     * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
        if (x.left != null)
            return maximum(x.left);

        // 如果x没有左孩子。则x有以下两种可能：
        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T> y = x.parent;
        while ((y!=null) && (x==y.left)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    /* 
     * 将结点插入到二叉树中
     *
     * 参数说明：
     *     tree 二叉树的
     *     z 插入的结点
     */
    private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;

        // 查找z的插入位置
        while (x != null) {
            y = x;
            cmp = z.key.compareTo(x.key);
            if (cmp < 0)
                x = x.left;
            else
                x = x.right;
        }

        z.parent = y;
        if (y==null)
            bst.mRoot = z;
        else {
            cmp = z.key.compareTo(y.key);
            if (cmp < 0)
                y.left = z;
            else
                y.right = z;
        }
    }

    /* 
     * 新建结点(key)，并将其插入到二叉树中
     *
     * 参数说明：
     *     tree 二叉树的根结点
     *     key 插入结点的键值
     */
    public void insert(T key) {
        BSTNode<T> z=new BSTNode<T>(key,null,null,null);

        // 如果新建结点失败，则返回。
        if (z != null)
            insert(this, z);
    }

    /* 
     * 删除结点(z)，并返回被删除的结点
     *
     * 参数说明：
     *     bst 二叉树
     *     z 删除的结点
     */
    private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x=null;
        BSTNode<T> y=null;

        if ((z.left == null) || (z.right == null) )
            y = z;
        else
            y = successor(z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;

        if (x != null)
            x.parent = y.parent;

        if (y.parent == null)
            bst.mRoot = x;
        else if (y == y.parent.left)
            y.parent.left = x;
        else
            y.parent.right = x;

        if (y != z) 
            z.key = y.key;

        return y;
    }

    /* 
     * 删除结点(z)，并返回被删除的结点
     *
     * 参数说明：
     *     tree 二叉树的根结点
     *     z 删除的结点
     */
    public void remove(T key) {
        BSTNode<T> z, node; 

        if ((z = search(mRoot, key)) != null)
            if ( (node = remove(this, z)) != null)
                node = null;
    }

    /*
     * 销毁二叉树
     */
    private void destroy(BSTNode<T> tree) {
        if (tree==null)
            return ;

        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);

        tree=null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    /*
     * 打印"二叉查找树"
     *
     * key        -- 节点的键值 
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(BSTNode<T> tree, T key, int direction) {

        if(tree != null) {

            if(direction==0)    // tree是根节点
                System.out.printf("%2d is root\n", tree.key);
            else                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

            print(tree.left, tree.key, -1);
            print(tree.right,tree.key,  1);
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }
}

5.1.2 实现查找二叉查找树中某个节点的后继，前驱节点

/**
* 前驱元素
* **/
public BSTreeNode<T> Pred(BSTreeNode<T> node) {
    if (node.left != null) {
        return Max(node.left);
    }
    BSTreeNode<T> parent = node.parent;
    while (parent != null && node != parent.right) {
        node = parent;
        parent = node.parent;
    }
    return parent;
}

/**
* 后继元素
* **/
public BSTreeNode<T> Succ(BSTreeNode<T> node) {
    if (node.right != null) {
        return Min(node.right);
    }
    BSTreeNode<T> parent = node.parent;
    while (parent != null && node != parent.left) {
        node = parent;
        parent = node.parent;
    }
    return parent;
}

5.1.3 实现二叉树前，中，后序以及层次遍历

/*
*在5.1.1中已经实现
*/

5.1.4 练习：翻转二叉树

class Solution{
    public TreeNode invertTree(TreeNode root){
        if(root==null)
            return root;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

5.1.5 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
        
    }

5.1.6 验证二叉查找树

class Solution {
    private TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
       return helper(root);
    }    
    private boolean helper(TreeNode root){
         if(root == null)
            return true;
         if(!helper(root.left))
             return false;
         if(pre != null && pre.val >= root.val)
             return false;
         pre = root;        
         return helper(root.right);
    }
}

TASK5.2 堆

5.2.1 实现一个小顶堆，大顶堆

public class MaxHeap<T extends Comparable<T>> {
    private List<T> mHeap; // 存放元素的动态数组
 
    public MaxHeap() {
        this.mHeap = new ArrayList<>();
    }
    /**
     * 大顶堆的向上调整算法(添加节点的时候调用) 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     * 
     * @param start
     *            -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void filterup(int start) {
 
        int c = start; // 需要调整的节点的初始位置
        int p = (c - 1) / 2; // 当前节点的父节点的位置
        T tmp = mHeap.get(c); // 被调整节点的值
 
        while (c > 0) {
            // 父节点的值和被调整节点的值进行比较
            int cmp = mHeap.get(p).compareTo(tmp);
            if (cmp >= 0) {
                // 父节点大
                break;
            } else {
                // 被调整节点的值大，交换
                mHeap.set(c, mHeap.get(p));
                c = p;
                p = (c - 1) / 2;
            }
        }
        // 找到被调整节点的最终位置了
        mHeap.set(c, tmp);
    }
 
    /**
     * 大顶堆的向下调整算法(删除节点的时候需要调用来调整大顶堆)
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     * 
     * @param start
     *            -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     * @param end
     *            -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void filterdown(int start, int end) {
 
        int c = start; // 被下调节点的初始位置
        int l = 2 * c + 1; // 左孩子节点的位置
        T tmp = mHeap.get(c); // 当前节点的值(大小)
 
        while (l <= end) {
            // 当前节点的左右节点进行比较
            int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
            // 取大的
            if (l < end && cmp < 0) {
                l++;
            }
            // 当前节点和大的那个再比较一下
            cmp = tmp.compareTo(mHeap.get(l));
            if (cmp >= 0) {
                // 当前节点大,不用动
                break;
            } else {
                // 当前节点小,交换
                mHeap.set(c, mHeap.get(l));
                c = l; // 更新当前节点的位置
                l = 2 * c + 1; // 更新当前节点的左孩子位置
            }
        }
        mHeap.set(c, tmp);
    }
 
    /**
     * 向大顶堆中插入新元素
     * 
     * @param data
     */
    public void insert(T data) {
 
        int insertIndex = mHeap.size(); // 获取插入的位置
        // 将新元素插入到数组尾部
        mHeap.add(data);
        // 调用filterup函数，调整大顶堆
        filterup(insertIndex);
    }
    /**
     * 删除大顶堆中的data节点
     * 
     * @param data
     * @return 返回-1表示出错, 返回0表示删除成功
     */
    public int remove(T data) {
 
        // 大顶堆空
        if (mHeap.isEmpty()) {
            return -1;
        }
 
        // 获取data在数组中的索引
        int index = mHeap.indexOf(data);
        if (index == -1) {
            return -1;
        }
 
        // 堆中元素的个数
        int size = mHeap.size();
        // 删除了data元素，需要用最后一个元素填补，然后调用filterdown算法进行调整
        mHeap.set(index, mHeap.get(size - 1)); // 用最后一个元素填补
        mHeap.remove(size - 1); // 删除最后一个元素
 
        if (mHeap.size() > 1 && index < mHeap.size()) {
            // 调整成大顶堆
            filterdown(index, mHeap.size() - 1);
        }
        return 0;
    }
    
    
    @Override
    public String toString() {
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < mHeap.size(); i++) {
            sb.append(mHeap.get(i) + " ");
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        
        int a[] = {10, 40 ,30, 60, 90, 70, 20, 50 ,80};
        
        //大顶堆
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        
        //添加元素
        System.out.println("=== 依次添加元素：");
        for(int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
            maxHeap.insert(a[i]);
        }
        
        //生成的大顶堆
        System.out.println("=== 生成的大顶堆：");
        System.out.println(maxHeap);
        
        //添加新元素85
        int data = 85;
        maxHeap.insert(data);
        System.out.println("=== 添加新元素" + data + "之后的大顶堆：");
        System.out.println(maxHeap);
        
        //删除元素90
        data = 90;
        maxHeap.remove(data);
        System.out.println("=== 删除元素" + data + "之后的大顶堆：");
        System.out.println(maxHeap);
    }
}

5.2.2 实现优先级队列

/**
 * 优先队列类（最大优先队列）
 */
public class PriorityHeap {

    // ------------------------------ Instance Variables

    private int[] arr;
    private int size;

    // ------------------------------ Constructors

    /**
     * 优先队列数组默认大小为64
     */
    public PriorityHeap() {
        this(64);
    }

    public PriorityHeap(int initSize) {
        if (initSize <= 0) {
            initSize = 64;
        }
        this.arr = new int[initSize];
        this.size = 0;
    }

    // ------------------------------ Public methods

    public int max() {
        return this.arr[0];
    }

    public int maxAndRemove() {
        int t = max();

        this.arr[0] = this.arr[--size];
        sink(0, this.arr[0]);
        return t;
    }
    public void add(int data) {
        resize(1);
        this.arr[size++] = data;
        pop(size - 1, data);
    }

    // ------------------------------ Private methods

    /**
     * key下沉方法
     */
    private void sink(int i, int key) {
        while (2 * i <= this.size - 1) {
            int child = 2 * i;
            if (child < this.size - 1 && this.arr[child] < this.arr[child + 1]) {
                child++;
            }
            if (this.arr[i] >= this.arr[child]) {
                break;
            }

            swap(i, child);
            i = child;
        }
    }

    /**
     * key上浮方法
     */
    private void pop(int i, int key) {
        while (i > 0) {
            int parent = i / 2;
            if (this.arr[i] <= this.arr[parent]) {
                break;
            }
            swap(i, parent);
            i = parent;
        }
    }

    /**
     * 重新调整数组大小
     */
    private void resize(int increaseSize) {
        if ((this.size + increaseSize) > this.arr.length) {
            int newSize = (this.size + increaseSize) > 2 * this.arr.length ? (this.size + increaseSize) : 2 * this.arr.length;
            int[] t = this.arr;

            this.arr = Arrays.copyOf(t, newSize);
        }
    }

    /**
     * Swaps arr[a] with arr[b].
     */
    private void swap(int a, int b) {
        int t = this.arr[a];
        this.arr[a] = this.arr[b];
        this.arr[b] = t;
    }
}

5.2.3 实现堆排序

/*堆排序分为三个步骤：
*    创建最大堆
*    确保最大堆中父节点的值比子节点的值都大
*    将根节点与最后一个叶子节点比较，择其大者剔除出堆，再重复第2、3步。
*第二步是整个堆排序的关键。
*/
public static void maxHeapify(int[] array, int heapsize, int i){
    int l = 2*i + 1;
    int r = 2*i + 2;
    int large = i;
    if (l < heapsize && array[i] < array[l]) {
        large = l;
    }else {
        large = i;
    }
    if (r < heapsize && array[large] < array[r]) {
        large = r;
    }
    if (large != i) {
        int temp = array[i];
        array[i] = array[large];
        array[large] = temp;
        //因为将最大值和父节点交换了位置，新的子节点并不能保证一定是比它的子节点大
        //所以需要递归，确定交换的子节点比它的子节点都大
        //而没有动的子节点是不需要进行递归的，因为它的数值没有变，如果之前满足最大堆条件，现在就还是满足的
        maxHeapify(array, heapsize, large);
    }
}
//创建堆
public static void buildMaxHeap(int[] array){
    int heapsize = array.length;
    for (int i = heapsize/2; i >= 0; i--) {
        maxHeapify(array,heapsize,i);
    }
}
public static void heapSort(int[] array){
    int heapsize = array.length;
    for (int i = heapsize - 1; i > 0; i--) {
        if (array[i] < array[0]) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapsize --;
            maxHeapify(array, heapsize, 0);
        }
    }
}

5.2.4 利用有限集队列合并K个有序数组

class Solution {
    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

5.2.5 ：求一组动态数据集合的最大Top K

/*
*不太明白这道题的具体意思，如果是需要求一组数据的Top K,
*那直接，最大堆排序，然后取TopK加入到一个list中返回，就行
*/
 public static void maxHeapify(int[] array, int size, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int small = i;
        if (left < size) {
            if (array[small] > array[left]) {
                small = left;
            }
        }
        if (right < size) {
            if (array[small] > array[right]) {
                small = right;
            }
        }
        if (small != i) {
            int temp = array[small];
            array[small] = array[i];
            array[i] = temp;
            maxHeapify(array, size, small);
        }
    }

    public static void buildHeap(int[] array, int size) {
        for (int i = size - 1; i >= 0; i--) {
            maxHeapify(array, size, i);
        }
    }
    
    public static List findKByHeap(int[] array, int k) {
        buildHeap(array, k);
        for (int i = k + 1; i < array.length; i++) {
            if (array[i] > array[0]) {
                int temp = array[i];
                array[i] = array[0];
                array[0] = temp;
                maxHeapify(array, k, 0);
            }
        }
        List list=new ArrayList();
        for(int i =0;i<k;i++){
            list.add(array[i])
        }
        return list;
    }

5.2.6 练习：路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        
        int t=sum-root.val;
        
       if(root.left==null && root.right==null)
           return t==0 ? true : false;
        
        return hasPathSum(root.left,t) || hasPathSum(root.right,t);
        
    }
}