在裸机上长出一棵树：用 x86-32 汇编从零实现 B 树-育师

平台：Linux x86-32 / ELF32，NASM 语法，全程裸int 0x80syscall，不链接 libc。
汇编源码内的注释全部使用俄语——纯粹是自我施加的额外难度，逼自己在写平衡树逻辑的同时，还要用第二语言把每一行的意图讲清楚。
全文代码均已在本地用nasm -f elf32汇编、ld -m elf_i386链接、qemu-i386实际运行验证，文中贴出的输出都是真实跑出来的，不是臆想的伪代码。

0. 为什么要干这件事

数据结构教科书里，B 树永远是"稍微复杂一点"的那一档：它不像链表、栈那样一眼看穿内存布局，也不像红黑树那样有大量现成的伪代码可以照抄——CLRS 里的 B-TREE-INSERT、B-TREE-SPLIT-CHILD 是用高级语言的思维写的（数组、下标、结构体字段），一旦要把它们摊平到寄存器和裸内存地址上，会暴露出很多平时被高级语言悄悄兜住的细节：

节点里到底怎么存"孩子指针数组"和"关键字数组"，偏移量怎么算，会不会算错一个*4；
没有malloc，节点从哪来——自己写一个极简的池分配器；
递归函数（split_child会调insert_nonfull，insert_nonfull又会递归调自己）在纯汇编里怎么保证栈平衡、寄存器不被子调用踩掉；
一个逻辑标志位（“是否是叶子节点”）如果方向写反,不会报编译错误，只会在某次分裂之后安静地把内存踩烂,然后在几百条指令之后才 segfault——这是本文后面会讲的真实翻车现场。

这些坑,在 C/C++/Python 里几乎不可见,但在汇编里全部会现出原形。写完这一遍之后,对"B 树为什么这样设计"的理解会比看十遍教科书伪代码更深。

1. B 树复习:我们要实现的是什么

B 树是一种自平衡的多路搜索树,专为"读写块设备"场景设计(数据库、文件系统索引都在用)。核心参数是最小度数t,它约束了每个节点能装多少关键字:

每个非根节点至少有t - 1个关键字,至多有2t - 1个;
每个内部节点的孩子数 = 关键字数 + 1,所以孩子数区间是[t, 2t];
所有叶子节点深度相同(这是"平衡"的来源);
节点内的关键字始终保持有序,第i个孩子子树里的所有关键字都落在keys[i-1]和keys[i]之间。

本文选择t = 2,也就是每个节点最多 3 个关键字、最多 4 个孩子——这是能装下的最小非平凡阶数,分裂逻辑最密集,最适合拿来练手(阶数越大,节点内部的搬移代码量越大,但算法逻辑是一样的)。

插入的核心技巧是**“预防式分裂”(proactive splitting):不是插入完了发现超员再往回处理,而是自顶向下走的路上,只要即将进入的孩子节点已经满员(n == 2t-1),就先把它分裂掉,再决定往左半还是右半继续走。这样保证了整个插入过程是单趟(one-pass)**,不需要任何回溯——这个性质对汇编实现极其友好,因为它意味着我们不需要维护一个"父节点栈"来做事后调整,递归的天然函数调用栈就够用了。

2. 内存布局:节点长什么样

没有struct关键字,没有malloc。一切都要自己摆。节点是这样的定长布局(共 36 字节):

偏移量 字段 大小 +0 leaf 4 字节 ; 1 = 是叶子, 0 = 内部节点 +4 n 4 字节 ; 当前存了几个关键字 +8 keys[0..2] 12 字节 ; 最多 3 个关键字 (2t-1, t=2) +20 children[0..3] 16 字节 ; 最多 4 个孩子指针 (2t)

为什么不做成变长节点(按实际关键字数分配)?因为变长意味着需要动态内存管理——而这次的自我约束是"不依赖标准库、不写通用堆分配器"。固定 36 字节的好处是可以用一个静态数组当对象池,分配变成一次乘法加一次加法:

%define NODE_SIZE 36 %define MAX_NODES 64 section .bss pool resb NODE_SIZE * MAX_NODES ; узел = 36 байт, пул = 64 узла next_free resd 1 ; индекс следующего свободного слота

