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

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

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

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

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

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

#1 程序源代码

#include #include #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; }

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

理论上来说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=***

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

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标记

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。