目 录
.............................................................................................................................................................1
实验名称： 二叉树的建立与遍历...................................................................................................1
指导教师： 吴亚峰............................................................................................................................1
班 级： 06 接计 1 班..........................................................................................................................1
学 号： 200601210115.......................................................................................................................1
河北理工大学计算机与自动控制学院.............................................................................................1
2009 年 5 月 9 日................................................................................................................................1
一、设计思想.....................................................................................................................................0
二、程序流程图.................................................................................................................................2
三、源代码.........................................................................................................................................7
四、程序执行结果...........................................................................................................................15
五、心得体会...................................................................................................................................16
一、设计思想
二叉树的存储：
在内存中为数组 binary 分配一个大小为 63（0，0，0）的存储空间，所有数组元素初
始化为 0，用来存放二叉树。每三个连续的数组地址存放一个节点：第一个地址存放节点
的值；第二个地址存放有无左孩子的信息，如果有则将其置为 1，否则为 0；第三个地址
存放有无右孩子的信息，如果有则将其置为 1，否则为 0。将 binary 的首址偏移赋给 si，cx
初始化为 0 用来计数，用回车代表输入的为空，即没有输入。按先根存储的方式来存二叉
树，首先输入一个字符，若为回车则退出程序，否则 cx+3 且调用函数 root。然后该结点
若有左孩子，调用 leftchild 函数，置该结点标志即第二个地址中的 0 为 1，该结点进栈，再
存储左孩子结点，递归调用左右，若没有左孩子，看有没有右孩子，若有，则调用
rightchild 置该结点标志位即上第三个地址中的 0 为 1，然后该结点进栈，再存储右孩子结
点，递归调用左右，整个用 cx 计数，数组 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,然后加
cx，cx 再继续加 3，否则 si 出栈，结束中序过程；若结点的第二个地址中的元素不为 0，则
si 进栈，si 加 cx，cx 继续加 3，直到结点的第二个地址中的元素为 0，再判断右子树标志位，
为 1 继续，si 继续进栈，再用数组地址初始化 si,然后加 cx，cx 再继续加 3，否则 si 出栈，
结束中序过程。
