下载掌阅APP，畅读海量书库
立即打开
在计算机科学中，二叉树是一种重要的数据结构。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地被转换为二叉树形式。
遍历是对树的一种最基本的运算。所谓的遍历二叉树，就是按照一定的规则和顺序扫描二叉树的所有节点，使得树上的每个节点都能被访问一次，而且只被访问一次。
本节将介绍二叉树的遍历原理和具体的实现方法。
二叉树是每个节点最多有两个子树的树结构。通常将子树分为“左子树”和“右子树”。二叉树的每个节点最多只有两棵子树（不存在度大于2的节点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层最多有2 i -1 个节点。深度为 k 的二叉树最多有2 k -1个节点。
假设下面的一组数据序列，如表2.1所示。
表2.1 数据序列与对应的节点编号
图2.1 二叉树的结构
用二叉树表示表2.1中所示的数据序列，如图2.1 所示，圆圈内的数字为该节点数据的值，圆圈外的数字为所对应节点的编号。
我们经常希望访问树中的每一个节点并且查看它的值。常见的二叉树遍历分为按深度优先遍历和按广度优先遍历。
在深度优先级中，我们希望从根节点访问最远的节点。与图的深度优先搜索不同的是，不需要记住访问过的每一个节点，因为树中不会有环。前序遍历（Pre-Order Traversal）、中序遍历（In-Order Traversal）和后序遍历（Post-Order Traversal）都是深度优先遍历的特例。
与深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称层序遍历（Level-Order Traversal）。
1.层序遍历
层序遍历就是按二叉树从上到下、从左到右依次扫描二叉树中的每个节点。对于图2.1给出的二叉树结构，按层序遍历数据的顺序为
20→19→17→16→18→10→15→14→12→13→9→7→6→8
2.前序遍历
前序遍历就是先访问根节点，再访问左节点，最后访问右节点。显然，在前序遍历中，访问父节点优于访问子节点。对于图2.1给出的二叉树结构，按前序遍历数据的顺序为
20→19→16→14→12→18→13→17→10→9→7→15→6→8
前序遍历用于创建树的“副本”，也用于获取表达式树上的前缀表达式。
3.中序遍历
中序遍历就是先访问左节点，再访问根节点，最后访问右节点。显然，在中序遍历中，访问父节点的次序位于左右子节点之间。对于图2.1给出的二叉树结构，按中序遍历数据的顺序为
14→16→12→19→13→18→20→9→10→7→17→6→15→8
在二叉搜索树（Binary Search Trees，BST）的情况下，中序遍历以非递减顺序给出节点。
4.后序遍历
后序遍历就是先访问左节点，再访问右节点，最后访问根节点。显然，在后序遍历中，先访问完左右子节点之后再访问父节点。对于图2.1给出的二叉树结构，按后序遍历数据的顺序为
14→12→16→13→18→19→9→7→10→6→8→15→17→20
后序遍历用于删除树，其对于获取表达式树的后缀表达式也非常有用。
基于递归的方法，在LoongIDE软件工具中使用C语言实现深度优先遍历（前序遍历、中序遍历和后序遍历）和广度优先遍历（层序遍历）算法的代码如代码清单2-1所示。
注 ：工程文件夹设置为：E:＼loongson1B_training_example＼example_2_1。
代码清单2-1 深度和广度优先遍历的C语言代码（递归实现）
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_2_1目录中，使用LoongIDE软件工具打开example_2_1.lxp工程文件。
本节将介绍如何对设计进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）在Windows操作系统中，进入设备管理器界面。在该界面中，找到虚拟出来的串口端口号，如图2.2所示。在本书所使用的计算机中，虚拟出的串口端口号为COM5。
（3）启动PuTTY（64-bit）软件工具，自动弹出“PuTTY Configuration”对话框，如图2.3所示。在该对话框中，选中“Session”选项，按如下设置参数。
图2.2 虚拟出来的串口
图2.3 “PuTTY Configuration”对话框
① Connection type：Serial（通过复选框设置）。
② Serial line：COM5（通过文本框设置）。
③ Speed：115200（通过文本框设置）。
（4）单击“Open”按钮，退出“PuTTY Configuration”对话框，进入命令行模式。
（5）在LoongIDE主界面主菜单下，选择Debug->Run，开始运行程序，在PuTTY命令行界面中则会打印出使用不同方法得到的遍历结果，如图2.4所示。
图2.4 PuTTY命令行模式下打印的信息（反色显示）
深度和广度优先遍历的C语言代码（非递归实现）如代码清单2-2所示。注意，代码中的tree［10］=0，对应表2.1中的空节点NULL。
代码清单2-2 深度和广度优先遍历的C语言代码（非递归实现）
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_2_2目录中，使用LoongIDE软件工具打开example_2_2.lxp工程文件。
本节将介绍如何对设计进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）启动并配置PuTTY（64-bit）软件工具。
（3）在LoongIDE主界面主菜单下，选择Debug->Run，开始运行程序，在PuTTY命令行界面中则会打印出使用不同方法得到的遍历结果，如图2.5所示。
图2.5 PuTTY命令行模式下打印的信息（反色显示）
在bsp_start.S文件中，添加如代码清单2-3所示的实现深度和广度优先遍历算法（非递归实现）。注意，代码中的tree［10］=0对应表2.1中的空节点NULL。
代码清单2-3 在bsp_start.S文件中添加实现深度和广度优先遍历算法（非递归实现）的汇编语言代码
注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_2_3目录中，使用LoongIDE软件工具打开example_2_3.lxp工程文件。
本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图2.6所示，在代码清单2-3中设置断点。
图2.6 在代码清单2-3中设置断点
（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面。
（4）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“a0”的一行，并用鼠标左键双击该行。注意，寄存器a0中保存着层序遍历结果的首地址。
（5）弹出“View Memory”对话框，如图2.7所示。从图2.7中可知，层序遍历的结果保存在存储空间地址为0x80212816开始的位置。在该对话框中，设置下面的参数。
① Count：15。（通过“Count”标题右侧的旋转按钮设置）。
② Data Type：short（通过选择“short”前面的复选框设置）。
（6）单击图2.7中的“Fetch”按钮。在图2.7的右侧窗口中，从地址0x80212816开始保存着层序遍历的结果。
（7）单击图2.7中的按钮图标
，退出“View Memory”对话框。
（8）在“CPU Registers”标签页中找到寄存器名字为“a1”的一行，并用鼠标左键双击该行。注意，寄存器a1中保存着前序遍历结果的首地址。
（9）弹出“View Memory”对话框，如图2.8所示。从图2.8中可知，前序遍历的结果保存在存储空间地址为0x80212834开始的位置。
（10）单击图2.8中的按钮图标
，退出“View Memory”对话框。
图2.7 “View Memory”对话框（1）
图2.8 “View Memory”对话框（2）
（11）在“CPU Registers”标签页中找到寄存器名字为“a2”的一行，并用鼠标左键双击该行。注意，寄存器a2中保存着中序遍历结果的首地址。
（12）弹出“View Memory”对话框，如图2.9所示。从图2.9中可知，中序遍历的结果保存在存储空间地址为0x80212852开始的位置。
（13）单击图2.9中的按钮图标
，退出“View Memory”对话框。
（14）在“CPU Registers”标签页中找到寄存器名字为“a3”的一行，并用鼠标左键再次双击该行。注意，寄存器a3中保存着后序遍历结果的首地址。
（15）弹出“View Memory”对话框，如图2.10所示。从图2.10中可知，后续遍历的结果保存在存储空间地址为0x80212870开始的位置。
图2.9 “View Memory”对话框（3）
图2.10 “View Memory”对话框（4）
（16）单击图2.10中的按钮图标
，退出“View Memory”对话框。