linux系统非线性结构的遍历算法

介绍

非线性结构的二叉搜索树（BST）可以进行各种不同方式的遍历，所谓遍历，就是环游树中的每一个节点，然后根据我们的需要对这些节点做某种处理。树的遍历方式主要有以下几种。

（1）先序遍历，先访问根节点，再访问左子树，最后访问右子树
（2）中序遍历，先访问左子树，再访问根节点，最后访问右子树
（3）后序遍历，先访问左子树，再访问右子树，最后访问根节点
（4）按层遍历，从上到下，从左到右，依次访问每一个节点。
注意，前三种方法都是递归的，比如先序遍历，在访问完其根节点之后，下一步如何访问其左子树呢？答案是递归地使用先序的逻辑继续访问其左子树。实际上，对于一棵树而言，当访问任意一棵子树都是用这种“根-》左-》右”的算法遍历是，这样的算法就叫先序遍历。

下图展示了这些遍历算法的逻辑：

下面是先序、中序、后序、按层的遍历算法实现。

travel.c

//  Description: 二叉树遍历：前序遍历、中序遍历、后序遍历和按层遍历
//               所有的遍历算法，都采用如下接口的函数来访问树节点：
//
//                        void handler(linktree root);
//
//               因此，使用本文件遍历算法时，应用程序需提供上述接口
//               函数的定义。



#include "commonheader.h"
#include "head4tree.h"

#define QUEUE_NODE_DATATYPE linktree
#include "head4queue.h"

void pre_travel(linktree root, void (*handler)(linktree))
{
	if(root == NULL)
		return;
	
	handler(root);
	pre_travel(root->lchild, handler);
	pre_travel(root->rchild, handler);
}

void mid_travel(linktree root, void (*handler)(linktree))
{
	if(root == NULL)
		return;
	
	mid_travel(root->lchild, handler);
	handler(root);
	mid_travel(root->rchild, handler);
}

void post_travel(linktree root, void (*handler)(linktree))
{
	if(root == NULL)
		return;

	post_travel(root->lchild, handler);
	post_travel(root->rchild, handler);
	handler(root);
}

void level_travel(linktree root, void (*handler)(linktree))
{
	if(root == NULL)
		return;

	linkqueue q;
	q = init_queue();

	en_queue(q, root);

	linktree tmp;
	while(1)
	{
		if(!out_queue(q, &tmp))
			break;

		handler(tmp);

		if(tmp->lchild != NULL)
			en_queue(q, tmp->lchild);
		if(tmp->rchild != NULL)
			en_queue(q, tmp->rchild);
	}
}

注意事项

1、需要注意的是，按层遍历需要用到队列逻辑，具体流程如下：
（1）创建一个空队列
（2）将树的根节点入队
（3）判断队列是否为空，如果为空，则遍历结束，否则出队队头元素
（4）访问该队头元素
（5）如果该队头元素左孩子不为空，则将其左孩子入队。
（6）如果该队头元素右孩子不为空，则将其右孩子入队
（7）重复第（3）步

2、handler是调用这些遍历算法的用户程序自定义的回调函数，用于在遍历节点时对节点做某种处理。
3、上述遍历算法实现代码中涉及的相关头文件在我的以下博文中有展示：
涉及的头文件