Data Structure

前言

慕课网刘宇波数据结构课程简记

课程：《玩转数据结构》

问题一：循环队列

一般认为，从队尾添加元素，从队首取出元素（FIFO）。

如下图：

空队列：front == tail

问题在于下面这种情况，tail需要处理

处理方式：tail = (tail + 1) % capacity

达成目标，这时，注意到队列中有一个空位置，这是特意“浪费”一个位置用来标识队列满。
队列满条件：(tail + 1) % capacity = front

问题二：递归

代码示例：

public class SumRecusion {

    // 暴露给用户调用的和函数
    public static int sum(int[] arr) {
        return sum(arr, 0);
    }

    // 真正调用的递归求和的和函数
    // 功能为计算arr[l ... n]范围内的数字和
    private static int sum(int[] arr, int l) {
        // 求解最基本的问题
        if (l == arr.length)
            return 0;
        // 把原问题转化为更小的问题
        // 调用sum函数理解为一个和完成指定功能的子函数的调用
        return arr[l] + sum(arr, l + 1);
    }
}

链表和递归

问题示例：递归删除链表中某个元素值

代码示例：

public class RecursionRemoveElement {
    
    public ListNode removeElements(ListNode head, int val){
        if(head == null)
            return null;

        /* 基本版
        ListNode res = removeElements(head.next, val);
        if(head.val == val)
            return res;
        else{
            head.next = res;
            return head;
        }
        */

        // 精简版
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

微观分析

问题三：二叉树

构建一个二叉树：（4个类试验一下）

TreeNode Class节点：

package playwithdatastructure.f_binary_search_tree.TreeDemo;

/**
 * @description:
 * @author: zw
 * @createDate: 2020/3/21
 * @version: 1.0.0
 */
public class TreeNode {
    Integer val;
    TreeNode left;
    TreeNode right;
    public TreeNode(){}
    public TreeNode(Integer val){
        this.val = val;
    }
    public TreeNode(Integer val, TreeNode left, TreeNode right){
        super();
        this.left = left;
        this.right = right;
        this.val = val;
    }
}

BinaryTree Interface 接口

package playwithdatastructure.f_binary_search_tree.TreeDemo;

/**
 * @description:
 * @author: zw
 * @createDate: 2020/3/21
 * @version: 1.0.0
 */
public interface BinaryTree {
    public int size();
    public boolean isEmpty();
    public int getHeight();
    public void preOrderTraversal();
    public void inOrderTraversal();
    public void postOrderTraversal();
    public void levelOrderTraversal();
    public void preOrderTraversalNR();
    public void inOrderTraversalNR();
    public void postOrderTraversalNR();
}

BinaryTreeImpl 二叉树实现

package playwithdatastructure.f_binary_search_tree.TreeDemo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @description:
 * @author: zw
 * @createDate: 2020/3/21
 * @version: 1.0.0
 */
public class BinaryTreeImpl implements BinaryTree {
    private TreeNode root;

    public BinaryTreeImpl(){}
    public BinaryTreeImpl(TreeNode root){
        super();
        this.root = root;
    }


    /* @description 暴露二叉树节点数函数
     * @param
     * @return int
     * @info zw 2020/3/21 21:45
     */
    @Override
    public int size() {
        return this.getSize(root);
    }
    // 递归具体实现获取size
    private int getSize(TreeNode node){
        if(node == null)
            return 0;
        int leftSize = getSize(node.left);
        int rightSize = getSize(node.right);
        return leftSize + rightSize + 1;
    }

    /* @description 暴露判空函数
     * @param
     * @return boolean
     * @info zw 2020/3/21 21:48
     */
    @Override
    public boolean isEmpty() {
        return root == null;
    }

    /* @description 暴露获取二叉树高度函数
     * @param
     * @return int
     * @info zw 2020/3/21 21:49
     */
    @Override
    public int getHeight() {
        return this.getHeight(root);
    }
    // 递归实现获取二叉树高度
    private int getHeight(TreeNode node){
        if(node == null)
            return 0;
        int leftHeight = getHeight(node.left) + 1;
        int rightHeight = getHeight(node.right) + 1;
        return leftHeight > rightHeight ? leftHeight : rightHeight;
    }

    /* @description 递归获取二叉树前序遍历
     * @param
     * @return void
     * @info zw 2020/3/21 21:50
     */
    @Override
    public void preOrderTraversal() {
        if(root == null)
            System.out.println("此为空树");
        System.out.println("二叉树递归前序遍历");
        this.preOrder(root);
        System.out.println();
    }
    // 二叉树前序遍历具体实现
    private void preOrder(TreeNode node){
        if(node == null)
            return;
        System.out.print(node.val + "->");
        preOrder(node.left);
        preOrder(node.right);
    }

    /* @description 暴露二叉树中序遍历函数
     * @param
     * @return void
     * @info zw 2020/3/21 21:50
     */
    @Override
    public void inOrderTraversal() {
        if(root == null)
            System.out.println("此为空树");
        System.out.println("二叉树递归中序遍历");
        inOrder(root);
        System.out.println();
    }
    // 递归中序遍历
    private void inOrder(TreeNode node){
        if(node == null)
            return;
        inOrder(node.left);
        System.out.print(node.val + "->");
        inOrder(node.right);
    }

    /* @description 暴露二叉树后序遍历
     * @param
     * @return void
     * @info zw 2020/3/21 21:54
     */
    @Override
    public void postOrderTraversal() {
        if(root == null)
            System.out.println("此为空树");
        System.out.println("二叉树递归后序遍历");
        postOrder(root);
        System.out.println();
    }
    // 递归后序遍历
    private void postOrder(TreeNode node){
        if(node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + "->");
    }

    /* @description 二叉树层次遍历（广度优先遍历）
     * @param
     * @return void
     * @info zw 2020/3/21 22:00
     */
    @Override
    public void levelOrderTraversal() {
        System.out.println("二叉树层次遍历：");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            System.out.print(curNode.val + "->");
            if(curNode.left != null)
                queue.add(curNode.left);
            if(curNode.right != null)
                queue.add(curNode.right);
        }
        System.out.println();
    }

    /* @description 先序遍历非递归实现，可以发现广度优先遍历和非递归前序遍历只有
     * 辅助工具不同，一个用队列，一个用栈
     * @param
     * @return void
     * @info zw 2020/3/21 22:15
     */
    @Override
    public void preOrderTraversalNR() {
        if(root == null)
            System.out.println("此为空树");
        System.out.println("非递归实现前序遍历");
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode curNode = stack.pop();
            System.out.print(curNode.val + "->");
            if(curNode.right != null)
                stack.push(curNode.right);
            if(curNode.left != null)
                stack.push(curNode.left);
        }
        System.out.println();
    }