alloc_node就是个 bump allocator——只增不减,没有free(现实中的 B 树删除操作需要回收节点,但这次先只做插入 + 查找,删除是留给"下一篇"的坑):

; node* alloc_node(void) -> eax = указатель на новый узел alloc_node: push ebp mov ebp, esp push ebx mov eax, [next_free] ; eax = индекс свободного узла mov ebx, eax imul ebx, ebx, NODE_SIZE add ebx, pool ; ebx = адрес нового узла inc eax mov [next_free], eax mov eax, ebx mov dword [eax+0], 1 ; leaf = 1 (истина) по умолчанию — лист mov dword [eax+4], 0 ; n = 0 (пока нет ключей) pop ebx mov esp, ebp pop ebp ret

注意这里一个隐含的设计决策:新分配的节点默认leaf = 1。这符合直觉——刚创建出来的节点还没有任何孩子,当然是叶子;只有在它被塞进内部结构、挂上孩子指针之后,才会被显式改成leaf = 0(在btree_insert树长高、创建新根的那段代码里能看到)。

3. 调用约定与寄存器分配

整套代码统一用cdecl 风格手写栈帧:

参数从右往左压栈,调用者负责求值顺序,被调用者用ret N自行清栈(这里图省事把"调用者/被调用者清栈"混用成了被调用者清栈,类似 stdcall,但因为整个工程是自己从头到尾写的,没有和外部 ABI 交互的需求,这样反而少写很多add esp, N);
每个函数开头push ebp / mov ebp, esp,参数从[ebp+8]开始;
需要局部变量就sub esp, N,用[ebp-4]这样的负偏移访问;
ebx / ecx / edx / esi / edi但凡会被用到,一律在函数入口 push、出口 pop——这在递归函数里是生死攸关的,因为insert_nonfull会调用自己,split_child里保存的esi(child 指针)如果不被现场保护,递归返回后这个值就废了。

eax有意不进入"需要保护"的名单——它被当作真正意义上的 caller-saved 临时寄存器和返回值寄存器,谁用完就自己再算一次,不指望调用后还保留原值。这是从写了几个版本踩坑之后总结出来的规矩:哪些寄存器"跨调用存活"、哪些"随时可能被冲掉",必须在写代码前就想清楚,而不是出了 bug 再去猜。

4. 核心算法:split_child

这是全篇最烧脑的一段,把 CLRS 伪代码里"数组下标搬移"翻译成裸指针运算。逻辑分四步:

分配一个新节点z,它将接管child的后半段关键字和孩子指针;
把child后t-1个关键字、后t个孩子指针(如果不是叶子的话)搬到z;
把parent里i位置之后的孩子指针、关键字统一右移一格,腾出空位;
把child的中间关键字提升到parent[i],z挂到parent.children[i+1]。

; --------------------------------------------------------------------- ; SPLIT_CHILD — расщепление переполненного дочернего узла ; void split_child(node* parent, int i, node* child) ; [ebp+8]=parent [ebp+12]=i [ebp+16]=child ; --------------------------------------------------------------------- split_child: push ebp mov ebp, esp sub esp, 4 ; локальная переменная: указатель на новый узел z push ebx push ecx push edx push esi push edi ; z = alloc_node() — новый узел, который заберёт правую половину ключей call alloc_node mov [ebp-4], eax ; сохраняем z mov esi, [ebp+16] ; esi = child (переполненный узел, 2T-1 ключей) mov edi, [ebp-4] ; edi = z (новый узел-сосед) mov eax, [esi+0] ; z.leaf = child.leaf (наследуем тип узла) mov [edi+0], eax mov dword [edi+4], T-1 ; z.n = T - 1 = 1 ; копируем старшие ключи child[T..2T-2] -> z[0..T-2] ; при T=2 копируется ровно один ключ: child.keys[2] -> z.keys[0] mov eax, [esi + 8 + (T)*4] ; child.keys[T] mov [edi + 8 + 0*4], eax ; z.keys[0] ; если child не лист — переносим и указатели на детей [T..2T-1] -> z[0..T-1] cmp dword [esi+0], 0 ; child.leaf (1 = лист, 0 = внутренний) jne .skip_children_copy mov eax, [esi + 20 + (T)*4] ; child.children[T] mov [edi + 20 + 0*4], eax mov eax, [esi + 20 + (T+1)*4] ; child.children[T+1] mov [edi + 20 + 1*4], eax .skip_children_copy: mov dword [esi+4], T-1 ; child.n = T - 1 = 1 (обрезаем переполненный узел) ; сдвигаем указатели-дети родителя вправо, освобождая место под z: [i+1 .. n] mov edx, [ebp+8] ; edx = parent mov ecx, [edx+4] ; ecx = parent.n mov eax, [ebp+12] ; eax = i .shift_children: cmp ecx, eax jle .children_done mov ebx, [edx + 20 + ecx*4] mov [edx + 20 + (ecx+1)*4], ebx dec ecx jmp .shift_children .children_done: mov ecx, eax inc ecx mov [edx + 20 + ecx*4], edi ; parent.children[i+1] = z ; сдвигаем ключи родителя вправо: [i .. n-1] -> [i+1 .. n] mov ecx, [edx+4] dec ecx .shift_keys: cmp ecx, eax jl .keys_done mov ebx, [edx + 8 + ecx*4] mov [edx + 8 + (ecx+1)*4], ebx dec ecx jmp .shift_keys .keys_done: mov ebx, [esi + 8 + (T-1)*4] ; средний ключ переносим наверх mov [edx + 8 + eax*4], ebx inc dword [edx+4] ; parent.n += 1 pop edi pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 12

