遍历模式上的经典算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇遍历模式上的经典算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
程序代码不仅仅是目的，更重要的是继续学习的方法，特别是像二叉树、树和图的遍历这样的包含着存储结构设计的基础性算法，应该是分析、设计、实现和解释复杂算法的工具、要素。本文以垂直输出二叉树、快速排序、汉诺塔、生成二叉链表的设计和实现为例，说明这个方法。
1垂直输出二叉树与层次遍历
垂直输出二叉树的算法可以利用层次遍历方法1的模式。不同的是，在层次遍历中对结点的访问要改为定位输出，因此，队列中的元素不仅要包含结点指针，而且要包含输出的位置。
如何确定结点输出的位置？显示器的横向是X轴，纵向是Y轴，坐标轴的交点在左上角。假设屏幕宽度(screenwidth)是80。如图1所示。
二叉树的第1层只有一个结点，是根，在(40,1)点输出。40为偏移量(offset)。
第2层有两个结点，分别是上一层结点的左右孩子，输出的位置相对其双亲的位置而左右对称，因此，偏移量应该是上一层偏移量的一半(offset=40/2=20)。具体输出位置分别是(40-offset,2)和(40+offset,2)，即(20,2)和(60,2)。
第3层有四个结点，分别是上一层的2个结点(20,2)和(60,2)的左右孩子，偏移量offet=20/2=10，结点(20,2)的左右孩子的输出位置分别是(20-offset,3)和(20+offset,3)，即(10,3)和(30,3)， 结点(60,2) 的左右孩子的输出位置分别是(60-offset,3)和(60+offset,3)，即(50,3)和(70,3)。
归纳起来，第i层上任一结点的输出位置是在访问第i-1层结点时，由其双亲的位置确定的。如果其双亲的位置是(parentpos,i-1)，那么该结点若是左孩子，则输出位置是(parentpos-offset,i)，若是右孩子，则位置是(parentpos+ offet,i)，其中偏移量offset是上一层偏移量的一半。
如何把输出光标移到输出位置呢？y坐标变化，即层数增加，只要执行换行操作即可。关键是如何根据x坐标的变化来移动光标。控制格式化输出的成员函数ios::width(int)，是按照参数值减去当前输出光标的缩进量来更新输出宽度的(而且默认情况下是按右对齐输出)。以图26.7为例，假设一个结点已在位置(20,2)上输出，这时的光标缩进量(假设用indent表示)是20，下一步要在(60,2)的位置上输出，x坐标是60，这时利用成员函数width(int)来计算的输出宽度应该是40，即x-indent，用参数表示为width(40)，即width(x-indent)。
struct Location
{
int xindent,ylevel; //结点坐标位置
};
void Gotoxy(int x,int y) //输出位置
{
static int level=0,indent=0;
if(y==0) //重复输出二叉树时要重新赋值
{
level=0; indent=0;
}
if(level!=y) //若层数增加，则缩进量从0开始
{
cout
indent=0; level++;
}
cout.width(x-indent); //根据已有缩进量确定当前缩进量
indent=x; //记录当前的缩进量
}
2快速排序与前序遍历
按照树的集合表示法，二叉树根的作用在于把集合分成两部分，一部分代表左子树结点，另一部分代表右子树结点。
首先，设计一个划分数组元素的算法：以数组的某一元素为基准，把数组元素分为前后两部分，前面的不大于基准，后面的不小于基准，返回值是基准的下标。这个基准相当于根。然后按照前序遍历的顺序，对数组的前后两部分(左子树和右子树)继续这种划分，直到数组有序(见表2)。
3汉诺塔与中序遍历
n阶汉诺塔问题：有三根石柱，在一根石柱上放着n个盘子，每个盘子都比它下面的小，遵循以下规则，把盘子移到另一根柱子上：
(1) 每次只能移动一个盘子。
(2) 盘子可以放在任一根柱子上。
(3) 任何时刻，大盘不能压在小盘之上。
下面用归纳法证明，n阶汉诺塔问题可以用n层二叉树描述，而且它的解就是该二叉树的中序遍历序列：
用一个四元组(n,A,B,C)表示这样一个n阶汉诺塔问题：把n个盘子从A柱搬到C柱，中间可以借助B柱。其中A、B、C的地位是相对的，不妨假设第一个表示起始位置，最后一个表示终止位置，中间表示过渡位置。例如(n,B,A,C)表示把n个盘子从B搬到C，中间可以借助A的n阶汉诺塔问题。用一个三元组((n),A,B)表示把第n个盘子从A直接搬到B。
假设有两个盘子，要把两个盘子从A搬到C，即(2,A,B,C)，就必须先把第1个盘子从A直接搬到B,即((1),A,B)，再把第2个盘子从A直接搬到C，即 ((2),A,C)，最后把第1个盘子从B直接搬到C，即((1),B,C)。序列((1),A,B)，((2),A,C)，((1),B,C)正好是以(2,A,B,C)为根，以(1,A,C,B)和(1,B,A,C)为左右孩子的二叉树的中序遍历序列，只是访问结点的结果是，去掉过渡位置，盘子数加括号)(见图2)。双亲结点与左孩子的关系是，盘子个数减1，过渡位置和终止位置交换，与右孩子的关系是，盘子个数减1，起始位置和过渡位置交换。
假设有n个盘子时结论成立。现在假设有n+1个盘子。要把n＋1个盘子从A搬到C，即(n＋1,A,B,C)，必须先把前n个盘子从A搬到B,即(n,A,C,B),然后把第n+1个盘子从A直接搬到C，即((n+1),A,C)，最后把前n个盘子从B搬到C,即(n,B,A,C)。序列(n,A,C,B)，((n+1),A,C)，(n,B,A,C)正好是以(n+1,A,B,C)为根，以(n,A,C,B)和(n,B,A,C)为左右子树根的二叉树的中序遍历顺序(中序遍历左子树，访问根结点，中序遍历右子树)(见图3(a))。而左右子树都是n阶汉诺塔问题，已假设结论成立。因此对n+1阶汉诺塔问题，结论也成立。到此证明完毕。
图3分别给出了n阶和3阶汉诺塔问题状态树。3阶汉诺塔问题的解用中序序列表示是:((1),A,C)，((2),A,B)，((1),C,A)，((3),A,C)，((1),B,A)，((2),B,C)，((1),A,C)。
4生成二叉链表与后序遍历
在二叉树顺序存储结构中，如果一个非0元素的下标是pos，那么该元素的左右孩子下标是2*pos+1和2*pos+2。把二叉树的顺序存储转为链式存储的算法可以按照层次遍历的模式完成(见表4)。
5小结
上述算法的非递归代码都可以和在相应的二叉树遍历的非递归模式中实现。另外，八皇后问题可以在树的前序遍历模式中解决，迷宫可以归于图的深度有限遍历，等等，如果需要，请参看清华大学出版的《C/C++与数据结构》(第3版)(下册)。