这三种周游算法都是递归算法。递归算法虽然简洁,但是有时程序设计不允许用递 归,这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键 是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理,可以写出非递归周游 叉树的算法。 (3)二叉树的广度优先周游算法 对二叉树进行广度优先(层次)周游的过程是:首先访问第0层,也就是根结点所在 的层,然后从左到右依次访问第一层两个结点,以此类推,当第i层的所有结点访问完 之后,再从左至右依次访问第计1层的各个结点。 根据层次周游二叉树的性质,这里需要使用一个队列作为辅助的存储结构。层次周 游过程的实现就是从根结点开始逐层逐个地访问各个结点。在周游开始的时候,首先将 根结点放入队列:然后每次从队列中取出队头元素处理,每处理一个结点时,按从左至 右的顺序把它的所有子结点放入队列。这样,上层结点总是排在下一层结点的前面,从 而实现了二叉树的广度优先周游。 (4)二叉树的链式存储结构 所谓链式存储方式,是指二叉树的各结点随机的存储在内存空间中,结点之间的关 系用指针表示。 在用链接方式存储二又树时,对于每一个结点,除了存储结点本身的信息外,还要 设置两个指向左右孩子的指针。即表示二叉树的链表的结点包含三个域:数据域和左 右指针域。用info域存储结点的数据元素,另外再设置两个指针域lett和 right,分别 指向结点的左子结点和右子结点。当结点的某个子结点为空时,相应的指针为空指针。 有时候为了便于查找二叉树中某个结点的父结点,还可以在结点结构中加入一个指向其 父结点的指针域。这方面的内容,需要用图片进行形象的展示。 (5)二叉树的顺序存储结构 叉树的顺序存储是指按照一定次序,用一组地址连续的存储单元存储二叉树上的 各个结点元素 由于二叉树是一种非线性结构,因此必须将二叉树的结点排成一个线性序列,使得 通过结点在这个序列中的相对位置就能够确定结点之间的逻辑关系。通常情况下,只通 过相应位置不足以刻化整个树形结构。而对于一棵具有n个结点的完全二叉树,可以从 根结点起自上而下,从左至右地把所有的结点编号,得到一个足以反映整个二叉树结构 的线性序列。采用这种方式,线性序列里存储的结点就是按照层次周游二叉树得到的排3 这三种周游算法都是递归算法。递归算法虽然简洁，但是有时程序设计不允许用递 归，这时就存在如何把递归程序转化成等价的非递归算法的问题。解决这个问题的关键 是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理，可以写出非递归周游 二叉树的算法。 （3）二叉树的广度优先周游算法 对二叉树进行广度优先(层次)周游的过程是：首先访问第 0 层，也就是根结点所在 的层，然后从左到右依次访问第一层两个结点，以此类推，当第 i 层的所有结点访问完 之后，再从左至右依次访问第 i+1 层的各个结点。 根据层次周游二叉树的性质，这里需要使用一个队列作为辅助的存储结构。层次周 游过程的实现就是从根结点开始逐层逐个地访问各个结点。在周游开始的时候，首先将 根结点放入队列；然后每次从队列中取出队头元素处理，每处理一个结点时，按从左至 右的顺序把它的所有子结点放入队列。这样，上层结点总是排在下一层结点的前面，从 而实现了二叉树的广度优先周游。 （4）二叉树的链式存储结构 所谓链式存储方式，是指二叉树的各结点随机的存储在内存空间中，结点之间的关 系用指针表示。 在用链接方式存储二叉树时，对于每一个结点，除了存储结点本身的信息外，还要 设置两个指向左右孩子的指针。即表示二叉树的链表的结点包含三个域：数据域和左、 右指针域。用 info 域存储结点的数据元素，另外再设置两个指针域 left 和 right，分别 指向结点的左子结点和右子结点。当结点的某个子结点为空时，相应的指针为空指针。 有时候为了便于查找二叉树中某个结点的父结点，还可以在结点结构中加入一个指向其 父结点的指针域。这方面的内容，需要用图片进行形象的展示。 （5）二叉树的顺序存储结构 二叉树的顺序存储是指按照一定次序，用一组地址连续的存储单元存储二叉树上的 各个结点元素。 由于二叉树是一种非线性结构，因此必须将二叉树的结点排成一个线性序列，使得 通过结点在这个序列中的相对位置就能够确定结点之间的逻辑关系。通常情况下，只通 过相应位置不足以刻化整个树形结构。而对于一棵具有 n 个结点的完全二叉树，可以从 根结点起自上而下，从左至右地把所有的结点编号，得到一个足以反映整个二叉树结构 的线性序列。采用这种方式，线性序列里存储的结点就是按照层次周游二叉树得到的排