这里有个容易踩的雷:.shift_children和.shift_keys两个循环的边界条件不一样——前者是jle(包含等号,因为孩子指针数组要多移一位),后者是jl。CLRS 伪代码里这两个循环的下标范围本来就差一格(孩子比关键字多一个),翻译成汇编时如果偷懒用同一个宏/同一段循环体,边界会全错。这也是为什么最终选择把两段循环完全独立地写开,而不是试图"复用"——在汇编层面,过早的抽象复用往往比重复代码更容易出 bug。

5. insert_nonfull:真正的递归下探

insert_nonfull假设自己拿到的节点必然不满(这个前提由调用者保证——正是"预防式分裂"发挥作用的地方)。它分两种情况:

叶子节点:直接在有序位置插入,把后面的关键字整体右移一格;
内部节点:找到 key 应该落在哪个孩子的子树里,如果那个孩子已经满员就先分裂它(分裂后中间关键字被提到当前节点,可能导致 key 该走的方向发生变化,所以分裂后要重新比较一次),然后递归调用自己进入那个孩子。

; --------------------------------------------------------------------- ; INSERT_NONFULL — вставка ключа в узел, заведомо не полный ; void insert_nonfull(node* x, int key) ; [ebp+8]=x [ebp+12]=key ; --------------------------------------------------------------------- insert_nonfull: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp+8] ; esi = x mov eax, [esi+4] ; eax = x.n dec eax ; i = n - 1 mov ecx, [ebp+12] ; ecx = key cmp dword [esi+0], 0 ; x.leaf ? (1 = лист, 0 = внутренний узел) jne .leaf_case ; --- ветка "внутренний узел" --- .find_child_loop: cmp eax, 0 jl .found_child_pos mov edx, [esi + 8 + eax*4] ; x.keys[i] cmp ecx, edx jge .found_child_pos dec eax jmp .find_child_loop .found_child_pos: inc eax ; i += 1 -> индекс нужного ребёнка mov ebx, [esi + 20 + eax*4] ; ebx = x.children[i] cmp dword [ebx+4], MAX_KEYS ; ребёнок переполнен? jne .no_split_needed push ebx ; child push eax ; i push esi ; parent call split_child ; после расщепления средний ключ мог "перегнать" наш искомый key mov edx, [esi + 8 + eax*4] ; x.keys[i] — новый средний ключ cmp ecx, edx jle .no_split_needed inc eax .no_split_needed: mov ebx, [esi + 20 + eax*4] ; ebx = актуальный ребёнок для рекурсии push ecx ; key push ebx ; x = ребёнок call insert_nonfull jmp .done .leaf_case: .shift_loop: cmp eax, 0 jl .insert_here mov edx, [esi + 8 + eax*4] cmp ecx, edx jge .insert_here mov ebx, [esi + 8 + eax*4] mov [esi + 8 + (eax+1)*4], ebx dec eax jmp .shift_loop .insert_here: inc eax mov [esi + 8 + eax*4], ecx ; x.keys[i+1] = key inc dword [esi+4] ; x.n += 1 .done: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8

