二叉树的汇编代码

以前我们学过了二叉树的周游以及对结点类的三种C++实现形式,在这里我们看一下在汇编角度下考虑这些问题会有什么改变.下面的两个函数分别实现了对一个二叉树的前序周游以及计算二叉树的结点数:

;////////////////////////////////////////////////////////////

;该程序分析二叉树的前序周游算法,关于二叉树的创建相关的过程在此

;没有给出.为了分析前序周游,在此仅给出相关的例如得到左结点以及右

;结点和周游过程式.

;////////////////////////////////////////////////////////////

;////////////////////////////////////////////////////////////

;二叉树的一种定义结构.

;////////////////////////////////////////////////////////////

BinNode struct

dwValue dword ? ;结点中的数值.

pstLeft dword ? ;左子结点指针.

pstRight dword ? ;右子结点指针.

BinNode ends

pBinNode typedef ptr BinNode ;创建一个结构体的指针.

.data

pstNode pBinNode ? ;根结点.

.code

;////////////////////////////////////////////////////////////

;返回左子结点指针.

;////////////////////////////////////////////////////////////

GetLeftNode proc uses esi pstN:pBinNode

mov esi,pstN

assume esi:ptr BinNode

mov eax,[esi].pstLeft ;返回左子结点指针.

assume esi:nothing

ret

GetLeftNode endp

;////////////////////////////////////////////////////////////

;返回右子结点指针.

;////////////////////////////////////////////////////////////

GetRightNode proc uses esi pstN:pBinNode

mov esi,pstN

assume esi:ptr BinNode

mov eax,[esi].pstRight ;返回右子结点指针.

assume esi:nothing

ret

GetRightNode endp

;////////////////////////////////////////////////////////////

;周游二叉树算法.由于先对结点进行操作,再周游,所以这是前序周游.

;////////////////////////////////////////////////////////////

Perorder proc pstN:pBinNode

mov eax,pstN

or eax,eax

je quit ;如果结点为NULL,那么退出过程.

invoke Visit,pstN ;对该结点进行处理的过程,在此没有写出该过程.

invoke GetLeftNode,pstN

invoke Perorder,eax ;周游左子结点.

invoke GetRightNode,pstN

invoke Perorder,eax ;周游左子结点.

quit:

ret

Perorder endp

;////////////////////////////////////////////////////////////

;对二叉树的另一个周游实例,它计算出二叉树结点的总数.

;////////////////////////////////////////////////////////////

GetNodeNumber proc

xor eax,eax

call NumberNode

call WriteDec

call Crlf ;输出结点个数.

ret

GetNodeNumber endp

NumberNode proc pstN:pBinNode

inc eax ;eax加一.

invoke GetLeftNode,pstN

invoke NumberNode,pstN

invoke GetRightNode,pstN

invoke NumberNode,pstN ;递归调用函数实现枚举结点数.

ret

NumberNode endp

下面的函数用于实现二叉树的结点类的两种形式:一种是通用形式,一种是利用共用体区分两种结点的形式.

;////////////////////////////////////////////////////////////

;二叉树结点的通用定义形式.这是第一种定义方法:

;////////////////////////////////////////////////////////////

BinNodePtr struct

dwValue dword ?

pstLeft dword ?

pstRight dword ?

BinNodePtr ends

pNode typedef ptr BinNodePtr

.data

pstRoot pNode ? ;根结点指针.

.code

;////////////////////////////////////////////////////////////

;对一个结进行赋值.

;////////////////////////////////////////////////////////////

SetBinNode proc uses esi pstN:pNode,\

dwVal:dword,\

pstL:dword,\

pstR:dword

mov esi,pstN

assume esi:ptr BinNodePtr

push dwVal

pop [esi].dwValue

push pstL

pop [esi].pstLeft

push pstR

pop [esi].pstEight ;对三个成员赋值.

assume esi,nothing

ret

SetBinNode endp

;////////////////////////////////////////////////////////////

;返回以及赋置值.

;////////////////////////////////////////////////////////////

GetNodeValue proc uses esi pstN:pNode

mov esi,pstN

mov eax,(BinNodePtr ptr[esi]).dwValue ;返回结构体的值.

ret

GetNodeValue endp

SetNodeValue proc uses esi pstN:pNode,dwVal:dword

mov esi,pstN

push dwVal

pop (BinNodePtr[esi]).dwValue

ret

SetNodeValue endp

;////////////////////////////////////////////////////////////

;返回结点的左右子结点值.

;////////////////////////////////////////////////////////////

GetLeftNode proc uses esi pstN:pNode

mov esi,pstN

mov eax,(BinNodePtr ptr[esi]).pstLeft ;返回左子结点指针.

ret

GetLeftNode endp

GetRightNode proc uses esi pstN:pNode

mov esi,pstN

mov eax,(BinNodePtr ptr[esi]).pstRight ;返回右子结点指针.

ret

GetRightNode endp

;////////////////////////////////////////////////////////////

;赋值结点的左右子结点值.

;////////////////////////////////////////////////////////////

