bitree.asm

次程序为数据结构中的二叉树

.MODEL SMALL
.STACK 64
.DATA
;===============
BITREE		DB 63 DUP(0)			;定义数组，顺序存储二叉树
MSGEMPTYTREE	DB 'YOUR TREE IS EMPTY!!!',0DH,0AH,'$'
MSGROOT     	DB 'Please input the root:$'
MSGRCHILD	DB "'s right child:$"
MSGLCHILD	DB "'s lift child:$"
MSGPRE		DB 'The PerOrderTraverse is:$'
MSGIN		DB 0DH,0AH,'The InOrderTraverse is:$'
MSGPOST		DB 0DH,0AH,'The PostOrderTraverse is:$'
;===============
.CODE
MAIN	PROC FAR
	MOV AX,@DATA
	MOV DS,AX
	
	CALL INITBITREE		;创建二叉树

	SUB SI,SI		;先序遍历
	LEA DX,MSGPRE
	CALL OUTPUT
	CALL PREORDERTRAVERSE

	SUB SI,SI		;中序遍历
	LEA DX,MSGIN
	CALL OUTPUT
	CALL INORDERTRAVERSE

	SUB SI,SI		;后序遍历
	LEA DX,MSGPOST
	CALL OUTPUT
	CALL POSTORDERTRAVERSE

	MOV AX,4C00H
	INT 21H
MAIN ENDP
;===============
;建立二叉树
;===============
INITBITREE	PROC NEAR	
		SUB DI,DI	;清零，用于指向PARENT节点
		SUB SI,SI	;清零，用于指向CHILD节点
		MOV CX,15	;标记循环次数
		LEA DX,MSGROOT
		CALL OUTPUT
		CALL INPUT
		CMP AL,0DH	;输入回车时为空树
		JNZ SAVE

		CALL ENTER	;好回车换行
		CALL EMPTYTREE	;调用空树提示子程序
		JMP RR
SAVE:		
		MOV BITREE[DI],AL
		CALL ENTER
LIFTCHILD:	
		CMP BITREE[DI],00H	;判断PARENT节点是否为空
		JZ LOOPR

		MOV DX,WORD PTR BITREE[DI]
		CALL OUTPUTS		;输出根节点
		LEA DX,MSGLCHILD	;输出LIFTCHILD节点提示
		CALL OUTPUT
		CALL INPUT
		INC SI		;标记存储子树
		INC DI		;指向下一根节点
		CMP AL,0DH	;是否为回车--空
		JZ RIGHTCHILD	;无左子树，跳转到右子树

		MOV BITREE[SI],AL	;存储左子树节点
RIGHTCHILD:	
		CALL ENTER
		DEC DI			;指向右子树的PARENT节点
		MOV DX,WORD PTR BITREE[DI]
		CALL OUTPUTS
		LEA DX,MSGRCHILD	;输出RIGHTCHILD节点提示
		CALL OUTPUT
		CALL INPUT
		INC SI		;标记存储子树
		INC DI
		CMP AL,0DH
		JZ LOOPL	;无左子树，跳转到右子树

		MOV BITREE[SI],AL	;存储右子树节点
		JMP LOOPL		;转到左子树
LOOPR:		
		INC DI		;指向数组中下一个节点作为ROOT节点
		INC SI		;跳过当前节点的左子树的存储位置
		INC SI		;跳过当前节点的右子树的存储位置
LOOPL:		
		CALL ENTER
		LOOP LIFTCHILD
RR:		
		RET
INITBITREE	ENDP
;=========================先序遍历	
PREORDERTRAVERSE PROC NEAR
	CMP BITREE[SI],00H		;判断PARENT节点是否为空
	JZ RRR
	MOV DX,WORD PTR BITREE[SI]	;访问当前节点
	CALL OUTPUTS
	
	PUSH SI				;递归遍历左子树
	SHL SI,01H
	INC SI
	CALL PREORDERTRAVERSE
	
	POP SI				;递归遍历右子树
	SHL SI,01H
	INC SI
	INC SI
	CALL PREORDERTRAVERSE
RRR:

	RET
PREORDERTRAVERSE ENDP
;=========================中序遍历
INORDERTRAVERSE PROC NEAR
	CMP BITREE[SI],00H		;判断PARENT节点是否为空
	JZ RRRR
	PUSH SI				;递归遍历左子树
	SHL SI,1
	INC SI
	CALL INORDERTRAVERSE

	POP SI				;访问当前节点
	MOV DX,WORD PTR BITREE[SI]
	CALL OUTPUTS
	
	SHL SI,1			;递归遍历右子树
	INC SI
	INC SI
	CALL INORDERTRAVERSE
RRRR:
	RET
INORDERTRAVERSE ENDP
;=========================后序遍历
POSTORDERTRAVERSE PROC NEAR
	CMP BITREE[SI],00H		;判断PARENT节点是否为空
	JZ RRRRR

	PUSH SI				;递归遍历左子树
	SHL SI,1
	INC SI
	CALL POSTORDERTRAVERSE

	INC SI				;递归遍历右子树
	CMP BITREE[SI],00H		;判断当前节点为空时访问其PARENT节点
	JZ POST	
	CALL POSTORDERTRAVERSE
POST:					;访问节点
	POP SI
	MOV DX,WORD PTR BITREE[SI]
	CALL OUTPUTS
RRRRR:
	RET
POSTORDERTRAVERSE ENDP
;===============字符串输出子程序
OUTPUT	PROC NEAR
	MOV AH,09H
	INT 21H
	RET
OUTPUT ENDP
;===============字符输入子程序
INPUT	PROC NEAR
	MOV AH,01H
	INT 21H
	RET
INPUT	ENDP
;===============单个字符输出子程序
OUTPUTS PROC NEAR
	MOV AH,02H
	INT 21H
	RET
OUTPUTS ENDP
;===============空树提示子程序
EMPTYTREE PROC NEAR
	LEA DX,MSGEMPTYTREE
	MOV AH,09H
	INT 21H
	RET
EMPTYTREE ENDP
;===============回车换行子程序
ENTER PROC NEAR
	MOV DX,0DH
	MOV AH,02H
	INT 21H
	MOV DX,0AH
	MOV AH,02H
	INT 21H
	RET
ENTER ENDP
;===============
END MAIN