这里的递归调用call insert_nonfull没有做任何特殊处理——纯汇编的call/ret本身就是一个天然支持递归的机制,只要每次调用都老老实实保护好现场寄存器、维护好栈帧,函数"调用自己"和"调用别的函数"在机器层面没有任何区别。这是这次实现里少数几个"不需要额外发明轮子"的地方。

6. btree_insert:树是怎么长高的

如果根节点已经满了,不能直接往根里塞——必须先长出一层新根。这是全树唯一会增加"高度"的时刻:

btree_insert: push ebp mov ebp, esp push eax push ebx mov eax, [root] cmp dword [eax+4], MAX_KEYS ; корень переполнен? jne .root_not_full call alloc_node mov ebx, eax ; ebx = новый корень s mov dword [ebx+0], 0 ; s.leaf = 0 (это уже не лист) mov dword [ebx+4], 0 ; s.n = 0 mov eax, [root] mov [ebx + 20 + 0*4], eax ; s.children[0] = старый корень mov [root], ebx push eax ; child = старый корень push 0 ; i = 0 push ebx ; parent = s call split_child mov ecx, [ebp+8] push ecx push ebx call insert_nonfull jmp .fin .root_not_full: mov ecx, [ebp+8] push ecx push eax call insert_nonfull .fin: pop ebx pop eax mov esp, ebp pop ebp ret 4

7. 真实翻车现场:一个方向反了的 if

上面贴出来的代码,其实是修好之后的版本。第一版写完、汇编、链接、丢进qemu-i386跑起来之后,直接是这样:

Segmentation fault (core dumped)

没有任何输出,连第一行 in-order 遍历的提示语都没打出来。这种"完全没输出就死"的现场,说明崩溃发生得很早——大概率是第一次调用insert_nonfull或split_child的时候就已经在读写非法地址了。

调试思路是把qemu-i386换成静默模式、用nasm -g -F dwarf带上调试信息重新汇编,再对照代码走查每一处涉及leaf字段的分支——这是最值得怀疑的地方,因为它是一个"语义方向"很容易搞反的布尔值:leaf = 1到底该在je还是jne的时候触发对应分支,纯靠肉眼很容易凭"感觉"写反,而 CPU 不会对你说"这个方向感觉不太对"。

结果真的在三处地方找到了同一个错误的三个变体:

; 错误版本(节选自 insert_nonfull): cmp dword [esi+0], 0 ; x.leaf ? je .leaf_case ; <-- 反了!leaf=1 才是叶子,这里却在 leaf=0 时跳转

leaf字段的约定是1 = 是叶子。但是je .leaf_case的意思是"当[esi+0] == 0时跳到叶子分支"——也就是说,内部节点(leaf=0)被当成叶子处理,直接在它的keys数组里插入,完全跳过了"找到正确孩子、递归下探"的逻辑;而真正的叶子节点反而被当成内部节点,试图读取它本不存在的children指针——那些指针槽位从alloc_node分配出来时是从来没被写过的,里面是.bss段的原始零值或者相邻节点覆盖下来的脏数据,顺着一个野指针写下去,几条指令之后必然SIGSEGV。

split_child和inorder_print里也各自藏了一个方向相反的同款错误,因为这三处都是"复制粘贴 + 手改"写出来的,复制的时候顺手把判断方向也复制过去了,而三处原本就该是同一个方向。这是一个很有代表性的教训:在没有类型系统兜底的语言里,一个语义相反的分支不会在编译期报错,只会在运行时以完全不相关的症状(内存越界)表现出来,而且离出错的根因(条件反了)往往隔着好几层函数调用,靠 core dump 的崩溃地址反推源头,不如直接把所有同类判断拉出来,一条条对着字段定义重新读一遍来得快。修复方式很朴素——把三处je/jne全部按leaf=1表示"是叶子"这个统一约定改正,同时把原来语焉不详的注释也一并改成明确写出"1 = лист, 0 = внутренний"(1=叶子,0=内部节点),避免未来的自己再犯一次。

8. 完整源码

以下是通过全部测试的完整实现,包含查找、中序遍历打印和不依赖 libc 的数字转字符串:

; ===================================================================== ; btree.asm — минимальная реализация B-дерева (степень t = 2) ; Платформа: Linux x86-32, ELF32, только сырые syscalls (без libc) ; Автор: neatsuki ; ===================================================================== %define T 2 ; минимальная степень дерева %define MAX_KEYS 3 ; 2*T - 1 %define MAX_CHILD 4 ; 2*T %define NODE_SIZE 36 ; 4(leaf) + 4(n) + 3*4(keys) + 4*4(children) %define MAX_NODES 64 ; размер пула узлов (статический аллокатор) section .bss pool resb NODE_SIZE * MAX_NODES ; пул узлов дерева next_free resd 1 ; индекс следующего свободного узла root resd 1 ; указатель на корень дерева numbuf resb 16 ; буфер для перевода числа в строку section .data msg_found db "FOUND: " len_found equ $ - msg_found msg_notfound db "NOT FOUND: " len_notfound equ $ - msg_notfound msg_inorder db "In-order obhod dereva: ", 10 len_inorder equ $ - msg_inorder msg_newline db 10 msg_space db " " section .text global _start ; void print_str(char *buf, int len) [ebp+8]=buf [ebp+12]=len print_str: push ebp mov ebp, esp push eax push ebx push ecx push edx mov eax, 4 ; sys_write mov ebx, 1 ; stdout mov ecx, [ebp+8] ; буфер mov edx, [ebp+12] ; длина int 0x80 pop edx pop ecx pop ebx pop eax mov esp, ebp pop ebp ret 8 ; void print_num(int n) [ebp+8]=число (может быть отрицательным) print_num: push ebp mov ebp, esp push eax push ebx push ecx push edx push edi mov eax, [ebp+8] lea edi, [numbuf+15] ; идём с конца буфера mov byte [edi], 0 mov ebx, 10 xor ecx, ecx ; счётчик цифр test eax, eax jns .conv_loop neg eax ; работаем с модулем, знак допечатаем отдельно .conv_loop: xor edx, edx div ebx ; eax = eax/10, edx = остаток add dl, '0' dec edi mov [edi], dl inc ecx test eax, eax jnz .conv_loop mov eax, [ebp+8] test eax, eax jns .no_sign dec edi mov byte [edi], '-' inc ecx .no_sign: push ecx push edi call print_str pop edi pop ecx pop edx pop ebx pop eax mov esp, ebp pop ebp ret 4 ; node* alloc_node(void) -> eax = указатель на новый узел alloc_node: push ebp mov ebp, esp push ebx mov eax, [next_free] mov ebx, eax imul ebx, ebx, NODE_SIZE add ebx, pool inc eax mov [next_free], eax mov eax, ebx mov dword [eax+0], 1 ; leaf = 1 по умолчанию mov dword [eax+4], 0 ; n = 0 pop ebx mov esp, ebp pop ebp ret ; void split_child(node* parent, int i, node* child) split_child: push ebp mov ebp, esp sub esp, 4 push ebx push ecx push edx push esi push edi call alloc_node mov [ebp-4], eax mov esi, [ebp+16] mov edi, [ebp-4] mov eax, [esi+0] mov [edi+0], eax mov dword [edi+4], T-1 mov eax, [esi + 8 + (T)*4] mov [edi + 8 + 0*4], eax cmp dword [esi+0], 0 jne .skip_children_copy mov eax, [esi + 20 + (T)*4] mov [edi + 20 + 0*4], eax mov eax, [esi + 20 + (T+1)*4] mov [edi + 20 + 1*4], eax .skip_children_copy: mov dword [esi+4], T-1 mov edx, [ebp+8] mov ecx, [edx+4] mov eax, [ebp+12] .shift_children: cmp ecx, eax jle .children_done mov ebx, [edx + 20 + ecx*4] mov [edx + 20 + (ecx+1)*4], ebx dec ecx jmp .shift_children .children_done: mov ecx, eax inc ecx mov [edx + 20 + ecx*4], edi mov ecx, [edx+4] dec ecx .shift_keys: cmp ecx, eax jl .keys_done mov ebx, [edx + 8 + ecx*4] mov [edx + 8 + (ecx+1)*4], ebx dec ecx jmp .shift_keys .keys_done: mov ebx, [esi + 8 + (T-1)*4] mov [edx + 8 + eax*4], ebx inc dword [edx+4] pop edi pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 12 ; void insert_nonfull(node* x, int key) insert_nonfull: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp+8] mov eax, [esi+4] dec eax mov ecx, [ebp+12] cmp dword [esi+0], 0 jne .leaf_case .find_child_loop: cmp eax, 0 jl .found_child_pos mov edx, [esi + 8 + eax*4] cmp ecx, edx jge .found_child_pos dec eax jmp .find_child_loop .found_child_pos: inc eax mov ebx, [esi + 20 + eax*4] cmp dword [ebx+4], MAX_KEYS jne .no_split_needed push ebx push eax push esi call split_child mov edx, [esi + 8 + eax*4] cmp ecx, edx jle .no_split_needed inc eax .no_split_needed: mov ebx, [esi + 20 + eax*4] push ecx push ebx call insert_nonfull jmp .done .leaf_case: .shift_loop: cmp eax, 0 jl .insert_here mov edx, [esi + 8 + eax*4] cmp ecx, edx jge .insert_here mov ebx, [esi + 8 + eax*4] mov [esi + 8 + (eax+1)*4], ebx dec eax jmp .shift_loop .insert_here: inc eax mov [esi + 8 + eax*4], ecx inc dword [esi+4] .done: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8 ; void btree_insert(int key) btree_insert: push ebp mov ebp, esp push eax push ebx mov eax, [root] cmp dword [eax+4], MAX_KEYS jne .root_not_full call alloc_node mov ebx, eax mov dword [ebx+0], 0 mov dword [ebx+4], 0 mov eax, [root] mov [ebx + 20 + 0*4], eax mov [root], ebx push eax push 0 push ebx call split_child mov ecx, [ebp+8] push ecx push ebx call insert_nonfull jmp .fin .root_not_full: mov ecx, [ebp+8] push ecx push eax call insert_nonfull .fin: pop ebx pop eax mov esp, ebp pop ebp ret 4 ; node* btree_search(node* x, int key) -> eax = узел или 0 btree_search: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp+8] mov ecx, [ebp+12] xor eax, eax .search_loop: cmp eax, [esi+4] jge .after_loop mov edx, [esi + 8 + eax*4] cmp ecx, edx jle .after_loop inc eax jmp .search_loop .after_loop: cmp eax, [esi+4] jge .not_this_key mov edx, [esi + 8 + eax*4] cmp ecx, edx jne .not_this_key mov eax, esi jmp .ret_found .not_this_key: cmp dword [esi+0], 0 jne .not_found mov ebx, [esi + 20 + eax*4] push ecx push ebx call btree_search jmp .ret_found .not_found: xor eax, eax .ret_found: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8 ; void inorder_print(node* x) inorder_print: push ebp mov ebp, esp push ebx push ecx push esi mov esi, [ebp+8] xor ecx, ecx .walk_loop: cmp ecx, [esi+4] jg .walk_done cmp dword [esi+0], 0 jne .print_key push ecx mov ebx, [esi + 20 + ecx*4] push ebx call inorder_print pop ecx .print_key: cmp ecx, [esi+4] jge .walk_next push ecx mov ebx, [esi + 8 + ecx*4] push ebx call print_num push 1 push msg_space call print_str pop ecx .walk_next: inc ecx jmp .walk_loop .walk_done: pop esi pop ecx pop ebx mov esp, ebp pop ebp ret 4 ; ===================================================================== ; ТОЧКА ВХОДА ; ===================================================================== _start: mov dword [next_free], 0 call alloc_node mov [root], eax push 10 call btree_insert push 20 call btree_insert push 5 call btree_insert push 6 call btree_insert push 12 call btree_insert push 30 call btree_insert push 7 call btree_insert push 17 call btree_insert push msg_inorder mov eax, len_inorder push eax call print_str mov eax, [root] push eax call inorder_print push 1 push msg_newline call print_str push len_found push msg_found call print_str mov eax, [root] push 17 push eax call btree_search test eax, eax setnz al movzx eax, al push eax call print_num push 1 push msg_newline call print_str push len_notfound push msg_notfound call print_str mov eax, [root] push 99 push eax call btree_searc