bitree.asm

使用汇编写的二叉树遍历

.MODEL SMALL
.STACK 64
.DATA
BiTree      DB  63 DUP(0)                          ;建立数组，进行初始化
MSGEMPTY    DB  0ah,0dh,'It is a empty tree',0DH,0AH,'$'
MSGROOT     DB  'Please input the root :','$'
MSGLEFT     DB  'Is it have the leftchildtree of ','$'
MSGRIGHT    DB  'Is it have the rightchildtree of ','$'
MSGNODE     DB  'Please input the node:','$'
MSGPRE      DB  'The PreOrderTraverse of the bitree is:',0dh,0ah,'$'
MSGIN       DB  0dh,0ah,'The InOrderTraverse of the bitree is:',0dh,0ah,'$'
MSGLATER    DB  0dh,0ah,'The LaterOrderTraverse of the bitree is:',0dh,0ah,'$'
MSGENTER    DB  0DH,0AH,'[Y/N]','$'
.CODE
MAIN   PROC FAR
       MOV AX,@DATA
       MOV DS,AX
       
       CALL InitBiTree             ;初始化一个二叉树，建立数组
       SUB  SI,SI                  ;SI寄存器清零
       LEA  DX,MSGPRE              ;先序遍历提示
       CALL OutPut
       CALL PreOrderTraverse       ;进行先序遍历
       SUB  SI,SI  
       LEA  DX,MSGIN               ;中序遍历提示
       CALL OutPut
       CALL InOrderTraverse        ;进行中序遍历
       SUB  SI,SI
       LEA  DX,MSGLATER            ;进行后序遍历提示
       CALL OutPut
       CALL LaterOrderTraverse     ;进行后序遍历
       JMP  EXIT                   ;退出

EXIT:  MOV  AX,4C00H               ;结束
       INT  21H
MAIN ENDP
;__________________________________
;建立二叉树
;__________________________________
InitBiTree PROC NEAR
           SUB  DI,DI              ;用于对结点的标记
           SUB  SI,SI              ;当前结点子树存储位置
           MOV  CX,15              ;循环记数到五层最后一个结点
           MOV  DX,OFFSET MSGROOT
           CALL OutPut             ;输出跟结点提示
           CALL InPut              ;输入跟结点
           
           CMP  AL,0dh             ;判断是否为空树
           JNZ  SAVE

           CALL EmptyTree    
           JMP  Loop3           
     SAVE: MOV  BiTree,AL          ;把输入内容存入树组
           CALL Enter               
      Left:
           CMP  BiTree[DI],0H      ;看结点是否为空
           JZ   Loop1              
           MOV  DX,OFFSET MSGLEFT  ;左子树输入提示
           CALL OutPut
           MOV  DX,WORD PTR BiTree[DI]
           CALL OutPut1            ;父结点,用于表示输入的是谁的子树
          
           MOV DX,OFFSET MSGENTER  ;换行回车
           CALL OutPut
           
           CALL InPut              ;输入判断信息
           CALL Change             ;无论'Y','y'都转化成'y'
           INC  SI                 ;右子数的存储位置
           INC  DI                 ;下一结点
           CMP  AL,79H             ;判断是否为'y'
           JNZ  Right              ;不是则进入Right
           
           CALL Enter
           MOV  DX,OFFSET MSGNODE  ;结点输入提示
           CALL OutPut
           CALL InPut              ;输入结点
           MOV  BiTree[SI],AL
     Right:
           CALL Enter
           MOV  DX,OFFSET MSGRIGHT ;是否有右子树提示
           CALL OutPut
           DEC  DI
           MOV  DX,WORD PTR BiTree[DI];右子树的根结点
           CALL OutPut1  
           MOV DX,OFFSET MSGENTER     ;换行回车
           CALL OutPut
           CALL InPut                 ;输入判断条件
           CALL Change                ;无论'Y','y'都转化成'y'
           INC  SI
           INC  DI
           CMP  AL,79H                ;判断是不是'y'
           JNZ  Loop2
           
           CALL Enter
           MOV  DX,OFFSET MSGNODE     ;结点输入提示
           CALL OutPut
           CALL InPut
           MOV  BiTree[SI],AL         ;结点输入数组
           CALL Enter
           JMP  Loop2
     Loop1:
           INC  DI                    ;当前结点加一,指向下一结点
           INC  SI                    ;如果当前结点不存在,则它的左子树也不存在
           INC  SI                    ;如果当前结点不存在,则它的右子树也不存在
           CALL Enter 
     Loop2:
           LOOP Left
     Loop3:
           RET