    /* @description 中序遍历非递归实现
     * @param
     * @return void
     * @info zw 2020/3/21 22:27
     */
    @Override
    public void inOrderTraversalNR() {
        if(root == null)
            System.out.println("此为空树");
        System.out.println("非递归实现中序遍历");
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;

        while(!stack.empty() || curNode !=null){
            while(curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            System.out.print(curNode.val + "->");
            curNode = curNode.right;
        }
        System.out.println();
    }

    /* @description 后序遍历非递归实现
     * @param
     * @return void
     * @info zw 2020/3/21 22:34
     */
    @Override
    public void postOrderTraversalNR() {
    // TODO: 2020/3/21
    }
}

BinaryTreeTest 测试

package playwithdatastructure.f_binary_search_tree.TreeDemo;

/**
 * @description:
 * @author: zw
 * @createDate: 2020/3/21
 * @version: 1.0.0
 */
public class BinaryTreeTest {
    public static void main(String[] args) {
        //创建一棵基本的二叉树
        TreeNode node7  = new TreeNode(7, null, null);
        TreeNode node6  = new TreeNode(6, null, null);
        TreeNode node3  = new TreeNode(3, null, null);
        TreeNode node5  = new TreeNode(5, node6, node7);
        TreeNode node2  = new TreeNode(2, node3, node5);
        TreeNode node8  = new TreeNode(8, null, null);
        TreeNode node11 = new TreeNode(11, null, null);
        TreeNode node12 = new TreeNode(12, null, null);
        TreeNode node10 = new TreeNode(10, node11, node12);
        TreeNode node9  = new TreeNode(9, node10, null);
        TreeNode node4  = new TreeNode(4, node8, node9);

        TreeNode root  = new TreeNode(1, node4, node2);
        BinaryTreeImpl link = new BinaryTreeImpl(root);

        //查看树是否为空
        System.out.println(link.isEmpty());

        //前序递归遍历
        link.preOrderTraversal();

        //中序递归遍历
        link.inOrderTraversal();

        //后序递归遍历
        link.postOrderTraversal();

        //计算结点的个数
        int size = link.size();
        System.out.println("个数是："+size);
        //得到树的高度
        int height = link.getHeight();
        System.out.println("树的高度是："+height);
        //借助队列实现层次遍历
        link.levelOrderTraversal();

        //借助栈实现先序遍历
        link.preOrderTraversalNR();

        //借助栈实现中序遍历，不采用递归
        link.inOrderTraversalNR();
    }
}

二叉树中序遍历

给定一个二叉树，返回它的中序遍历。

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

迭代：

递归：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new List<>();
        if(root == null)
            return;
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);
        return res;
    }
}