————————————本栏目旨在交流计算机知识，欢迎交流指正！———————————

        上一章，我们介绍了深度优先搜索（dfs）与广度优先搜索（bfs）的概念，这一张，我们将会用动态存储的方式来实现它。

如图所示，今天我们将用此图来作为范本实现我们的搜索：

首先，让我们回忆一下三大基础遍历方式：

先序遍历：ABCDEFGHK

中序遍历：BDCAEHGKF

后序遍历：DCBHKGFEA

我们这里将会介绍基础递归法来实现这三种遍历，但是在这之前，我们得先建树：

        首先，我们先书写.h文件里的外置引用函数与树节点和树头：

typedef int Element;
// 树的节点结构
typedef struct _tree_node {
	Element data;
	struct _tree_node *left;
	struct _tree_node *right;
} TreeNode;

// 二叉树的树头
typedef struct {
	TreeNode *root;
	int count;
} BinaryTree;

BinaryTree *createBinaryTree(TreeNode *root);
void releaseBinaryTree(BinaryTree *tree);

TreeNode *createTreeNode(Element e);
void insertBinaryTree(BinaryTree *tree, TreeNode *parent, TreeNode *left, TreeNode *right);
void visitTreeNode(const TreeNode *node);

void preOrderBTree(const BinaryTree *tree);
void inOrderBTree(const BinaryTree* tree);
void postOrderBTree(const BinaryTree* tree);
void levelOrderBTree(const BinaryTree *tree);

void preOrderBtreeNoRecursion(const BinaryTree *tree);
void inOrderBtreeNoRecursion(const BinaryTree *tree);

###输出呈现函数###

void visitTreeNode(const TreeNode* node) {
	if (node)
		printf("\t%c", node->data);
}

 ###初始化建树的函数###

BinaryTree *createBinaryTree(TreeNode *root) {
	BinaryTree *tree = malloc(sizeof(BinaryTree));
	if (tree == NULL) {
		fprintf(stderr, "tree malloc failed!\n");
		return NULL;
	}
	if (root) {
		tree->root = root;
		tree->count = 1;
	} else {
		tree->root = NULL;
		tree->count = 0;
	}
	return tree;
}
//树头的建立

TreeNode *createTreeNode(Element e) {
	TreeNode *node = malloc(sizeof(TreeNode));
	node->data = e;
	node->left = node->right = NULL;
	return node;
}
//节点的建立

###树的赋值插入函数###

void insertBinaryTree(BinaryTree* tree, TreeNode* parent, TreeNode* left, TreeNode* right) {
	if (tree && parent) {
		parent->left = left;
		parent->right = right;

		if (left) {
			tree->count++;
		}
		if (right) {
			tree->count++;
		}
	}
}

1、先序遍历：

        先序遍历讲究一个单边走到头再返回，于是我们可以将输出段放在递归接口之前，确保完整走完一边子树再走另一边。

        

static void preOrderNode(const TreeNode *node) {
	if (node) {
		visitTreeNode(node);
		preOrderNode(node->left);
		preOrderNode(node->right);
	}
}

2、中序遍历：

        中序遍历讲究一个“V”字型走向遍历，所以输出段应该放在左子树遍历与右子树遍历之间，在主体“V”上走过小“V”。

static void inOrderNode(const TreeNode *node) {
	if (node) {
		inOrderNode(node->left);
		visitTreeNode(node);
		inOrderNode(node->right);
	}
}

 3、后序遍历：

        后序遍历讲究起于微末，终于殿堂，瓮中捉鳖。先把子树从左到右从下到上从叶子结点开始遍历完毕，最后再变量根节点，所以当左子树和右子树递归完毕后才能输出。

static void postOrderNode(const TreeNode *node) {
	if (node) {
		postOrderNode(node->left);
		postOrderNode(node->right);
		visitTreeNode(node);
	}
}

//集成前、中、后序遍历
void preOrderBTree(const BinaryTree* tree) {
	preOrderNode(tree->root);
	printf("\n");
}

void inOrderBTree(const BinaryTree* tree) {
	inOrderNode(tree->root);
	printf("\n");
}

