声明：本文的代码和理论来源：《系统设计师（高级程序员）教程》（王春森 主编，清华大学出版社）。本文的内容来源与我对书中代码的分析和注释。
在上一篇文章里，讲解了用栈前序遍历树。这一节讲解仍然沿用上一文中的准备知识。
（1）按层次遍历树。层次，即相当于资源管理器的文件夹深度，见前文图1中的纵坐标。由于在示例树中的节点编号就是按照层次来给出的，所以按层次遍历这棵树的结果就是：1，2，3，4，5，6，7，8，9。
     由于我们在遍历过程中处于树的某个局部，因此我们需要引入一个辅助数据结构来帮助我们完成遍历。考虑到层次遍历的特点是，每一层次的所有子节点应该集中在一起，当访问某个节点时，其下一层次的子节点应该处于等待被访问的状态。因此我们应该引入队列作为辅助存储。
     方法如下：

     算法：每次取出队首节点，打印该节点，队首指针向后移动一格，然后将其所有子节点顺序进入列尾部，队尾指针相应向后移动。
     初始队列状态：根节点入队列，队列中仅有根节点。head=0，tail=1；
     结束条件：队列为空。即队列的两个指针重合，head==tail；

     队列我们同样用一个数组来模拟，并且需要两个变量head和tail来标识队列的有效区间，队列的特点是FIFO（先入先出），因此，子序列入队是顺序入队（和前文中用栈前序不同，由于栈的特点是FILO或者LIFO，所以子节点是逆序入栈的）。有效队列在数组中处于移动状态，在head，tail在移动到数组末尾时，重新指向数组前部，所以代码中这里有个索引自增后对队列长度取余的运算，因此实际上这里的队列在逻辑上是环形的，也就是数组的首尾相接，因此只有向队首或者向队尾两种移动方向的区别，而队列位于数组的什么位置并不重要（比如队列可能会一部分位于数组末端，一部分位于数组起始处，在内存视角上看不是连续的，但在逻辑上依然是连续的）。

     下面我们看相关的代码：

/*

 * 用队列（queue）来层次遍历一颗普通树

 */
#define M 10 /*树的次/度：最大子节点数*/
#define QN 100 /*队列最大长度*/
typedef struct tnode
{
    char data;
    struct tnode *child[M];
}TNODE;

int lev_order(TNODE *t, int m)
{
    TNODE *q[QN];/* queue */
    TNODE *p;
    int head=0, tail=0, i;/*队列的头，尾索引*/
    q[tail++]=t; /*根节点入列*/
    while(head!=tail)/* 当队列不为空（首尾相遇时为空） */
    {
        p=q[head];/*从队首出列一个节点*/
        head=(head+1)%QN; /* head向后（队尾方向）移动一格 */
        printf("%c ",t->data);/*打印该节点*/
        
        for(i=0;i<m;i++) /* 出列节点的所有子节点按顺序入列（进入队列尾部） */
        {
            if(p->child[i])
            {
                if((tail+1)%QN==head) /*如果队列已经满了，返回0表示失败 */
                    return 0;
                q[tail]=p->child[i]; /*子节点入列*/
                tail=(tail+1)%QN;    /* tail向后移动一格 */
            }
        }
    }
    return 1; /*遍历结束，返回1表示成功*/
}

（2）关于树的少许补充：
2.1 二叉查找树和堆的结构看起来一样，但是区别是，二叉查找树：左子<=根<=右子； 而堆是：子节点<=根。另外，堆在逻辑上是树形，但存储是用数组存储的（节点按层次连续存入数组）。
2.2 中序遍历二叉查找树，输出的一个有序结果。
2.3 用作图法按前序，后序遍历树的规律：
      假设我们把二叉树的一个节点提取出来，我们看出，从节点中心垂直向上定义为0度角，逆时针正向，则节点的左右子树分支分别为120度（左子树）和240（右子树）。则我们可以用作图法得到各种序遍历的节点输出角度：从根节点上方向左下方画一条线外围住所有节点直到返回根节点，当线条经历到节点的以下角度时输出该节点（如图3所示，前序输出为1，2，4，5，3，6）：
      前序输出角度：60度；
      中序（仅针对二叉树）：180度；
      后序：300度。

[[it] 本帖最后由 hoodlum1980 于 2008-3-22 11:02 编辑 [/it]]