用汇编语言编写二叉树遍历

《用汇编语言编写二叉树遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、汇编程序设计说明书实验名称：二叉树的建立与遍历指导教师：吴亚峰姓名：卑艳杰班级：06接计1班学号：200601210115河北理工大学计算机与自动控制学院2009年5月9日16目录一、设计思想1二、程序流程图2三、源代码7四、程序执行结果15五、心得体会1616一、设计思想二叉树的存储：在内存中为数组binary分配一个大小为63（0，0，0）的存储空间，所有数组元素初始化为0，用来存放二叉树。每三个连续的数组地址存放一个节点：第一个地址存放节点的值；第二个地址存放有无左孩子的信息，如果有则将其置为1，否则为0；第三个地址存放

2、有无右孩子的信息，如果有则将其置为1，否则为0。将binary的首址偏移赋给si，cx初始化为0用来计数，用回车代表输入的为空，即没有输入。按先根存储的方式来存二叉树，首先输入一个字符，若为回车则退出程序，否则cx+3且调用函数root。然后该结点若有左孩子，调用leftchild函数，置该结点标志即第二个地址中的0为1，该结点进栈，再存储左孩子结点，递归调用左右，若没有左孩子，看有没有右孩子，若有，则调用rightchild置该结点标志位即上第三个地址中的0为1，然后该结点进栈，再存储右孩子结点，递归调用左右，整个用cx计数

3、，数组binary中每多一个节点，cx加3。此存储方式正好符合先序遍历思想。二叉树的遍历：（1）先序遍历：将binary的首址偏移赋给si，cx用来计数。每显示输出一个节点，则cx加3直接把数组元素下标为0，3，6，……用si遍历下来，每遍历一个结点，要判断si所指数组元素是否是0，是0，结束遍历；不是0，则输出，至到si所指元素为0，则没有结点，此时结束先序遍历。（2）中序遍历：用数组地址初始化si,然后加cx加3，若结点的第二个地址中的元素为0，打印si，再判断右子树标志位，为1继续，si继续进栈，再用数组地址初始化si,

4、然后加cx，cx再继续加3，否则si出栈，结束中序过程；若结点的第二个地址中的元素不为0，则si进栈，si加cx，cx继续加3，直到结点的第二个地址中的元素为0，再判断右子树标志位，为1继续，si继续进栈，再用数组地址初始化si,然后加cx，cx再继续加3，否则si出栈，结束中序过程。（3）后序遍历：后序遍历和中序遍历类似，只是先遍历左孩子，后遍历右孩子，再打印，递归。16打印MSGJ的内容初始化si、cxcallmidr结束（main）打印中序遍历提示打印后序遍历提示初始化si、cxcalllastrY存储字符callroo

5、t开始（main）si、cx清0打印MSGA的内容输入字符=回车打印MSG1的内容N二、程序流程图图1：主程序16结束root出栈N有右孩子?NY该结点进栈si=si+cx;cx=cx+3有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axN有右孩子?NY该结点进栈si=si+cx;cx=cx+3有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axN有右孩子?NY该结点进栈si=si+cx;cx=cx+3有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axN有右孩子?NY该结点进

6、栈si=si+cx;cx=cx+3有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axN有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axNN有右孩子?有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axNN有右孩子?有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axNN有右孩子?有左孩子?设左孩子标志位Y开始rootcx=186？？[si]=axN开始rootcx=186？？[si]=axNY设左孩子标志位开始rootcx=186？？[si]=axN设右孩子

7、标志位该结点进栈si=si+cx;cx=cx+3YY设左孩子标志位有左孩子?N有右孩子?图2：二叉树的存储16Y开始firstr结束firstr初始化sisi=si+3N[si]=0?打印[si]图3：先序遍历16开始midr结束midr打印[si][si+1]=0?si=si+cxcx=cx=3[si+2]=0?si进栈si出栈初始化si初始化sisi=si+cxcx=cx=3si进栈NNYY图4：中序遍历16开始lastr结束lastr打印[si][si+1]=0?si=si+cxcx=cx=3[si+2]=0?si进栈s

8、i出栈初始化si初始化sisi=si+cxcx=cx=3si进栈NNYY图5：后序遍历16三、源代码.modelsmall;----------------------------------------------------------------------------