NASMx64汇编二叉树程序编译错误及功能修复与扩展需求

原问题核心修复点 #

原代码存在三个致命问题：

• 数组空间不足：仅定义单个16位元素，无法存储多节点二叉树
• 8/16位操作数不匹配：删除逻辑中存在16位寄存器向8位寄存器赋值的错误指令
• 初始元素数量不足：仅初始化3个元素，不满足任务要求的至少4个

完整修复代码 #

%include "io.inc"
section .data
    ; 分配100个16位空间存储节点：BH存节点值，BL高4位存左子索引、低4位存右子索引
    array: times 100 dw 0
    space_str: db " ", 0
    new_line: db 0xA, 0

section .text
global main
main:
    mov ebp, esp; 调试用栈基址
    xor eax, eax
    xor esi, esi
 
    call init          ; 初始化4个初始元素
    mov eax, 19        ; 新增元素19
    call addElem
    PRINT_STRING "初始树（中序遍历）："
    call showTree
    PRINT_STRING new_line

    mov eax, 19        ; 查找元素19
    call searchElem
    jz search_not_found_19
    PRINT_STRING "找到元素19"
    PRINT_STRING new_line
    jmp search_end_19
search_not_found_19:
    PRINT_STRING "未找到元素19"
    PRINT_STRING new_line
search_end_19:

    mov eax, 19        ; 删除元素19
    call removeElem
    PRINT_STRING "删除19后的树（中序遍历）："
    call showTree
    PRINT_STRING new_line

    mov eax, 10        ; 查找元素10
    call searchElem
    jz search_not_found_10
    PRINT_STRING "找到元素10"
    PRINT_STRING new_line
    jmp search_end_10
search_not_found_10:
    PRINT_STRING "未找到元素10"
    PRINT_STRING new_line
search_end_10:

    PRINT_STRING "树的升序输出："
    call sortedOutput  ; 新增升序输出函数
    PRINT_STRING new_line

    ; 输入输出示例
    PRINT_STRING "输入16进制数："
    GET_HEX 2, ax
    PRINT_STRING "十进制结果："
    PRINT_DEC 2, ax
    PRINT_STRING new_line
    ret
    
; 初始化4个元素：8、3、10、15
init:
    mov al, 8
    call addElem
    mov al, 3
    call addElem
    mov al, 10
    call addElem 
    mov al, 15
    call addElem
    ret
    
; 添加元素：AL存待添加值，ESI为当前节点索引（初始调用ESI=0）
addElem:
    mov bx, [array + esi*2]
    test bx, bx
    jz add_null       ; 当前节点为空，直接赋值
    cmp bh, al
    je add_equal      ; 元素已存在，直接返回
    jg add_goRight    ; 当前值更大，走右子树
    jmp add_goLeft    ; 当前值更小，走左子树

add_null:
    mov bh, al        ; BH存储节点值
    xor bl, bl        ; 初始化子节点索引为0
    mov [array + esi*2], bx
    ret

add_equal:
    ret

add_goRight:
    mov cl, bl
    and cl, 0x0F      ; 取出右子索引（BL低4位）
    cmp cl, 0
    je add_createRight
    movzx esi, cl
    call addElem
    ret

add_createRight:
    ; 找到第一个空节点位置
    mov ecx, 1
find_right_empty:
    cmp word [array + ecx*2], 0
    jz found_right_node
    inc ecx
    jmp find_right_empty
found_right_node:
    ; 初始化新节点
    mov bh, al
    xor bl, bl
    mov [array + ecx*2], bx
    ; 更新当前节点的右子索引
    mov bx, [array + esi*2]
    and bl, 0xF0
    or bl, cl
    mov [array + esi*2], bx
    ret

add_goLeft:
    mov cl, bl
    shr cl, 4
    and cl, 0x0F      ; 取出左子索引（BL高4位）
    cmp cl, 0
    je add_createLeft
    movzx esi, cl
    call addElem
    ret

add_createLeft:
    ; 找到第一个空节点位置
    mov ecx, 1
find_left_empty:
    cmp word [array + ecx*2], 0
    jz found_left_node
    inc ecx
    jmp find_left_empty
found_left_node:
    ; 初始化新节点
    mov bh, al
    xor bl, bl
    mov [array + ecx*2], bx
    ; 更新当前节点的左子索引
    mov bx, [array + esi*2]
    and bl, 0x0F
    shl cl, 4
    or bl, cl
    mov [array + esi*2], bx
    ret

; 删除元素：AL存待删除值，返回时ZF=1表示未找到，ZF=0表示删除成功
removeElem:
    mov esi, 0
