[原创]说说汇编与二叉树

搬砖王

技术分享 2月前 15 浏览

[原创]说说汇编与二叉树

这篇文章写给还不明白二叉树或者看不懂二叉树的汇编代码的新手朋友们。
1、现在游戏越来越多的用二叉树来储存一些数据结构，逆向游戏的朋友们可能经常会碰到二叉树遍历的问题，不熟悉二叉树或不熟悉汇编二叉树的朋友们可能对二叉树结构一筹莫展，就像我没写这篇帖子之前一样，但用汇编写过一边二叉树，就再也不会看二叉树的代码像陌生人一样了，这就是为什么要用汇编写二叉树的原因。
2、什么是二叉树，如下图所示（一个3层的二叉树）

用汇编来定义一个二叉树结构如下：

DTREENODE struct
	NodeData		DWORD	?
	lChildNode		DWORD	?
	rChildNode		DWORD	?
DTREENODE ends

NodeData是二叉树节点的数据，代码里我写入的是其序号，当然你还可以定义更多的数据
lChildNode是二叉树的左孩子节点，指向其下一层左节点
rChildNode是二叉树的右孩子节点，指向其下一层右节点
最后一层（如4节点）的lChildNode和rChildNode都为0，不再指向任何新节点了
3、代码：

.386
.Model Flat, StdCall
Option Casemap :None
include windows.inc
include user32.inc
include kernel32.inc
includelib user32.lib
includelib kernel32.lib
InitDTree proto
CreateDTreeNode proto _pDTreeNode:DWORD, _Index:DWORD
AllocMem proto _MemSize:DWORD
PrintDTree proto _pDTree:DWORD

DTREENODE struct
NodeData DWORD ?
lChildNode DWORD ?
rChildNode DWORD ?
DTREENODE ends
.data
DTree DTREENODE 7 dup (<>)
NodeNum DWORD 3 ;二叉树的层数
MemAddr DWORD offset DTree ;MemAddr = 指向DTree未分配的内存
.const
.code
Start:
add MemAddr, sizeof DTREENODE
invoke InitDTree
invoke PrintDTree, addr DTree
invoke ExitProcess, eax

;名称：InitDTree
;功能：初始化二叉树
;参数：无
;返回：无
InitDTree proc
invoke CreateDTreeNode, addr DTree, 1
ret
InitDTree endp
;名称：CreateDTreeNode
;功能：递归调用自身创建一个NodeNum层的满二叉树
;参数：_pDTreeNode = 二叉树节点指针
;参数： _Index = 二叉树节点序号，写入节点的NodeData字段
;返回：无
CreateDTreeNode proc _pDTreeNode:DWORD, _Index:DWORD
pushad
mov ebx, _pDTreeNode
assume ebx:ptr DTREENODE
mov esi, _Index
mov [ebx].NodeData, esi
mov ecx, esi ;ecx = 节点所在的层数 = 序号/2 + 1
shr ecx, 1
inc ecx
.if ecx >= NodeNum
mov [ebx].lChildNode, 0
mov [ebx].rChildNode, 0
.else
mov eax, sizeof DTREENODE ;分配双倍的DTREENODE所需字节的内存分别放左节点和右节点
shl eax, 1
invoke AllocMem, eax
test eax, eax
jz AllocMemFail
shl esi, 1 ;左子节点的序号 = 父节点的序号*2，右子节点的序号 = 父节点的序号*2 + 1
mov [ebx].lChildNode, eax
invoke CreateDTreeNode, eax, esi
add eax, sizeof DTREENODE
mov [ebx].rChildNode, eax
inc esi
invoke CreateDTreeNode, eax, esi
AllocMemFail:
.endif
assume ebx:nothing
popad
ret
CreateDTreeNode endp
;名称：AllocMem
;功能：调度内存，根据要分配的内存大小设置MemAddr的值
;参数：_MemSize = 要分配的内存大小
;返回：eax = 分配的内存地址，失败则 eax = 0
AllocMem proc _MemSize:DWORD
push edx
mov edx, offset DTree
add edx, sizeof DTree
mov eax, MemAddr
.if eax >= edx ;判断要申请的内存地址是否超出范围
xor eax, eax
.else
mov edx, _MemSize ;将MemAddr + _MemSize，指向新的内存地址
add MemAddr, edx
.endif
pop edx
ret
AllocMem endp
;名称：PrintDTree
;功能：利用递归遍历输出二叉树
;参数：_pDTree = 二叉树节点指针
;返回：无
PrintDTree proc _pDTree:DWORD
push ebx
mov ebx, _pDTree
assume ebx:ptr DTREENODE
invoke VK_DwordMsgBox, [ebx].NodeData ;弹出一个消息框，显示二叉树节点的数据
.if [ebx].lChildNode != 0
invoke PrintDTree, [ebx].lChildNode
.endif
.if [ebx].rChildNode != 0
invoke PrintDTree, [ebx].rChildNode
.endif
assume ebx:nothing
pop ebx
ret
PrintDTree endp
end Start

4、代码中的CreateDTreeNode是创建一个满二叉树，共7个节点，我没使用VirtualAlloc等函数申请动态内存（可以直接替换代码中的AllocMem函数），而是自己写了个，是为了能将二叉树的数据写到一个连续的内存中便于观察，同时可免去申请内存后释放的问题，我们可以申请一块大内存，然后一次释放即可，只需要将MemAddr改为申请的内存地址即可。
创建好后的二叉树在内存的存放如下：