第二周 2020 年 10 月 26 ~ 2020 年 11 月 01

Algorithm/Tip:

二叉树的递归相对很容易，而迭代就有些复杂。本周主要针对对二叉树迭代遍历的联系。
在二叉树迭代遍历时，一般都会用 栈 ，用来存放二叉树的节点。

前序遍历

关于前序遍历，目前接触到的方式有以下两种。都是通过栈来存放二叉树的节点。

void preorder(TreeNode root){
    if(root == null){
        return;
    }
    // 存放二叉树的节点
    Deque<TreeNode> stack = new LinkList<>();
    // 记录当前的节点
    TreeNode node = root;
    while(!stack.isEmpty() || node != null){
        // 一直遍历左子树，直到左子树为空
        while(node != null){
            // 第一个节点是 root 节点
            System.out.println("node = " + node.val);
            // 将当前节点存入 stack 
            stack.push(node);
            // 接下来才是 root 节点的左子树
            node = node.left;
        }
        // 这时所有的左子树都已经存入 stack 中
        // 左子树遍历完毕之后，后去栈顶节点，即记录的当前节点，然后开始后去其右节点，开始遍历右节点
        node = stack.pop();
        node = node.right;
    }
}

Review/Share

JVM Spec Chapter 2.1 ~ 2.4

JVM 的结构

想要实现一个 JVM，只需要能正确读取并执行 class 文件的一些指令。所以想要了解 JVM 的结构，只需要了解 class 的文件的结构就可以了。

class 文件格式

JVM 执行的 class 文件，是可以独立于硬件和系统的。
class 文件格式，包含了定义了类或者接口的具体信息，包含特定平台字节序列和对象文件格式。

数据类型

JVM 支持两种数据类型：基本数据类型和引用数据类型。它们存储在变量，作为的参数传递，作为方法的返回值。
JVM 希望在运行前就进行所有的类型检查。类型检查一般是由编译器完成的，而不是由 JVM 完成的。在运行时基本数据类型的值不需要标记，不需要进行检查，也不需要与引用数据类型进行区分。JVM 有一系列的指令集，来区分不同的数据类型；每个数据类型都有特定的操作指令。
JVM 支持显示的对象类型。对象可以动态的分配类的实例，或者数组。对象的引用一般也被认为是 JVM 的引用类型，引用类型的值可以看做是指向对象的指针。一个对象可能存在多个引用。对象可以通过引用类型操作、传递和测试引用类型的值。

基本数据类型和取值

JVM 支持的基本数类型包含数字类型、boolean 和 returnAddress 类型。
数字类型包含整形和浮点型。
整形：

• byte：8 位带符号的二进制整形补码；默认值 0；[-2~ 2-1]
• short：16 位带符号的二进制整形补码；默认值 0； [-2 to 2 - 1]
• int：32 位带符号的二进制整形补码；默认值 0；[-2 to 2 - 1]
• long：64 位带符号二进制整形补码；默认值 0； [-2 to 2 - 1]
• char：16 位无符号整形；表示基本多语言平面中的 Unicode 码位；UTF-16 编码，默认值 ‘\u0000’ ; [0 ~ 65535]

浮点型：

• float：单精度浮点数占用 4 个字节，32 位，存储遵循了 IEEE754 标准；默认值 0.0F;
• double：双精度浮点数占用 8 个字节，64位，存储遵循了 IEEE754 标准；默认值 0.0D。

boolean 型：
boolean 只有两个值，true 和 false 。JVM 中没有专门用于 boolean 类型的指令，在 Java 中编译器会将 boolean 类型编译为 int 类型相关的表达式。JVM 不直接支持 boolean 数组，而且是将 boolean 属组编译成 byte 数组，使用 0 表示 false，1表示 true。
returnAddress：
returnAddress 类型是指向 JVM 的指令操作码中的指针。在基本类型中，只有 returnAddress 类型与 Java 语言类型没有直接的关联。JVM 的指令 jsr、 ret 、 jsr_w 就会使用到 returnAddress 。

引用类型和取值

引用类型包含三种形式： 类，数组和接口。引用类型的值时 动态创建的类实例，数组或者实现了接口的类实例或数组。
数组的每个元素必须是同类型的，其中元素可以基本数据类型，类，接口，也可以是数组。
引用类型也可以是特殊的 null 引用，即没有任何对象。引用类型的默认值就是 null。