📄 b.asm
字号:
TITLE BITRTR (EXE) BINARY TREE TRAVERSING
;-----------------------------------------------------------------------------------------
.MODEL SMALL
.STACK 64
.DATA
;-----------------------------------------------------------------------------------------
BINARY DB 63 DUP (0,0,0)
HEADG1 DB 'PLEASE ENTER THE ROOT OF BINARY TREE:',0AH,0DH,'$'
HEADG2 DB 20H,'DOES THE ',27H,'$'
HEADG3 DB 27H,' HAVE LEFTCHILD? Y:INPUT THE LEFTCHILD N: PRESS ENTER',0AH,0DH,'$'
HEADG4 DB 27H,' HAVE RIGHTCHILD? Y:INPUT THE RIGHTCHILD N:PRESS ENTER',0AH,0DH,'$'
HEADG5 DB 'FIRST TRAVERSING:',0AH,0DH,'$'
HEADG6 DB 'MIDDLE TRAVERSING:',0AH,0DH,'$'
HEADG7 DB 'LAST TRAVERSING:',0AH,0DH,'$'
;-----------------------------------主程序------------------------------------
.CODE
START:
MAIN PROC FAR
MOV AX,@DATA
MOV DS,AX ;框架，初始化寄存器
PART1: MOV CX,189
MOV BX,OFFSET BINARY
MOV DX,0
LOOP1: MOV BYTE PTR[BX],DL ;清零，建立新二叉树
INC BX
DEC CX
CMP CX,0
JNZ LOOP1
;-----------------------------------------------------------------------------------------
LOOP2: MOV DX,OFFSET HEADG1
MOV AX,0900H
INT 21H ;显示提示，给ROOT赋值
MOV SI,OFFSET BINARY ;SI指向数据段
XOR CX,CX ;清除个数
MOV AX,0100H
INT 21H ;输入根结点
CMP AL,0DH ;与AL比较
JZ EXIT1 ;对根结点不赋值，直接跳出
MOV CX,3 ;分配3个空间存放自己和左右子树
CALL INROOT ;不是回车则放入AL中，执行INROOT
CALL FIRSTR ;前序遍历
MOV AX,0900H
INT 21H
;--------------- 利用CX=3，和SI控制输出中序和后序-------------------
MOV DX,OFFSET HEADG6
INT 21H ;提示中序遍历
MOV SI,OFFSET BINARY ;SI指向数据段
MOV CX,3 ; 利用CX=3
CALL MIDR ;中序遍历
MOV DX,OFFSET HEADG7
INT 21H ; 提示后序遍历
MOV SI,OFFSET BINARY ;SI指向数据段
MOV CX,3
CALL LASTR ;后序遍历
MOV AX,0100H
INT 21H
CMP AL,1BH
JNZ PART1 ;判断是否结束
EXIT1: MOV AX, 4C00H
INT 21H
MAIN ENDP
;------------------------------输入根结点---------------------------
INROOT PROC NEAR
PART2: PUSH AX
PUSH DX
CMP CX,186
JZ QUIT ;结点数满，跳出
MOV [SI],AL
CALL LEFTCHILD ;遍历左子树
CALL RIGHTCHILD ;遍历右子树
POP DX
POP AX
RET
;--------------------------------- 退出程序-----------------------------------
QUIT: MOV AX,0900H
POP DX
POP AX
JMP EXIT1
INROOT ENDP
;-------------------------------- 输入左子树--------------------------------
LEFTCHILD PROC NEAR
PART3: PUSH AX
PUSH DX
PUSH BX
MOV BX,OFFSET HEADG3
CALL PROMPT ;提示是否有左子树
MOV AX,0100H
INT 21H
CMP AL,0DH
JZ RIGHT ;无左结点跳出，判断本结点右结点
ADD BYTE PTR [SI+1],1 ;有则给其在当前值基础上+1
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL INROOT ;输入根结点
POP SI
RIGHT: POP BX
POP DX
POP AX
RET
LEFTCHILD ENDP
;------------------------------- 输入右子树---------------------------------
RIGHTCHILD PROC NEAR
PART4:PUSH AX
PUSH DX
PUSH BX
MOV BX,OFFSET HEADG4
CALL PROMPT ;提示是否有右子树
MOV AX,0100H
INT 21H
CMP AL,0DH
JZ LEFT ;无右结点跳出，判断下个结点左结点
ADD BYTE PTR[SI+2],1 ;有则给其在当前值基础上+2
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL INROOT ;输入根结点
POP SI
LEFT:SUB SI,3 ;去找上个结点的右结点
POP BX
POP DX
POP AX
RET
RIGHTCHILD ENDP
;--------------------------- 提问是否有左右子树---------------------------
PROMPT PROC NEAR
PART5:PUSH AX
PUSH DX
MOV AX,0900H
MOV DX,OFFSET HEADG2
INT 21H ;提问是否有左右子树
MOV AX,0200H
MOV DL,[SI]
INT 21H
MOV AX,0900H
MOV DX,BX
INT 21H
POP DX
POP AX
RET
PROMPT ENDP
;------------------------------- 先序遍历根结点-------------------------
FIRSTR PROC NEAR
PUSH AX
PUSH DX
MOV DX,OFFSET HEADG5
MOV AX,0900H
INT 21H ;提示先序遍历
MOV SI,OFFSET BINARY ;SI指向数据段
PART6: MOV DL,[SI]
MOV AX,0200H
INT 21H
ADD SI,3
CMP BYTE PTR[SI],0
JZ RE ;无根结点则返回上个结点
JMP PART6 ;有则继续输入
RE:POP DX
POP AX
RET
FIRSTR ENDP
;----------------------------------- 中序遍历------------------------------
MIDR PROC NEAR
PART7:PUSH AX
PUSH DX
CALL MIDRL ;返回中序左子树遍历
MOV AX,0200H
MOV DL,[SI]
INT 21H
CALL MIDRR ;返回中序右子树遍历
POP DX
POP AX
RET
MIDR ENDP
;-------------------------------- 判断左子树----------------------------------
MIDRL PROC NEAR
PART8:PUSH AX
PUSH DX
CMP BYTE PTR[SI+1],0
JZ EXIT2 ;无左子树则返回上个结点
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL MIDR ;有的话继续对左结点判断
POP SI
EXIT2:POP DX
POP AX
RET
MIDRL ENDP
;------------------------------- 判断右子树-------------------------------------
MIDRR PROC NEAR
PART9:PUSH AX
PUSH DX
CMP BYTE PTR[SI+2],0
JZ EXIT3 ;无右子树则返回上个结点
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL MIDR ;有的话继续对左结点判断
POP SI
EXIT3:SUB SI,3
POP DX
POP AX
RET
MIDRR ENDP
;-------------------------------- 后序遍历-----------------------------
LASTR PROC NEAR
PART10:PUSH AX
PUSH DX
CALL LASTRL ;返回后序左子树遍历
CALL LASTRR ;返回后序右子树遍历
MOV AX,0200H
MOV DL,[SI]
INT 21H
SUB SI,3
POP DX
POP AX
RET
LASTR ENDP
;--------------------------------- 判断左子树------------------------------
LASTRL PROC NEAR
PART11:PUSH AX
PUSH DX
CMP BYTE PTR[SI+1],0
JZ EXIT4 ;无左子树则返回上个结点
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL LASTR ;返回重新进行LASTR遍历
POP SI
EXIT4:POP DX
POP AX
RET
LASTRL ENDP
;------------------------------- 判断右子树--------------------------------
LASTRR PROC NEAR
PART12:PUSH AX
PUSH DX
CMP BYTE PTR[SI+2],0
JZ EXIT5 ;无左子树则返回上个结点
PUSH SI
MOV SI,OFFSET BINARY ;SI指向数据段
ADD SI,CX
ADD CX,3
CALL LASTR ;返回重新进行LASTR遍历
POP SI
EXIT5:POP DX
POP AX
RET
LASTRR ENDP
;-----------------------------------------------------------------------------------------
END START
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -