📄 shu.asm
字号:
;顺序存储二叉树
;设一个数组 a[i]
;1。仅当i=1时，结点i为根结点；
;2。结点i的左儿子结点为2i；
;3。结点i的右儿子结点为2i+1；
;程序说明：首先利用数组顺序接收二叉树，然后先序遍历二叉树，最后输出先序遍历序列
;=====================================================================================
;=====================================================================================
;算法思想:
; 1.先序遍历非递归算法
; #define maxsize 100
; typedef struct
; {
; Bitree Elem[maxsize];
; int top;
; }SqStack;
; void PreOrderUnrec(Bitree t)
; {
; SqStack s;
; StackInit(s);
; p=t;
; while (p!=null || !StackEmpty(s))
; {
; while (p!=null) //遍历左子树
; {
; visite(p->data);
; push(s,p);
; p=p->lchild;
; }//endwhile
; if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
; {
; p=pop(s);
; p=p->rchild;
; }//endif
; }//endwhile
; }//PreOrderUnrec
; 2.中序遍历非递归算法
; #define maxsize 100
; typedef struct
; {
; Bitree Elem[maxsize];
; int top;
; }SqStack;
; void InOrderUnrec(Bitree t)
; {
; SqStack s;
; StackInit(s);
; p=t;
; while (p!=null || !StackEmpty(s))
; {
; while (p!=null) //遍历左子树
; {
; push(s,p);
; p=p->lchild;
; }//endwhile
; if (!StackEmpty(s))
; {
; p=pop(s);
; visite(p->data); //访问根结点
; p=p->rchild; //通过下一次循环实现右子树遍历
; }//endif
; }//endwhile
; }//InOrderUnrec
; 3.后序遍历非递归算法
; void postOrder(treenode *head)
; {
; stack<treenode *> st;
; treenode *p=head;
; treenode *pre=null;//指针pre用于指向刚访问完的结点
; while(p)
; {
; while(p)
; {st.push(p);p=p->lchild;}//向左走到尽头
; while(p==null&&!st.IsEmpty())
; {
; p=st.pop();
; if(p->rchild==pre||p->rchild==null)
; {visit();pre=p;p=null;} //当栈顶元素所指结点的右子树空,或刚访问完其右孩子,则访问此结点
; else{st.push(p);p=p->rchild;}//向右一步
; }//while
; }//while
; }//postorder
;===================================================================================
;===================================================================================
;*************************************
.MODEL SMALL
;**********************************
.STACk
;**********************************
.DATA
TREE_ARRAY DB 64 DUP (30H) ;接收保存 节点 初值0
TREE_STORAGE DB 64 DUP (0) ;存储遍历后 节点的次序 用以输出 初值0
TREE_STACK DB 64 DUP (0)
TREE_TEMP DB 32 DUP (0)
MSG_ROOT DB 0AH, 0DH,"Please input the Binary_Tree's root:","$"
MSG_INPUT DB 0AH, 0DH,"Please input ","$"
MSG_LEFT DB "'s left child(no left child press #):","$"
MSG_RIGHT DB "'s right child(no left child press #):","$"
MSG_PRE DB 0AH, 0DH,"PRE_ORDER IS:","$"
MSG_IN DB 0AH, 0DH,"IN_ORDER IS:","$"
MSG_POST DB 0AH, 0DH,"POST_ORDER IS:","$"
;**********************************
.CODE
MAIN PROC FAR
MOV AX , @DATA
MOV DS , AX
CALL INPUTROOT ;输入二叉树程序
CALL INPUTLEFT
MAIN ENDP
;=====================================
INPUTROOT PROC NEAR
MOV AH,09H
LEA DX,MSG_ROOT ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
SUB DI,DI ;初始化 DI 清零
MOV AH,01H
INT 21H ;利用循环 接收二叉树
CMP AL,'#' ;当输入#号 是 结束二叉树的 输入
JE EXIT
INC DI ;自加1，从偏移量1开始，用数组顺序存贮二叉树，节点i的左子比为2i 右子为2i+1
MOV TREE_ARRAY[DI],AL
SUB BX,BX
MOV TREE_STACK[BX],00h
SUB AX,AX
MOV AX,DI
INC BX
MOV TREE_STACK[BX],AL
EXIT: RET
INPUTROOT ENDP
;=====================================
INPUTLEFT PROC NEAR
WY11: MOV AH,09H
LEA DX,MSG_INPUT ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
MOV AH,02H
MOV DL,TREE_ARRAY[DI]
INT 21H
MOV AH,09H
LEA DX,MSG_LEFT
INT 21H
MOV AH,01H
INT 21H
CMP AL,'#'
JE EXIT9
SHL DI,01H
MOV TREE_ARRAY[DI],AL
SUB AX,AX
MOV AX,DI
INC BX
MOV TREE_STACK[BX],AL
JMP WY11
EXIT9: CALL INPUTRIGHT
INPUTLEFT ENDP
;=====================================
INPUTRIGHT PROC NEAR
CMP TREE_STACK[BX],00H
JE EXIT11
MOV AH,09H
LEA DX,MSG_INPUT ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
MOV AH,02H
MOV DL,TREE_ARRAY[DI]
INT 21H
MOV AH,09H
LEA DX,MSG_RIGHT
INT 21H
MOV AH,01H
INT 21H
CMP AL,'#'
JE EXIT10
DEC BX
SHL DI,01H
INC DI
MOV TREE_ARRAY[DI],AL
SUB AX,AX
MOV AX,DI
INC BX
MOV TREE_STACK[BX],AL
CALL INPUTLEFT
EXIT10: DEC BX
SUB AX,AX
MOV AL,TREE_STACK[BX]
MOV DI,AX
CALL INPUTRIGHT
EXIT11: CALL PRE_ORDER ;先序遍历二叉树
INPUTRIGHT ENDP
;=====================================
PRE_ORDER PROC NEAR ;先序遍历程序
SUB DI,DI ;初始化 DI 清零
SUB SI,SI ;初始化 SI 清零
SUB AX,AX
SUB BX,BX
MOV TREE_STACK[BX],00h ;把0送入 栈 此为递归头 当POP 出0时，说明先序遍历已经结束，开始输出先序遍历
INC DI
MOV AL,TREE_ARRAY[DI]
MOV TREE_STORAGE[SI],AL ;根节点进入 TREE_STORAGE数组，TREE_STORAGE数组存放的是 遍历的序列
INC SI
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL ;保存根节点的DI，即偏移量
CALL PRE_ORDERRECURSION ;调RECURSION
PRE_ORDER ENDP
;=====================================
PRE_ORDERRECURSION PROC NEAR
CALL PRE_ORDERLEFT ;调LEFT
CALL PRE_ORDERRIGHT ;调RIGHT
RET
PRE_ORDERRECURSION ENDP
;=====================================
PRE_ORDERLEFT PROC NEAR ;查找左子程序
PRE_ORDERLEFTCHILD: SHL DI,01H ;将DI成2 找其左子
MOV AL,TREE_ARRAY[DI]
CMP AL,30h ;AL中的值和0比较，等于0说明 没有左子，不等于零 有左子
JE EXIT1
MOV TREE_STORAGE[SI],AL ;将左子保存到TREE_STORAGE数组，用以输出
INC SI
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL ;保存当前DI的偏移量
JMP PRE_ORDERLEFTCHILD ;循环找其左子，没有左子，返回RECURSION，开始查找右子
EXIT1: RET
PRE_ORDERLEFT ENDP
;=====================================
PRE_ORDERRIGHT PROC NEAR ;查找右子程序
WY:
MOV AL,TREE_STACK[BX]
MOV DI,AX
DEC BX
CMP DI,0000h
JE EXIT2 ;递归头 AX等于0 表示先序遍历完成，跳EXIT2后，打印先序遍历
SHL DI,01H
INC DI ;开始查找右子 ADD DI,DI和INC DI 相当于 2i+1操作
MOV AL,TREE_ARRAY[DI]
CMP AL,30h ;如果AL等于0表示 无右子继续POP，不等于0 表示有左子
JE WY
MOV TREE_STORAGE[SI],AL
INC SI
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL ;左子入栈
CALL PRE_ORDERRECURSION ;继续调RECURSION 看是否有左子
EXIT2: CALL PRINT
PRE_ORDERRIGHT ENDP
;=====================================
IN_ORDER PROC NEAR
SUB BX,BX
MOV TREE_STACK[BX],00h
SUB DI,DI
INC DI
MOV AL,TREE_ARRAY[DI]
INC BX
SUB AX,AX
MOV AX,DI
MOV TREE_STACK[BX],AL
SUB SI,SI
CALL IN_ORDERRECURSION
IN_ORDER ENDP
;=====================================
IN_ORDERRECURSION PROC NEAR
CALL IN_ORDERLEFT ;调LEFT
CALL IN_ORDERRIGHT ;调RIGHT
RET
IN_ORDERRECURSION ENDP
;=====================================
IN_ORDERLEFT PROC NEAR
IN_ORDERLEFTCHILD:
ADD DI,DI
MOV AL,TREE_ARRAY[DI]
CMP AL,30H
JE WY2
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL
JMP IN_ORDERLEFTCHILD
WY2: RET
IN_ORDERLEFT ENDP
;=====================================
IN_ORDERRIGHT PROC NEAR ;查找右子程序
WY3: MOV AL,TREE_STACK[BX]
MOV DI,AX
DEC BX
CMP DI,0000h
JE EXIT4
MOV AL,TREE_ARRAY[DI]
MOV TREE_STORAGE[SI],AL
INC SI
SHL DI,01H
INC DI
MOV AL,TREE_ARRAY[DI]
CMP AL,30H
JE WY3
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL
CALL IN_ORDERRECURSION
EXIT4: CALL PRINT1
IN_ORDERRIGHT ENDP
;=====================================
POST_ORDER PROC NEAR
SUB SI,SI
SUB BX,BX
SUB BP,BP
MOV TREE_STACK[BX],00h
SUB DI,DI
INC DI
SUB AX,AX
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL
CALL POST_ORDERRECURSION
POST_ORDER ENDP
;=====================================
POST_ORDERRECURSION PROC NEAR
CALL POST_ORDERLEFT ;调LEFT
CALL POST_ORDERRIGHT ;调RIGHT
RET
POST_ORDERRECURSION ENDP
;=====================================
POST_ORDERLEFT PROC NEAR
POST_ORDERLEFTCHILD:
ADD DI,DI
MOV AL,TREE_ARRAY[DI]
CMP AL,30H
JE WY7
MOV AX,DI
INC BX
MOV TREE_STACK[BX],AL
JMP POST_ORDERLEFTCHILD
WY7: RET
POST_ORDERLEFT ENDP
;=====================================
POST_ORDERRIGHT PROC NEAR
MOV AL,TREE_STACK[BX]
MOV DI,AX
DEC BX
CMP DI,0000h
JE EXIT7
MOV CX,DI
CMP TREE_TEMP[BP],CL
JE WY9
SHL DI,01H
INC DI ;开始查找右子 ADD DI,DI和INC DI 相当于 2i+1操作
MOV AL,TREE_ARRAY[DI]
CMP AL,30h
JE WY8
WY10: DEC DI
SHR DI,01H
INC BP
MOV CX,DI
MOV TREE_TEMP[BP],CL
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL
SHL DI,01H
INC DI
INC BX
MOV AX,DI
MOV TREE_STACK[BX],AL
CALL POST_ORDERRECURSION
WY8:
DEC DI
SHR DI,01H
MOV AL,TREE_ARRAY[DI]
MOV TREE_STORAGE[SI],AL
INC SI
CALL POST_ORDERRIGHT
WY9:
SHL DI,01H
INC DI ;开始查找右子 ADD DI,DI和INC DI 相当于 2i+1操作
MOV AL,TREE_ARRAY[DI]
CMP AL,30h
JE WY10
DEC BP
DEC DI
SHR DI,01H
MOV AL,TREE_ARRAY[DI]
MOV TREE_STORAGE[SI],AL
INC SI
CALL POST_ORDERRIGHT
EXIT7: CALL PRINT2
POST_ORDERRIGHT ENDP
;=====================================
PRINT PROC NEAR ;打印先序遍历程序
MOV AH,09H
LEA DX,MSG_PRE ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
SUB SI,SI ;初始化 SI 清零
WY1: MOV AH,02H
MOV DL,TREE_STORAGE[SI]
CMP DL,00h ;数组的值不等于0就 循环输出数组中元素，等于0表示先序遍历输出完毕
JE EXIT3 ;输出完毕后 返回DOS
INT 21H
INC SI
JMP WY1
EXIT3: CALL IN_ORDER
PRINT ENDP
;=====================================
PRINT1 PROC NEAR ;打印先序遍历程序
MOV AH,09H
LEA DX,MSG_IN ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
SUB SI,SI ;初始化 SI 清零
WY5: MOV AH,02H
MOV DL,TREE_STORAGE[SI]
CMP DL,00h ;数组的值不等于0就 循环输出数组中元素，等于0表示先序遍历输出完毕
JE EXIT5 ;输出完毕后 返回DOS
INT 21H
INC SI
JMP WY5
EXIT5: CALL POST_ORDER
PRINT1 ENDP
;=====================================
PRINT2 PROC NEAR ;打印先序遍历程序
MOV AH,09H
LEA DX,MSG_POST ;打印提示语句，让用户 按行出入二叉树的节点，无节点按0
INT 21H
SUB SI,SI ;初始化 SI 清零
WY6: MOV AH,02H
MOV DL,TREE_STORAGE[SI]
CMP DL,00h ;数组的值不等于0就 循环输出数组中元素，等于0表示先序遍历输出完毕
JE EXIT8 ;输出完毕后 返回DOS
INT 21H
INC SI
JMP WY6
EXIT8: CALL RETURN
PRINT2 ENDP
;=====================================
RETURN PROC NEAR
MOV AH , 4CH ;返回DOS
INT 21H
RETURN ENDP
;=====================================
END MAIN ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -