postb.asm

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

;二叉树的后根遍历算法。
;
;                 A
;               /  \
;             /      \
;           B          C
;         /  \        /
;       D      E     F
;      / \    /     / \
;     G   H  I     J   K
;
STACK	EQU	1FH	;用户堆栈所在页面。
BOTTOM	EQU	00H	;用户堆栈栈底单元。
TOP	DATA	3EH	;用户堆栈栈顶指针。
TREE	EQU	20H	;二叉树存放的片外RAM页面。
OUT	EQU	21H	;被访问节点信息输出存放的片外RAM页面。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	SP,#5FH	;设置足够大的系统堆栈空间。
	MOV	DPTR,#DATS;将二叉树的结构信息存放到片外ＲＡＭ中。
	MOV	P2,#TREE
	MOV	R0,#0
	MOV	R2,#32
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	MOV	DPH,#OUT;指向输出存放节点信息的片外RAM页面。
	MOV	DPL,#0
	MOV	R2,#0
	CLR	A
CLEAR:	MOVX	@DPTR,A	;初始化输出区。
	INC	DPTR
	DJNZ	R2,CLEAR
	MOV	P2,#TREE;指向二叉树存放页面。
	MOV	R0,#0
	MOV	DPH,#OUT;指向输出存放节点信息的片外RAM页面。
	MOV	DPL,#0
	MOVX	A,@R0	;读取二叉树有效节点总数。
	MOVX	@DPTR,A	;存放到输出区的00H单元。
	INC	R0	;指向根节点。
	INC	DPTR	;指向输出区第一个存放位置。
	JZ	STOP	;如果是空树，则结束访问。
	MOV	SP,#5FH	;设置足够大的系统堆栈空间。
	LCALL	SETNULL	;初始化用户堆栈。
	LCALL	POST	;从全树的根节点出发，调用后根遍历算法。
STOP:	LJMP	STOP	;遍历顺序为GHDIEBJKFCA。

DATS:	DB	0BH,41H,42H,43H
	DB	44H,45H,46H,00H
	DB	47H,48H,49H,00H
	DB	4AH,4BH,00H,00H
	DB	0,0,0,0
	DB	0,0,0,0
	DB	0,0,0,0
	DB	0,0,0,0

POST:	MOVX	A,@R0	;读取当前节点。
	JZ	POSTEND	;是虚节点则返回。
	MOV	A,R0	;取当前节点的编号。
	JB	ACC.7,POST1;已假定第八层是最底层，没有子树。
	LCALL	DPUSH	;将当前节点编号压入用户堆栈进行保护。
	CLR	C	;计算左孩子的编号（2×ｎ）。
	RLC	A
	MOV	R0,A	;存放左孩子的编号。
	LCALL	POST	;首先按后根遍历算法访问左子树（递归调用）。
	LCALL	DPOP	;取出保存的节点编号。
	LCALL	DPUSH	;继续进行保护。
	SETB	C	;计算右孩子的编号（2×ｎ＋１）。
	RLC	A
	MOV	R0,A	;存放右孩子的编号。
	LCALL	POST	;然后按后根遍历算法访问右子树（递归调用）。
	LCALL	DPOP	;取出保存的节点编号。
	MOV	R0,A	;存放当前节点的编号。
POST1:	MOVX	A,@R0	;读取当前节点。
	MOVX	@DPTR,A	;保存到输出区，最后完成访问根节点的目的。
	INC	DPTR	;调整输出指针。
POSTEND:RET		;返回。

SETNULL:MOV	A,#BOTTOM;初始化空栈，取栈底单元位置。
	MOV	TOP,A	;使栈顶指针指向栈底。
	RET		;设置好空栈。

DPUSH:	INC	TOP	;新栈顶。
	PUSH	DPH
	PUSH	DPL
	MOV	DPH,#STACK;取堆栈所在页面。
	MOV	DPL,TOP	;取栈顶单元位置。
	MOVX	@DPTR,A	;数据压入栈顶。
	POP	DPL
	POP	DPH
	RET		;结束。

DPOP:	PUSH	DPH
	PUSH	DPL
	MOV	DPH,#STACK;取堆栈所在页面。
	MOV	DPL,TOP	;取栈顶单元。
	MOVX	A,@DPTR	;取出栈顶元素。
	DEC	TOP	;指向新的栈顶。
	POP	DPL
	POP	DPH
	RET		;结束。
	END