树和二叉树相互转化【源代码】
文章作者：三把刀
assume cs:code,ds:data,ss:stack
data segment
db 'RABC.DE..F...GHK....#'
PTCV db 16 dup(0)
PTCDA db 128 dup(0)
PTCDB db 128 dup(0)
PTCDC db 128 dup(0)
data ends
stack segment stack
dw 32 dup(0)
stack ends
code segment
start:
mov ax,data
mov ds,ax
mov si,0
mov ax,stack
mov ss,ax
mov sp,0
call PToCTree
call CToPTree
call ShowConInter
mov ax,4c00h
int 21h
;-----------------------------------PToCTree start
;ds:si
PToCTree:
;生成一个树放在本方法PTCData空间中
;PTCDA[0]存储数组的索引值
;PTCDB存储转换之后的二叉树，存储数据依次是节点，左节点索引，右节点索引
push ax
push di
push si
push bx
push dx
mov di,0
mov byte ptr PTCV[0],0
mov al,[si]
mov PTCDA[di],al
mov byte ptr PTCDA[di + 1],-1
mov byte ptr PTCDA[di + 3],1
add di,8
inc si
PTCS:
mov al,[si]
mov PTCDA[di],al
mov al,PTCV[0]
mov PTCDA[di + 1],al
mov PTCDA[di + 3],1
add di,8
inc si
cmp byte ptr [si],'#'
je PTCC
cmp byte ptr [si],'.'
jne PTCS
PTCS1:
add byte ptr PTCV[0],8
inc si
cmp byte ptr [si],'#'
je PTCC
cmp byte ptr [si],'.'
je PTCS1
jmp PTCS
PTCC:
;生成树结束
mov byte ptr PTCDA[di],'#'
mov bx,offset PTCDA
call PostTree
;-----------------------------------------------生成树的先序遍历
;call ClearScreen
;mov bx,offset PTCDA
;mov dh,6
;mov dl,0
;mov al,20
;call TPreTra
;-----------------------------------------------生成树结束
;--------------------------------------------------------------------------树转换成二叉树
mov al,PTCDA[0]
mov PTCDB[0],al
mov byte ptr PTCDB[7],0
mov di,0
mov si,0
mov bx,0
PTCCS1:
push bx
mov bx,offset PTCDA
call PTCF1
pop bx
cmp word ptr PTCV[0],-1
je PTCBackDataA
;左子树
mov al,PTCV[0]
mov ah,PTCV[1]
mov di,ax
add si,8
mov ax,si
mov byte ptr PTCDB[bx + 1],al
mov al,PTCDA[di]
mov PTCDB[si],al
mov byte ptr PTCDB[si + 3],bl
mov al,PTCDB[bx + 7]
inc al
mov PTCDB[si + 7],al
mov bx,si
jmp PTCCS1
PTCBackDataA:
;右子树
;回溯
mov byte ptr PTCDB[bx + 1],-1
PTCBackDataB:
mov ax,0
mov al,PTCDA[di + 1]
mov di,ax
push bx
mov bx,offset PTCDA
call PTCF1
pop bx
cmp word ptr PTCV[0],-1
je PTCNodeOver
mov al,PTCV[0]
mov ah,PTCV[1]
mov di,ax
add si,8
mov al,PTCDA[di]
mov PTCDB[si],al
mov ax,si
mov byte ptr PTCDB[bx + 2],al
mov byte ptr PTCDB[si + 3],bl
mov al,PTCDB[bx + 7]
inc al
mov PTCDB[si + 7],al
mov bx,si
jmp PTCCS1
PTCNodeOver:
mov byte ptr PTCDB[bx + 2],-1
call PTCF2
mov ax,0
mov al,PTCDA[di + 1]
cmp byte ptr PTCDA[di + 1],-1
je PTCReturn
jmp PTCBackDataB
PTCReturn:
mov byte ptr PTCDB[2],-1
mov byte ptr PTCDB[3],-1
mov byte ptr PTCDB[si + 8],'#'
;------------------------------------------------先序遍历二叉树
mov bx,offset PTCDA
call ResumeSign
;mov bx,offset PTCDB
;mov dh,6
;mov dl,0
;mov al,60
;call BTPreTra
;------------------------------------------------遍历结束
pop dx
pop bx
pop si
pop di
pop ax
ret
;--------function1 start
;在ds:[bx]指向的数据中查找当前节点di的孩子
PTCF1:
push si
push ax
mov si,di
add si,8
PTCF1S1:
cmp byte ptr [bx + si],'#'
je PTCF1ReturnB
mov ax,0
mov al,[bx + si + 1]
cmp ax,di
je PTCF1ReturnA
add si,8
jmp PTCF1S1
PTCF1S2:
add si,8
jmp PTCF1S1
PTCF1ReturnA:
cmp byte ptr [bx + si + 2],1
je PTCF1S2
mov byte ptr [bx + si + 2],1
mov word ptr PTCV[0],si
jmp PTCF1Return
PTCF1ReturnB:
mov word ptr PTCV[0],-1
PTCF1Return:
pop ax
pop si
ret
;--------function1 end
;--------function2 start
PTCF2: ;查找当前节点的父
push ax
PTCF2S:
sub bx,8
mov ax,0
mov al,PTCDA[di]
cmp al,PTCDB[bx]
je PTCF2Return
jmp PTCF2S
PTCF2Return:
pop ax
ret
;--------function2 end
;-----------------------------------PToCTree end
;-----------------------------------CToPTree start
;-------------------------------------------------------------------------二叉树向树的转换
CToPTree:
push ax
push bx
push di
push si
mov bx,0
mov di,0
mov si,0
mov al,PTCDB[bx]
mov PTCDC[di],al
mov byte ptr PTCDC[di + 1],-1
mov byte ptr PTCDC[di + 3],1
CTPS:
cmp byte ptr PTCDB[bx + 1],-1
je CTPS1
mov ax,0
mov al,PTCDB[bx + 1]
mov bx,ax
add si,8
mov al,PTCDB[bx]
mov PTCDC[si],al
mov ax,di
mov PTCDC[si + 1],al
mov di,si
mov byte ptr PTCDC[di + 3],1
jmp CTPS
CTPS1:
cmp byte ptr PTCDB[bx + 2],-1
je CTPS2
mov ax,0
mov al,PTCDB[bx + 2]
mov bx,ax
add si,8
mov al,PTCDB[bx]
mov PTCDC[si],al
mov al,PTCDC[di + 1]
mov PTCDC[si + 1],al
mov di,si
mov byte ptr PTCDC[di + 3],1
jmp CTPS
CTPS2:
mov ax,0
mov al,PTCDC[di + 1]
mov di,ax
call CTPF1
cmp byte ptr PTCDC[di + 1],-1
je CTPReturn
jmp CTPS1
CTPReturn:
mov byte ptr PTCDC[si + 8],'#'
;-------------------------------转成树后的先序遍历
mov bx,offset PTCDC
call PostTree
;mov bx,offset PTCDC
;mov dh,6
;mov dl,0
;mov al,20
;call TPreTra
pop si
pop di
pop bx
pop ax
ret
;--------function1 start
CTPF1: ;查找
push ax
CTPF1S:
sub bx,8
mov al,PTCDC[di]
cmp al,PTCDB[bx]
je CTPF1Return
jmp CTPF1S
CTPF1Return:
pop ax
ret
;--------function1 end
;-----------------------------------CToPTree end
;--------恢复树的访问标志位
ResumeSign:
push di
push ax
mov di,0
RSS:
cmp byte ptr [bx + di],'#'
je RSReturn
mov al,PTCV[7]
mov [bx + di + 2],al
mov byte ptr [bx + di + 4],0
add di,8
jmp RSS
RSReturn:
pop ax
pop di
ret
;--------结束
;-----------------------------------PostTree start
;树的后序遍历
PostTree:
push di
push si
push ax
push bx
mov di,0
mov si,8
PTS:
cmp byte ptr [bx + si],'#'
je PTNO
mov ax,0
mov al,[bx + si + 1]
cmp ax,di
je PTS1
add si,8
jmp PTS
PTS2:
add si,8
jmp PTS
PTS1:
cmp byte ptr [bx + si + 2],1
je PTS2
mov di,si
mov si,8
jmp PTS
PTNO:
cmp byte ptr [bx + di + 1],-1
je PTSReturn
mov byte ptr [bx + di + 2],1
push ax
cmp byte ptr [bx + di + 3],1
jna PTNS3
dec byte ptr [bx + di + 3]
PTNS3:
mov ax,0
mov al,[bx + di + 1]
mov si,ax
mov al,[bx + di + 3]
add [bx + si + 3],al
mov di,si
mov si,8
pop ax
jmp PTS
PTSReturn:
;恢复访问标志位
dec byte ptr [bx + 3]
call ResumeSign
PTNOut:
pop bx
pop ax
pop si
pop di
ret
;-----------------------------------PostTree end
;-----------------------------------TPreTra start
;树的先序遍历
;dh,dl开始画的行列
;al权值
;di当前节点
TPreTra:
push di
push dx
push ax
push cx
mov di,0
mov PTCV[6],dh
mov PTCV[7],dl
mov [bx + di + 4],dl
mov [bx + di + 5],dl
mov [bx + di + 6],al
mov ah,0
mov dh,2
div dh
add al,dl
mov [bx + di + 7],al
mov dl,al
mov dh,PTCV[6]
;打印根
push bx
mov bh,[bx + di]
mov bl,1
mov cl,00000111B
call print
pop bx
TPTS:
call PTCF1
cmp word ptr PTCV[0],-1
je TPTS1
mov al,PTCV[0]
mov ah,PTCV[1]
mov di,ax
call PrintNowNode
jmp TPTS
TPTS1:
cmp byte ptr [bx + di + 1],-1
je TPTReturn
mov ax,0
mov al,[bx + di + 1]
mov di,ax
jmp TPTS
TPTReturn:
call ResumeSign
pop cx
pop ax
pop dx
pop di
ret
;-----------------------------------TPreTra end
;--------PrintNowNode start
;打印当前节点
;计算当前节点的深度，得出画的行
;[bx + di]执行的位置
;dh,dl行列
PrintNowNode:
push ax
push cx
push di
mov cl,0
mov dh,PTCV[6]
PNNS:
cmp byte ptr [bx + di + 1],-1
je PNNS1
mov ax,0
mov al,[bx + di + 1]
mov di,ax
inc cl
jmp PNNS
PNNS1:
add cl,cl
add dh,cl
pop di
pop cx
pop ax
;计算画的列
push si
push ax
mov cl,dh
;求孩子的权值
mov dh,[bx + di + 3]
mov ax,0
mov al,[bx + di + 1]
mov si,ax
mov ax,0
mov al,[bx + si + 3]
div dh
mov dh,al
mov ax,0
mov al,[bx + si + 6]
div dh
cmp ah,5
jb PNNS2
inc al
PNNS2:
mov [bx + di + 6],al
;孩子画的位置
mov dl,[bx + si + 4]
add dl,[bx + si + 5]
mov [bx + di + 5],dl
add [bx + si + 4],al
mov ah,0
mov dh,2
div dh
cmp ah,5
jb PNNS3
inc al
PNNS3:
add dl,al
mov dh,cl
pop ax
pop si
push bx
mov [bx + di + 7],dl
mov bh,[bx + di]
mov bl,1
mov cl,00000111B
call print
pop bx
push di
push dx
push bx
dec dh
mov ch,dl
mov ax,0
mov al,[bx + di + 1]
mov di,ax
mov dl,[bx + di + 7]
mov bh,ch
call ShowLine
pop bx
pop dx
pop di
ret
;--------PrintNowNode end
;-----------------------------------BTPreTra start
;二叉树的先序遍历
BTPreTra:
push di
push ax
push cx
push dx
push bp
mov di,0
push di
mov PTCV[6],dh
mov byte ptr [bx + di + 4],al
mov byte ptr [bx + di + 5],dl
mov ah,0
mov dh,2
div dh
add dl,al
mov byte ptr [bx + di + 6],dl
mov dh,PTCV[6]
;打印根
push bx
mov bh,[bx + di]
mov bl,1
mov cl,00000111B
call print
pop bx
BTPTS:
cmp byte ptr [bx + di + 1],-1
je BTPTS1
mov ax,0
mov al,[bx + di + 1]
mov di,ax
push di
;打印左子树
push bx
mov ax,0
mov al,[bx + di + 3]
mov si,ax
mov ax,0
mov al,[bx + si + 4]
mov dh,2
div dh
mov [bx + di + 4],al
mov ah,0
mov dh,2
div dh
mov dl,[bx + si + 5]
mov [bx + di + 5],dl
cmp al,0
je BTPS
jmp BTPS1
BTPS:
sub al,1
BTPS1:
add dl,al
mov [bx + di + 6],dl
mov dh,[bx + di + 7]
add dh,dh
add dh,PTCV[6]
mov bh,[bx + di]
mov bl,1
mov cl,00000111B
call print
pop bx
push di
push dx
push bx
dec dh
mov ch,dl
mov ax,0
mov al,[bx + di + 3]
mov di,ax
mov dl,[bx + di + 6]
mov bh,ch
call ShowLine
pop bx
pop dx
pop di
jmp BTPTS
BTPTS1:
pop ax
cmp byte ptr [bx + di + 2],-1
je BTPTS2
mov ax,0
mov al,[bx + di + 2]
mov di,ax
push di
;打印右子树
push bx
mov ax,0
mov al,[bx + di + 3]
mov si,ax
mov ax,0
mov al,[bx + si + 4]
mov dh,2
div dh
mov [bx + di + 4],al
mov dl,[bx + si + 5]
add dl,al
mov [bx + di + 5],dl
mov ah,0
mov dh,2
div dh
cmp al,0
je BTPS3
jmp BTPS4
BTPS3:
mov dl,[bx + si + 6]
mov al,1
BTPS4:
add dl,al
mov [bx + di + 6],dl
mov dh,[bx + di + 7]
add dh,dh
add dh,PTCV[6]
mov bh,[bx + di]
mov bl,1
mov cl,00000111B
call print
pop bx
push di
push dx
push bx
dec dh
mov ch,dl
mov ax,0
mov al,[bx + di + 3]
mov di,ax
mov dl,[bx + di + 6]
mov bh,ch
call ShowLine
pop bx
pop dx
pop di
jmp BTPTS
BTPTS2:
cmp byte ptr [bx + di + 3],-1
je BTPreTraReturn
mov bp,sp
mov di,ss:[bp]
jmp BTPTS1
BTPreTraReturn:
pop bp
pop dx
pop cx
pop ax
pop di
ret
;-----------------------------------BTPreTra end
;-----------------------------------print start
;在指定位置打印字符
;cl颜色值
;dh,dl传行列
;bh传打印的数据
;bl传功能号
;0ds:si传数据段的位置
;1bh传打印的数据
print:
push ax
push di
push si
push es
push dx
push bx
mov ax,0b800h
mov es,ax
mov ax,0
mov al,160
mul dh
mov di,ax
mov ax,2
mul dl
add di,ax
cmp bl,0
je show0
cmp bl,1
je show1
jmp return
show0:
mov al,[si]
mov es:[di],al
mov es:[di + 1],cl
inc si
cmp byte ptr [si],'#'
je return
add di,2
jmp show0
show1:
mov es:[di],bh
mov es:[di + 1],cl
return:
pop bx
pop dx
pop es
pop si
pop di
pop ax
ret
;-----------------------------------print end
;-----------------------------------delay start
delay:
push ax ;延时
push dx
mov dx,2000h
mov ax,0
ds1:
sub ax,1
sbb dx,0
cmp ax,0
jne ds1
cmp dx,0
jne ds1
pop dx
pop ax
ret
;-----------------------------------delay end
;--------------------------------ClearScreen start
;清屏
ClearScreen:
push bx
push es
push cx
push ax
mov ax,0500h
int 10h
mov bx,0b800h
mov es,bx
mov bx,0
mov cx,2000
CLS:
mov byte ptr es:[bx],' '
add bx,2
loop CLS
pop ax
pop cx
pop es
pop bx
ret
;--------------------------------ClearScreen end
;-------------------------------ShowLine start
;dh行号
;dl起始列父节点的列，bh终止列子节点的列
ShowLine:
push cx
push dx
push bx
cmp dl,bh
je SLIN1
jmp SLIN2
SLIN1:
mov byte ptr PTCV[0],1
mov bh,179
jmp SLSS
SLIN2:
cmp dl,bh
ja SLIN3 ;起始位置大于终止位置发生跳转
mov al,bh
sub al,dl
mov bh,192
mov byte ptr PTCV[0],2
jmp SLIN
SLIN3:
mov al,dl
sub al,bh
mov bh,217
mov byte ptr PTCV[0],3
SLIN:
cmp al,3
jb SLSS1
sub al,2
inc al
mov cx,0
mov cl,al
jmp SLSS
SLSS1:
cmp al,1
ja SLSS2
mov cx,0
mov byte ptr PTCV[1],1
jmp SLSS
SLSS2:
mov cx,1
mov byte ptr PTCV[1],2
SLSS:
push cx
mov bl,1
mov cl,00000010B
call print
pop cx
cmp byte ptr PTCV[0],2
je SLSD1
cmp byte ptr PTCV[0],3
je SLSD2
jmp SLSReturn
SLSD1:
inc dl
cmp byte ptr PTCV[1],1
je SLSO1
SLS1:
push cx
mov bl,1
mov bh,196
mov cl,00000010B
call print
inc dl
pop cx
loop SLS1
SLSO1:
mov bh,191
jmp SLS3
SLSD2:
dec dl
cmp byte ptr PTCV[1],1
je SLSO2
SLS2:
push cx
mov bl,1
mov bh,196
mov cl,00000010B
call print
dec dl
pop cx
loop SLS2
SLSO2:
mov bh,218
SLS3:
mov bl,1
mov cl,00000010B
call print
SLSReturn:
pop bx
pop dx
pop cx
ret
;-------------------------------ShowLine end
;-------------------------------ShowConInter start
;控制面板
ShowConInter:
jmp ShowInterface
CUES dw CUE0,CUE1,CUE2,CUE3
CUE0 db "Copyright (c) 2007 www.asmedu.net#"
CUE1 db "Tree to Bintree#"
CUE2 db "Bintree to Tree#"
CUE3 db "Use ",24," and ",25," select.Press ESC to exit#"
INDEX db 0,0
ShowInterface:
push ax
push bx
push ds
call ClearScreen
mov ax,data
mov ds,ax
mov bx,offset PTCDC
mov dh,6
mov dl,0
mov al,40
call TPreTra
mov byte ptr INDEX[0],0
SIFS:
mov ax,cs
mov ds,ax
mov bl,0
mov dh,0
mov dl,0
mov si,CUES[0]
mov cl,00000111B
call print
mov dh,18
mov dl,50
mov si,CUES[2]
cmp byte ptr INDEX[0],0
je SIFS1
mov cl,00000111B
jmp SIFS2
SIFS1:
mov cl,00000010B
SIFS2:
call print
mov dh,20
mov si,CUES[4]
cmp byte ptr INDEX[0],1
je SIFS3
mov cl,00000111B
jmp SIFS4
SIFS3:
mov cl,00000010B
SIFS4:
call print
mov dh,22
mov dl,30
mov si,CUES[6]
mov cl,00000011B
call print
mov ah,0
int 16h
cmp ah,01h
je ShowInterReturn
;检测上键
cmp ah,48h
jne SIFS5
cmp byte ptr INDEX[0],1
jb SIFS6
dec byte ptr INDEX[0]
jmp SIFS5
SIFS6:
mov byte ptr INDEX[0],1
SIFS5:
;检测下键
cmp ah,50h
jne SIFS7
cmp byte ptr INDEX[0],1
jb SIFS8
dec byte ptr INDEX[0]
jmp SIFS7
SIFS8:
mov byte ptr INDEX[0],1
SIFS7:
;检测回车键
cmp ah,1ch
jne SIFS9
call ClearScreen
mov ax,data
mov ds,ax
cmp byte ptr INDEX[0],0
jne SIFS10
mov bx,offset PTCDC
mov dh,6
mov dl,0
mov al,40
call TPreTra
call ClearScreen
mov bx,offset PTCDB
call BTPreTra
jmp SIFS9
SIFS10:
mov dh,6
mov dl,0
mov al,40
mov bx,offset PTCDC
call TPreTra
SIFS9:
jmp SIFS
ShowInterReturn:
call ClearScreen
pop ds
pop bx
pop ax
ret
;-------------------------------ShowConInter end
code ends
end start
发表日期：09/09/21 00:00
网友评论(0)
当前1/1页 首页 上一页下一页 尾页