remove_loop:
    mov bx, [array + esi*2]
    test bx, bx
    jz remove_notFound
    cmp bh, al
    je remove_current
    jg remove_goRight
    jmp remove_goLeft

remove_goRight:
    mov cl, bl
    and cl, 0x0F
    cmp cl, 0
    je remove_notFound
    movzx esi, cl
    jmp remove_loop

remove_goLeft:
    mov cl, bl
    shr cl, 4
    and cl, 0x0F
    cmp cl, 0
    je remove_notFound
    movzx esi, cl
    jmp remove_loop

remove_current:
    ; 获取左右子索引
    mov cl, bl
    mov dl, cl
    shr dl, 4
    and dl, 0x0F      ; DL=左子索引
    and cl, 0x0F      ; CL=右子索引

    ; 无子女情况：直接清空节点
    test dl, dl
    jnz remove_has_left
    test cl, cl
    jnz remove_has_right
    xor bx, bx
    mov [array + esi*2], bx
    jmp remove_found

    ; 仅有左子女：左子节点替换当前节点
remove_has_left:
    mov bx, [array + dl*2]
    mov [array + esi*2], bx
    xor bx, bx
    mov [array + dl*2], bx
    jmp remove_found

    ; 仅有右子女：右子节点替换当前节点
remove_has_right:
    mov bx, [array + cl*2]
    mov [array + esi*2], bx
    xor bx, bx
    mov [array + cl*2], bx
    jmp remove_found

remove_found:
    xor eax, eax      ; ZF=0表示删除成功
    ret

remove_notFound:
    xor eax, eax
    inc eax           ; ZF=1表示未找到
    ret
 
; 中序遍历输出树结构
showTree:
    mov bx, [array + esi*2]
    test bx, bx
    jz show_end
    ; 遍历左子树
    mov cl, bl
    shr cl, 4
    and cl, 0x0F
    cmp cl, 0
    je show_no_left
    push esi
    movzx esi, cl
    call showTree
    pop esi
show_no_left:
    ; 输出当前节点
    movzx eax, bh
    PRINT_DEC 1, eax
    PRINT_STRING space_str
    ; 遍历右子树
    mov cl, bl
    and cl, 0x0F
    cmp cl, 0
    je show_no_right
    push esi
    movzx esi, cl
    call showTree
    pop esi
show_no_right:
show_end:
    ret
 
; 查找元素：AL存待查找值，返回时ZF=1表示未找到，ZF=0表示找到
searchElem:
    mov esi, 0
search_loop:
    mov bx, [array + esi*2]
    test bx, bx
    jz search_notFound
    cmp bh, al
    je search_found
    jg search_goRight
    jmp search_goLeft

search_goRight:
    mov cl, bl
    and cl, 0x0F
    cmp cl, 0
    je search_notFound
    movzx esi, cl
    jmp search_loop

search_goLeft:
    mov cl, bl
    shr cl, 4
    and cl, 0x0F
    cmp cl, 0
    je search_notFound
    movzx esi, cl
    jmp search_loop

search_found:
    xor eax, eax      ; ZF=0表示找到
    ret

search_notFound:
    xor eax, eax
    inc eax           ; ZF=1表示未找到
    ret

; 新增：升序输出（利用二叉搜索树中序遍历天然升序的特性）
sortedOutput:
    mov esi, 0
sorted_loop:
    mov bx, [array + esi*2]
    test bx, bx
    jz sorted_end
    ; 遍历左子树（值更小）
    mov cl, bl
    shr cl, 4
    and cl, 0x0F
    cmp cl, 0
    je sorted_no_left
    push esi
    movzx esi, cl
    call sortedOutput
    pop esi
sorted_no_left:
    ; 输出当前节点
    movzx eax, bh
    PRINT_DEC 1, eax
    PRINT_STRING space_str
    ; 遍历右子树（值更大）
    mov cl, bl
    and cl, 0x0F
    cmp cl, 0
    je sorted_no_right
    push esi
    movzx esi, cl
    call sortedOutput
    pop esi
sorted_no_right:
sorted_end:
    ret

功能说明 #

1. 初始元素：init函数初始化8、3、10、15四个元素，满足任务要求
2. 升序输出：新增sortedOutput函数，基于二叉搜索树中序遍历特性，直接输出从小到大的节点值，无需额外排序算法
3. 修复编译错误：调整节点存储结构，避免8位/16位操作数不匹配问题，扩展数组空间解决节点存储不足
4. 完善核心功能：修复删除逻辑，实现三种删除场景的正确处理，完善查找、添加功能的鲁棒性

内容的提问来源于stack exchange，提问作者Hyde