SetLeftNode proc uses esi pstN:pNode,pstL:pNode

mov esi,pstN

push pstL

pop (BinNodePtr ptr[esi]).pstLeft

ret

SetLeftNode endp

SetRightNode proc uses esi pstN:pNode,pstR:pNode

mov esi,pstN

push pstR

pop (BinNodePtr ptr[esi]).pstRight

ret

SetRightNode endp

;////////////////////////////////////////////////////////////

;判断是分支结点还是叶结点.

;////////////////////////////////////////////////////////////

IsLeaf proc uses esi pstN:pNode

mov esi,pstN

cmp (BinNodePtr ptr[esi]).pstLeft,NULL

jne notLeaf

cmp (BinNodePtr ptr[esi]).pstRight,NULL

je Leaf

notLeaf:

xor eax,eax ;不是叶结点,返回false.

ret

Leaf:

or eax,1 ;是叶结点,返回true.

ret

IsLeaf endp

;////////////////////////////////////////////////////////////

;对二叉树的测试程序.其中的Visit过程没有在此定义,它表示对该结

;点的操作.

;////////////////////////////////////////////////////////////

Traverse proc uses esi pstN:pNode

mov esi,pstN

or esi,esi

jz quit ;结点为NULL,那么返回.

invoke Visit,esi ;对结点的处理.在此没有定义该过程.

invoke GetLeftNode,esi

invoke Traverse,eax

invoke GetRightNode,esi

invoke Traverse,eax ;对两个左右分支子树进行递归调用.用前序周游算法进行分析结点.

quit:

ret

Traverse endp

上面是通用定义形式,可以看出,在应用代码中是用IsLeaf过程实现分支结点还是叶结点的判断.下面分析另一种区分两种结点的形式,它利用了共用体类型的特性来区分,这只要在上面的通用形式中多加修改就可以得到:

;////////////////////////////////////////////////////////////

;数据结构在上面的基础上进行如下的修改.

;////////////////////////////////////////////////////////////

BinNodePtr struct

union node

dwValue dword ? ;叶结点数据.

struct Intl ;结构体是分支结点的数据.

pstLeft dword ?

pstRight dword ?

opx byte ?

ends

ends

NodeFlags dword ? ;分支还是叶结点标志.

BinNodePtr ends

pBinNode typedef ptr BinNode ;创建一个结构体的指针.

;////////////////////////////////////////////////////////////

;添加两个标志.

;////////////////////////////////////////////////////////////

ISLEAF EQU 0 ;是叶结点.

ISINTL EQU 1 ;是分支结点.

.data

pstNode pBinNode ? ;根结点.

;////////////////////////////////////////////////////////////

;对一个分支结进行赋值.

;////////////////////////////////////////////////////////////

SetBinNode proc uses esi pstN:pNode,\

op:byte,\

pstL:dword,\

pstR:dword

mov esi,pstN

assume esi:ptr BinNodePtr

mov al,op

mov [esi].node.intl.opx,al

push pstL

pop [esi].node.intl.pstLeft

push pstR

pop [esi].node.intl.pstEight ;对分支结点三个成员赋值.

mov [esi].NodeFlags,ISINTL ;是分支结点.

assume esi,nothing

ret

SetBinNode endp

;////////////////////////////////////////////////////////////

;对一个叶结进行赋值.

;////////////////////////////////////////////////////////////

SetBinNode proc uses esi pstN:pNode,\

dwVal:dword,\

mov esi,pstN

assume esi:ptr BinNodePtr

push dwVal

pop [esi].node.dwValue ;对叶结点数据进行赋值.

mov [esi].NodeFlags,ISLEAF ;是叶结点.

assume esi,nothing

ret

SetBinNode endp

;////////////////////////////////////////////////////////////

;返回结点类型

;////////////////////////////////////////////////////////////

IsLeaf proc uses esi pstN:pNode

mov esi,pstN

assume esi:ptr BinNodePtr

cmp [esi].NodeFlags,ISLEAF

jne notLeaf

or eax,eax ;如果是叶结点那么返回true.

ret

notLeaf:

xor eax,eax ;如果是分支结点,那么返回false.

assume esi:nothing

ret

IsLeaf endp

;////////////////////////////////////////////////////////////

;返回结点的左右子结点值.

;////////////////////////////////////////////////////////////

GetLeftNode proc uses esi pstN:pNode

mov esi,pstN

assume esi:ptr BinNodePtr

mov eax,[esi].node.intl.pstLeft ;返回左子结点指针.

assume esi:nothing

ret

GetLeftNode endp

GetRightNode proc uses esi pstN:pNode

mov esi,pstN

assume esi:ptr BinNodePtr

mov eax,[esi].node.intl.pstRight ;返回右子结点指针.

assume esi:nothing

ret

GetRightNode endp

由于在汇编语言中没有类似C++语言的类这种数据结构,为了区分两种结点,不仅需要实现三种嵌套的结构体,而且还需要一个多余的变量保存是分支结点起作用还是叶结点,这种实现方法比通用形式要复杂得多,所以在现实中不常用.

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1714.html 转载请保留链接。