tree.asm

You can see some basis operation on the binary tree.There are some very easy content of data structu

.model small
.stack
.data
letter db 32 dup (' ')	;初始值定义为空格，在树中空格表示结点不存在
msg_enter db  0Dh,0Ah,'$'
msg_cue db  'Input the root letter:','$'
msg_input db 'Input the','$'
msg_left db "'s left child is:",'$'
msg_right db "'s right child is:",'$'
msg_empty db 'There is no data in your tree! EXIT...','$'
msg_show db 'Display as follow:','$'
msg_interface db '--------------------------------------------------------------------','$'
msg_pre db '	The Preorder is:','$'
msg_in db '	The Inorder is:','$'
msg_post db '	The Postorder is:','$'
.code
main proc far
	mov ax,@data
	mov ds,ax
	mov di,1		;左子=2*di，右子=2*di+1
	mov si,di
;等待输入根结点的提示信息：
	lea dx,msg_cue
	call print		;调显示字符串子程序
	call input
	call enter		;回车
	cmp letter[di],20h
	jne creat		;根结点存在
;提示树中无任何元素并结束程序
	lea dx,msg_empty 
	call print		;调显示字符串子程序
	jmp over
creat:
;调初始化树子过程（先序）：
	call Init_tree
	lea dx,msg_interface
	call print
	call enter
;提示遍历部分：
	lea dx,msg_show
	call print		;调显示字符串子程序
	call enter		;回车
	lea dx,msg_interface
	call print
	call enter
;先序遍历:	
	lea dx,msg_pre
	call print		;调显示字符串子程序
	mov di,1
	call Pre_order
	call enter		;回车
	lea dx,msg_interface
	call print
	call enter
;中序遍历:
	lea dx,msg_in
	call print		;调显示字符串子程序
	mov di,1
	call In_order
	call enter		;回车
	lea dx,msg_interface
	call print
	call enter
;后序遍历:
	lea dx,msg_post
	call print		;调显示字符串子程序
	mov di,1
	mov si,1
	call Post_order
over:
main endp
	mov ah,4ch
	int 21h
;-----------------------------------------------------------------------------------------
;	proc  print——打印信息子过程
;-----------------------------------------------------------------------------------------
print proc near
	mov ah,09h
	int 21h
 	ret
print endp
;-----------------------------------------------------------------------------------------
;	proc enter——回车换行子过程
;-----------------------------------------------------------------------------------------
enter proc near
	lea dx,msg_enter
	mov ah,09h
	int 21h
	ret
enter endp
;-----------------------------------------------------------------------------------------
;	proc input——输入字符子过程	
;-----------------------------------------------------------------------------------------
input proc near
	mov ah,01h
	int 21h
	mov letter[di],al	;保存所输入的数据
	ret
input endp
;-----------------------------------------------------------------------------------------
;	proc output——输出字符子过程
;-----------------------------------------------------------------------------------------
output proc near
	mov dl,letter[si] 	 ;用于输出提示信息
	cmp dl,' '		 ;空格表示结点为空
	jz output_return
	mov ah,02h
	int 21h
output_return:
	ret
output endp
;-----------------------------------------------------------------------------------------
;	proc init_tree——生成树子过程 
;-----------------------------------------------------------------------------------------
init_tree proc near
	push di
	mov si,di		;根结点入栈并赋给用于提示信息的SI
	shl di,01h		;找到左结点，左子=2*di，右子=2*di+1
	cmp di,31		;判是否超五层
	ja right		;超出则跳转
	call output		;输出父结点以及提示信息
	lea dx,msg_left
	call print		;调输出子程序
	call input		;调输入子程序
	cmp al,20h		;判结点是否存在
	call enter		;回车
	je right		
	call init_tree	;递归
right:pop di
	mov si,di
	shl di,01h
	inc di			;找到右子结点，左子=2*di，右子=2*di+1
	cmp di,31		;判是否超五层
	ja return		;超则结束
	call output		;输出结点
	lea dx,msg_right;输出输入右子提示信息
	call print		;调显示字符串子程序
	call input		;调输入
	cmp al,20h		;判是否为空
	call enter		;回车
	je return		;空则结束
	call init_tree	;递归
return:
	ret
init_tree endp
;-----------------------------------------------------------------------------------------
;	proc Pre_order——先序遍历子过程
;-----------------------------------------------------------------------------------------
Pre_order proc near
	push di				;保存父结点
	mov si,di
	call output			;访问根结点
	shl di,01h			;找到左结点，左子=2*di，右子=2*di+1
	cmp di,31			;是否超过五层
	ja pre_right	
	cmp letter[di],' '	;判断结点是否为空
	je pre_right	
	call Pre_order		;递归
	
pre_right:
	pop di		
	shl di,01h		
	inc di				;找到右孩子结点，左子=2*di，右子=2*di+1
	mov si,di
	cmp di,31			;判是否超过五层
	ja pre_return		;超出则推出
	cmp letter[di],' '	;判结点是否为空
	je pre_return		;空则结束
	call Pre_order		;递归
pre_return:	
	ret
Pre_order endp
;-----------------------------------------------------------------------------------------
;	proc Inorder——中序遍历子过程
;-----------------------------------------------------------------------------------------
In_order proc near
	push di
	mov si,di
	shl di,01h			;找到左孩子结点，左子=2*di，右子=2*di+1
	cmp di,31			;判是否超五层
	ja in_right			;超则跳转
	cmp letter[di],' '	;判结点是否为空
	je in_right			;空则跳转
	call In_order		;递归
in_right:
	pop di
	mov si,di
	call output			;访问结点
	shl di,01h	
	inc di				;找到右结点，左子=2*di，右子=2*di+1
	cmp di,31			;判是否超五层
	ja in_return		;超则推出
	cmp letter[di],' '	;判结点是否为空
	je in_return		;空则推出
	call In_order		;递归
in_return:
	ret
In_order endp
;-----------------------------------------------------------------------------------------
;	proc Post_order——后序遍历子过程
;-----------------------------------------------------------------------------------------
Post_order proc near
	push di
	shl di,01h			;找到左孩子结点，左子=2*di，右子=2*di+1
	cmp di,31			;判是否超五层
	ja post_right		;超则跳转
	cmp letter[di],' '	;判结点是否为空
	je post_right		;空则跳转
	call Post_order		;递归
post_right:
	pop di
	mov si,di
	shl di,01h	
	inc di				;找到右结点，左子=2*di，右子=2*di+1
	cmp di,31			;判是否超五层
	ja post_return		;超则推出
	cmp letter[di],' '	;判结点是否为空
	je post_return		;空则退出
	push si				;保存父结点
	call Post_order		;递归
	pop si	
post_return:
	call output			;访问结点
	ret
Post_order endp
;-----------------------------------------------------------------------------------------
end main