掌握树的遍历，这篇文章就够了

欢迎大家来到IT世界,在知识的湖畔探索吧!

树的遍历方法概括

树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。

树通常有前序遍历、中序遍历（仅适合二叉树）、后序遍历和层次遍历四种方式。

下面我们一一分析上面的四种遍历方式。

树的前序遍历

欢迎大家来到IT世界,在知识的湖畔探索吧!

1. 访问根结点
2. 按照从左到右的顺序前序遍历根结点的每一棵子树。
3. 先序遍历序列：abcdfge

中序遍历二叉树

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树
4. 中序遍历序列：bafgdce

树的后序遍历

1. 按照从左到右的顺序后序遍历根结点的每一棵子树；
2. 访问根结点；
3. 后序遍历序列：bgfdeca

树的层次遍历

1. 从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
2. 层次遍历序列：abcdefg

上面介绍了树的四种遍历的基本方法，下面我们以层次遍历为例详细介绍下树的遍历

树的层次遍历的算法实现

如上图所示，层次遍历的输出结果应该是：A B C D E F G H I

1. 初始化队列；
2. 访问根结点，根结点进队；
3. while（队列不空）
4. 队首元素出队；
5. 若其子女不为空，从左到右依次输出其子女，并进队。

上面是层次遍历算法的基本实现方法步骤，下面我们通过代码逐步实现

这里我们采用指针方式的孩子表示法类型定义，该方法在之前的文章中已经讲述过了，这里不做讲解。

#define m 3 /*树的度数*/ typedef char datatype; /*结点值的类型*/ typedef struct node /*结点的类型*/ { datatype data; struct node *child[m]; /*指向子女的指针数组* / } node *tree; tree root; /*root表示指向树根结点的指针*/

欢迎大家来到IT世界,在知识的湖畔探索吧!

这里假定树的度为3，#define m 3

欢迎大家来到IT世界,在知识的湖畔探索吧!void levelorder(tree t) /* t为指向树根结点的指针 */ { tree queue[100],p; /*存放等待访问的结点队列*/ int front,rear,i; /*f、r分别为队头、队尾指针*/ front=rear=0; /*初始化空队列*/ queue[rear++]=t; /*根结点进队*/ while (front<rear) /*队列不为空*/ { p=queue[front++]; /*出队*/ printf(“%c”, p-> data); for (i=0;i<m;++i) /*依次访问p的所有子女结点，并进队*/ if (p->child[i]) { queue[rear++]=p->child[i]; /*孩子结点进队*/ } } }

上面的代码中，第12行用来输出从根节点开始的各个结点的数据域，13行的for循环用来将每个结点的孩子结点入队，并在下次while循环中输出各个结点。如此循环直到队列为空（不存在孩子结点，也就是树遍历完全）。