btree2.asm

实现输入二叉树并对它进行先序中序后序遍历

.model small  
.stack 64
;-------------------------
.data
array db 31 dup(?)
f  db 0dh,0ah,'$'
f1 db 'please input the root of the tree(if no,press enter):','$'
f2 db 'have a leftchild?(if no,press enter):','$'
f3 db 'have a rightchild?(if no,press enter):','$'
f4 db 'The first root traversing:','$'
f5 db  'The middle root traversing:','$'
f6 db  'The last root traversing:','$'
;------------------------------------------------------------------
.code
;------------------------------------------------------------------     
main proc far
start:  mov ax,@data
        mov ds,ax                         ;初始化DS
        mov si,0                          ;设置数组array的指针si为0
        mov dx,offset f1
        mov ah,09h
        int 21h                           ;显示提示输入根结点字符串
        mov ah,01h
        int 21h                           ;输入根结点
        cmp al,0
        jz exit1                          ;若为0则返回DOS
        call inroot                       ;调用inroot开始建二叉树
        mov dx,offset f
        mov ah,09h
        int 21h                           ;显示换行回车
        mov dx,offset f4
        mov ah,09h
        int 21h                           ;显示字符串先序遍历 
        call firstroot                    ;调用先序遍历子程序
        mov dx,offset f
        mov ah,09h
        int 21h
        mov dx,offset f5
        mov ah,09h
        int 21h                           ;显示字符串中序遍历
        call midroot                      ;调用中序遍历子程序
        mov dx,offset f
        mov ah,09h
        int 21h
        mov dx,offset f6
        mov ah,09h
        int 21h                           ;显示字符串后序遍历
        call lastroot                     ;调用后序遍历子程序
exit1:  mov ax,4c00h
        int 21h                      
main endp                                 ;主程序结束
;----------------------------------------------------------------           
inroot proc near                          ;输入二叉树的过程                  
        mov [array+si],al                 ;把根结点放入数组
        call left                         ;调用left输入左孩子
        call right                        ;调用right输入右孩子 
  ret
inroot endp
;----------------------------------------------------------------
left proc near                       
        push ax
        mov bx,ax                         ;把输入的字符暂存入bx中
        mov dx,offset f
        mov ah,09h
        int 21h                           ;显示换行回车
        mov dl,bl
        mov ah,02h
        int 21h                           ;显示输入的字符
        mov ah,02h
        mov dl,' '
        int 21h                           ;显示一个空格
        mov dx,offset f2
        mov ah,09h
        int 21h                           ;显示字符串f2
        mov ah,01h
        int 21h                           ;输入左孩子结点
        cmp al,0dh
        jz quit1                          ;如果为回车则结束
        push si                     
        add si,si
        inc si                            ;不为0指针变为2si+1
        call inroot                       ;调用inroot询问该结点有无左右孩子
        pop si
quit1:  pop ax
  ret
left endp                                 ;左孩子输入完毕
;----------------------------------------------------------------
right proc near
        push ax
        mov bx,ax                         ;把输入的字符放入bx中
        mov dx,offset f
        mov ah,09h
        int 21h                           ;显示换行回车
        mov ah,02h
        mov dl,bl
        int 21h                           ;显示输入的字符
        mov ah,02h
        mov dl,' '
        int 21h                           ;显示一个空格
        mov dx,offset f3
        mov ah,09h
        int 21h                           ;显示字符串f3
        mov ah,01h
        int 21h                           ;输入左孩子结点
        cmp al,0dh
        jz quit2                          ;如果为回车则结束
        push si 
        add si,si
        inc si
        inc si                            ;不为0指针变为2si+2
        call inroot                       ;调用inroot询问该结点有无左右孩子
        pop si
quit2:  pop ax
  ret
right endp                                ;右孩子输入完毕
;---------------------------------------------------------------
firstroot proc near                       ;先序遍历过程
        mov dl,[array+si] 
        mov ah,02h
        int 21h                           ;把根结点放入dl并显示
        call frleft                       ;调用frleft子程序
        call frright                      ;调用frright子程序                    
  ret
firstroot endp
;---------------------------------------------------------------
frleft proc near
        push si                           ;把当前si压栈
        add si,si   
        inc si                            ;si变为2si+1  
        cmp byte ptr[array+si],0
        jz quit5                          ;比较为0则结束
        call firstroot                    ;不为0则调用firstroot
quit5:  pop si                            ;si出栈
  ret
frleft endp
; --------------------------------------------------------------
frright proc near
        push si                           ;把当前si压栈
        add si,si
        inc si
        inc si                            ;si变为2si+2
        cmp byte ptr[array+si],0
        jz quit6                          ;比较为0则结束
        call firstroot                    ;不为0则调用firstroot
quit6:  pop si                            ;si出栈
  ret
frright endp
;---------------------------------------------------------------
midroot proc near                         ;中序遍历过程
        call mrleft                       ;调用mrleft子程序
        mov dl,[array+si]                 ;当前根结点放入dl
        mov ah,02h
        int 21h                           ;显示此根结点
        call mrright                      ;调用mrright子程序
  ret
midroot endp
;---------------------------------------------------------------
mrleft proc near
        push si                           ;把当前si压栈
        add si,si
        inc si                            ;si变为2si+1
        cmp byte ptr[array+si],0 
        jz quit3                          ;比较为0则结束
        call midroot                      ;不为0则调用midroot
quit3:  pop si                            ;si出栈
  ret
mrleft endp
;---------------------------------------------------------------
mrright proc near
        push si                          ;把当前si压栈
        add si,si
        inc si
        inc si                           ;si变为2si+2
        cmp byte ptr[array+si],0
        jz quit4                         ;比较为0则结束
        call midroot                     ;不为0则调用midroot
quit4:  pop si                           ;si出栈
  ret
mrright endp
;---------------------------------------------------------------

lastroot proc near                       ;后序遍历过程
        call lrleft                      ;调用lrleft子程序
        call lrright                     ;调用lrright子程序
        mov dl,[array+si]                ;当前根结点放入dl
        mov ah,02h 
        int 21h                          ;显示此根结点
  ret
lastroot endp
;----------------------------------------------------------------
lrleft proc near
        push si                          ;把当前si压栈
        add si,si
        inc si                           ;si变为2si+1
        cmp byte ptr[array+si],0
        jz quit7                         ;比较为0则结束
        call lastroot                    ;不为0则调用lastroot
quit7:  pop si                           ;si出栈
  ret
lrleft endp
;----------------------------------------------------------------
lrright proc near
        push si                          ;把当前si压栈
        add si,si
        inc si
        inc si                           ;si变为2si+2
        cmp byte ptr[array+si],0
        jz quit8                         ;比较为0则结束
        call lastroot                    ;不为0则调用lastroot
quit8:  pop si                           ;si出栈
  ret
lrright endp
;----------------------------------------------------------------
end main                                 ;程序结束