InitBiTree ENDP
;__________________________________
;先序遍历
;__________________________________
PreOrderTraverse PROC NEAR
                 CMP BiTree[SI],0
                 JZ  LL
                 MOV DX,WORD PTR BiTree[SI]
                 CALL OutPut1
                 MOV  DX,OFFSET MSGPRE
                 PUSH SI                   ;把当前结点入栈
                 SHL  SI,1                 ;SI左移乘2
                 INC  SI                   ;SI的值加1,即此时SI表示左子树结点位置
                 CALL PreOrderTraverse 
                 POP  SI
                 SHL  SI,1                 ;SI表示右子树的位置
                 ADD  SI,2
                 CALL PreOrderTraverse 
              LL:
                 RET 
PreOrderTraverse ENDP
;__________________________________
;中序遍历
;__________________________________
InOrderTraverse PROC NEAR
                CMP  BiTree[SI],0
                JZ   LLL
                PUSH SI
                SHL  SI,1                  ;SI左移乘2
                INC  SI                    ;SI的值加1,即此时SI表示左子树结点位置
                CALL InOrderTraverse 
                POP  SI
                MOV  DX,WORD PTR BiTree[SI]
                CALL OutPut1
                SHL  SI,1                  ;SI表示右子树的位置
                ADD  SI,2
                CALL InOrderTraverse 
            LLL:
                RET
InOrderTraverse ENDP
;__________________________________
;后序遍历
;__________________________________
LaterOrderTraverse PROC NEAR
                   CMP  BiTree[SI],0
                   JZ   LLLL
                   PUSH SI
                   SHL  SI,1                ;SI左移乘2
                   INC  SI                  ;SI的值加1,即此时SI表示左子树结点位置
                   CALL LaterOrderTraverse 
                   INC  SI
                   CMP  BiTree[SI],0
                   JZ   la
                   CALL LaterOrderTraverse 
                la:                         ;SI表示右子树的位置
                   POP  SI
                   MOV  DX,WORD PTR BiTree[SI]
                   CALL OutPut1
              LLLL:
                   RET
LaterOrderTraverse ENDP
;__________________________________
OutPut PROC NEAR                       ;输出字符串
       MOV AH,09H
       INT 21H
       RET
OutPut ENDP
;__________________________________
InPut PROC NEAR                    ;输入单个字符
      MOV AH,01H
      INT 21H
      RET
InPut ENDP
;__________________________________
Enter PROC NEAR                    ;输入后换行并回车
      MOV DL,0DH
      MOV AH,2
      INT 21H
      
      MOV DL,0AH
      MOV AH,2
      INT 21H
      RET
Enter ENDP
;__________________________________
OutPut1 PROC NEAR                  ;输出单个字符
      MOV AH,2H
      INT 21H
      RET
OutPut1 ENDP
;__________________________________
Change PROC NEAR                   ;把"Y"变成"y"
       MOV BL,01100000b
       OR AL,BL
       RET
Change ENDP
;__________________________________
EmptyTree PROC NEAR                       ;空树提示
       LEA  DX,MSGEMPTY
       MOV  AH,09H
       INT  21H
       RET
EmptyTree ENDP
END MAIN