void postOrderBTree(const BinaryTree* tree) {
	postOrderNode(tree->root);
	printf("\n");
}

        好了，温习过基础深度遍历方法后，我们来介绍广度优先遍历，所谓广度优先遍历就是一层一层的遍历，不再追求走到叶子结点，而是从左到右一步步走完，所以，广度优先遍历多被用于寻找最短路的题目中。如何实现呢？这里我们尝试使用队列的知识：如果满足就入队，并且这一层入队完毕后把所有上一层次的点出队。这样就可以形成一层层的遍历了。

上代码：

/* 广度遍历
 * 1. 引入一个任务队列，先把根节点入队
 * 2. 从任务队列中，取出一个节点，处理他（访问）
 * 3. 如果2步的节点，有左那么就入队，有右那么就入队
 * 4. 重复第2步
 */
void levelOrderBTree(const BinaryTree* tree) {
	// 申请一个任务队列，用顺序存储，循环队列，队列里每个元素应该是节点的地址
#define MaxQueueSize 8
	TreeNode* queue[MaxQueueSize];
	int front, rear;

	// 初始化系统
	front = rear = 0;
	queue[rear] = tree->root;
	rear = (rear + 1) % MaxQueueSize;

	// 开始循环系统处理事务
	while (rear != front) {
		TreeNode* node = queue[front];
		front = (front + 1) % MaxQueueSize;
		visitTreeNode(node);
		if (node->left) {
			queue[rear] = node->left;
			rear = (rear + 1) % MaxQueueSize;
		}
		if (node->right) {
			queue[rear] = node->right;
			rear = (rear + 1) % MaxQueueSize;
		}
	}
}

好了，介绍完深度优先遍历与广度优先遍历的写法后，我们还有一个拓展知识点——仔细思考一下，如果使用深度优先遍历，如果层数太多我们在写一个搜索时会时常遇到加载慢的问题，而如果我们使用记忆化搜索，随着数据量的增多，不免会积累海量的数据。下面，我们将介绍一种不基于递归的深度优先搜索写法，并用栈来实现。

        说到栈，我们回忆之前栏目中的栈结构：先进后出，后进先出，所以，假设我们要实现先序遍历，那么我们先出栈的必须是左子树，所以先压右子树进栈，再压左子树。最后出栈时，先出左子树，后出右子树。大体思路如下：

/* 非递归实现先序遍历，基本思路：
 * 先序的结果是当前节点、再左节点、最后右节点。把栈当做任务的暂存空间，
 * 先压右节点，再压左节点，一旦弹栈，出现的是左节点。
 * 基本步骤：
 * 1. 初始化部分
 *		将根节点压栈
 * 2. 循环处理任务部分
 *	2.1 弹栈，访问弹出来的节点，判断节点有右先压右，有左再压左，保证先右后左
 *	2.2 循环出栈，直到栈内无元素
 */
void preOrderBtreeNoRecursion(const BinaryTree* tree) {
	ArrayStack stack;
	initArrayStack(&stack);
	pushArrayStack(&stack, tree->root);

	TreeNode *node;
	while (!isEmptyArrayStack(&stack)) {
		node = getTopArrayStack(&stack);
		popArrayStack(&stack);
		visitTreeNode(node);
		if (node->right) {
			pushArrayStack(&stack, node->right);
		}
		if (node->left) {
			pushArrayStack(&stack, node->left);
		}
	}
}

/* 以根节点开始，整条左边进栈，从栈中弹出节点，开始访问
 * 如果这个节点有右孩子，把右孩子当做新节点
 * 再次整条边进栈，再弹栈
 */
void inOrderBtreeNoRecursion(const BinaryTree* tree) {
	ArrayStack stack;
	initArrayStack(&stack);
	// pushArrayStack(&stack, tree->root);

	TreeNode *node = tree->root;

	while (!isEmptyArrayStack(&stack) || node) {
		if (node) {
			pushArrayStack(&stack, node);
			node = node->left;
		} else {
			node = getTopArrayStack(&stack);
			popArrayStack(&stack);
			visitTreeNode(node);
			node =node->right;
		}
	}
}

希望能对你有所帮助！