C语言反汇编05：二叉树先序遍历

二叉树先序遍历的实现思想是：

1. 访问根节点；
2. 访问当前节点的左子树；
3. 若当前节点无左子树，则访问当前节点的右子树；

希望输出的结果：1 2 4 5 3 6 7

#1 程序源代码
#2 经典代码段反汇编分析

#1 程序源代码

#include <corecrt_malloc.h>
#include <stdio.h>

#define ElemType int

// typedef struct定义结构体并且别名
typedef struct BiNode {
    ElemType data;
    BiNode* lchild; // 左右子节点也是一样的结构体类型
    BiNode* rchild;
} *BiTree;

void CreateTree(BiTree* T)
{
    //BiNode是类型，而*BiTree是变量
    //申请一个BiNode的内存空间，将空间给*T用
    *T = (BiNode*)malloc(sizeof(BiNode)); 
    (*T)->data = 1;

    (*T)->lchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->lchild->data = 2;

    (*T)->rchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->rchild->data = 3;

    (*T)->lchild->lchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->lchild->lchild->data = 4;
    (*T)->lchild->lchild->lchild = nullptr;
    (*T)->lchild->lchild->rchild = nullptr;

    (*T)->lchild->rchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->lchild->rchild->data = 5;
    (*T)->lchild->rchild->lchild = nullptr;
    (*T)->lchild->rchild->rchild = nullptr;

    (*T)->rchild->lchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->rchild->lchild->data = 6;
    (*T)->rchild->lchild->lchild = nullptr;
    (*T)->rchild->lchild->rchild = nullptr;

    (*T)->rchild->rchild = (BiNode*)malloc(sizeof(BiNode));
    (*T)->rchild->rchild->data = 7;
    (*T)->rchild->rchild->lchild = nullptr;
    (*T)->rchild->rchild->rchild = nullptr;

}

void displayElem(BiNode* elem)
{
    printf("%d ", elem->data);
}

// 递归调用输出结果，先左后右
// 跳转点是nullptr及递归特性
void PreOrderTraverse(BiTree T)
{
    if (T) {
        displayElem(T);
        PreOrderTraverse(T->lchild); // 1 2 4 null 5 null 3 6 null 7
        PreOrderTraverse(T->rchild);
    }
}

int main() {
    BiTree tree;
    CreateTree(&tree);
    printf("先序遍历: \n");
    PreOrderTraverse(tree);
    return 0;
}

#2 经典代码段反汇编分析

这行代码非常有意思，分析一下

这行代码本身要比反汇编要复杂，一般情况下反汇编会比源代码复杂；
因为这行代码的功能被底层直接执行了，硬件明确知道你要干吗了；

理论上来说sizeof需要call一次，BiNode需要存储一次
但都没有执行，直接给出了18H = 24 字节 = 8 + 8 + 8
好像C语言的内存结构和操作系统直接有关系，64位的4字节直接升为了8字节，默认结构体64位8字节
mov ecx,18h 对应代码sizeof(BiNode)
call qword ptr[malloc] 调用malloc方法，也不需要传递参数
mov rcx,qword ptr[T] 对应代码T，将T的指针放到rcx中
mov qword ptr[rcx],rax 将rax中的数据放到[rcx]中，对应代码*T=***

mov rax,qword ptr[T] 对应代码T，将T存储起来，以备用
mov rax,qword ptr[rax] 对应代码T->lchild，因为T直接存储了lchild，可以直接取
mov rax,qword ptr[rax+8] 对应代码T->lchild->lchild，8的偏移量
mov rax,qword ptr[rax+8] 对应代码T->lchild->lchild->data
mov ecx,4 对应代码4，将4存储以备用
mov word ptr [rax],cx 在语言层面的4默认32位，4个字节，反汇编认为4只要16位就可以
自动将ecx降为了16位寄存器cx，赋值给rax，对应代码*T->lchild->lchild->data=4

看看递归在反汇编的执行流程，递归是一种非常高效的编程逻辑使用

入口反汇编，走通用流程，方法都需要特殊处理

if(T) = if(T == nullptr)，这里的T是一个指针，比较是的指针里面的数据是不是0，
默认内存中的0或1就是空，无实际的数据

如果是空则转跳到方法的结尾

将[T]放到rcx中，[T]因为是指针，使用了qword ptr [T]来表示

进入递归逻辑，第一个递归lchild，第二是递归rchild，分析一个递归反汇编
mov rax,qword ptr[T] 对应代码T，将T放到rax中以备用
mov rcx,qword ptr[rax+10h] 对应代码T->rchild，将T->rchild放到rcx给call调用
call PreOrderTraverse 调用方法PreOrderTraverse

递归的调用方式
当执行到第一个递归的时候，一路走T->lchild的流程，直到遇到了T->lchild=nullptr
则会跳转到方法的结尾，返回到最后执行的上一层，接着执行下一个递归方法，一直这样循环，直到全部执行完毕，nullptr标记