数据结构与算法：对于二叉树层次遍历及三种非递归遍历所需辅助空间的理解

一. 二叉树层次遍历

二叉树的层次遍历借助辅助队列实现，要理解为何基于辅助队列来实现对于二叉树的层次遍历，首先，需要知道什么是二叉树的层次遍历，所谓层次遍历，简单的说，就是从根节点开始，逐层从左往右依次访问每个节点，即按照树的每一行从左往右的次序依次进行访问（同一层上越靠左的越先被访问，我们想到队列先进先出的特性）因此，我们需要用辅助队列来实现，相关的代码如下：

void levelOrder(Bitree T) {
	Queue Q;
	initQueue(Q);
	Bitree p = T;
	EnQueue(Q,T);
	while (!isEmptyQ(Q)) {
		DeQueue(Q, p); // 对头元素出队
		visit(p);
		if (p->lchild != NULL) {
			levelOrder(p->lchild);
		}
		if (p->rchild != NULL) {
			levelOrder(p->rchild);
		}
	}
}

二. 二叉树的三种非递归遍历

非递归遍历需要借助辅助栈来实现，这是因为，无论是先序遍历，中序遍历，还是后续遍历，都需要深入到最左下的节点，以先序遍历为例：在遍历完成一个子节点后，进行visit，之后需要遍历该子节点的左子节点，以此类推，中序遍历和后续遍历就更好理解了，需要先递归地遍历左子树，仍然是要先找到最“左下”方的节点，因此，这里借助了栈“后进先出”的特性，直到将所有的左子节点全部入栈，直到不存在左子节点，这时，才对栈顶的元素（最近访问的左子节点）进行操作，注意这里的操作不全指弹栈访问，因为三种遍历的不同特性，在这里不一一说明，本文仅解释如何理解这两种不同的存储结构，具体实现代码如下：

void Non_recursive_forpreBitree(BiTNode* B) {
	stackNode S;
	initiation(S);
	Bitree p = B; //p为工作指针，用于遍历整棵二叉树
	while (p || !isEmpty(S)) {
		if (p) {
			visit(B);
			push(S, p);
			p = p->lchild;
		}
		else {
			pop(S, p);
			p = p->rchild;
		}
	}
}
void Non_recursive_formidBitree(BiTNode* B) {
	stackNode S;
	initiation(S);
	Bitree p = B;
	while (p || !isEmpty(S)) {
		if (p) {
			push(S, p);
			p = p->lchild;
		}
		else {
			pop(S, p);
			visit(p);
			p = p->rchild;
		}
	}
}
void Non_recursive_forproBitree(BiTNode* B) {
	stackNode S;
	initiation(S);
	Bitree p = B;
	Bitree r = B; // r用于记录最后一次访问的节点
	while (p || !isEmpty(S)) {
		if (p) {
			push(S, p);
			p = p->lchild;
		}
		else {
			GetTop(S,p);
			if (p->rchild && r != p->rchild) { //因为后续遍历是先访问右子树，再访问根节点，因此如果想访问一个节点，首先要看其右子树是否被访问
				p = p->rchild;
			}
			else {
				pop(S, p);
				visit(p);
				r = p;
				p = NULL;
			}
		}
	}
}

最后，附上案例的接口：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define MaxSize 20
#define ElemType char
typedef struct BiTNode {
	ElemType data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,*Bitree;
typedef struct stackNode {
	Bitree datas[MaxSize];
	int tag;
}stackNode;
typedef struct Queue {
	ElemType data[MaxSize];
	int rear, front;
}Queue;
void initiation(stackNode& S) {
	S.tag = -1;
}
bool isEmpty(stackNode S) {
	if (S.tag == -1) {
		return true;
	}
	return false;
}
bool isFlowOut(stackNode S) {
	if (S.tag == MaxSize) {
		return true;
	}
	return false;
}
bool push(stackNode& S, Bitree x) {
	if (isFlowOut(S)) {
		return false;
	}
	S.datas[++S.tag] = x;
	return true;
}
Bitree pop(stackNode& S, Bitree& e) {
	if (isEmpty(S)) {
		exit(0);
	}
	e = S.datas[S.tag--];
	return e;
}
bool visit(Bitree B) {
	if (B == NULL) {
		return false;
	}
	printf("%c", B->data);
	return true;
}