二叉树深度优先遍历算法的非递归实现

非递归实现就是自己定义栈来实现，而递归实现就是调用系统定义的栈。

示例二叉树如下：

（1）先序遍历非递归算法 

先序遍历非递归算法的思路：

• 在二叉树先序遍历非递归算法中，先将根结点压栈，在栈不为空的时候执行循环：
• 让栈顶元素p出栈，访问栈顶元素p，如果p的右孩子不为空，则让其右孩子先进栈，
• 如果p的左孩子不为空，则再让其左孩子进栈(注意：进栈顺序一定是先右孩子，再左孩子)。

图解：

核心代码：

/* 先序遍历非递归算法 */ 
void preOrderNonrecursion(BTNode *bt){
	if(bt!=NULL){
		BTNode *stack[maxSize];// 定义一个栈
		int top=-1;// 初始化一个栈
		BTNode *p;
		stack[++top]=bt;// 根节点入栈
		while(top!=-1){// 当栈不空的时候执行循环，栈空循环退出
			p=stack[top--];// 出栈并输出栈顶结点
			printf("%c",p->data);// 访问p结点的数据
			if(p->rchild!=NULL){// 栈顶结点的右孩子存在，则右孩子入栈
				stack[++top]=p->rchild; 
			} 
			if(p->lchild!=NULL){// 栈顶结点的左孩子存在，则左孩子入栈 
				stack[++top]=p->lchild;
			}
		} 
	}
} 

（2）中序遍历非递归算法

类似于先序遍历。

先序遍历非递归算法的思路：

• 开始根节点入栈。
• 循环如下操作：如果栈顶结点的左孩子存在，则左孩子入栈；如果栈顶结点左孩子不存在，则出栈并输出栈顶结点，然后检查其右孩子是否存在，如果存在，则右孩子入栈。
• 当栈空时算法结束。

图解：

核心代码：

/* 中序遍历非递归算法 */
void inOrderNonrecursion(BTNode *bt) {
	if(bt!=NULL) {
		BTNode *stack[maxSize];// 定义栈
		int top=-1;// 初始化栈
		BTNode *p=bt;
		/* 下边这个循环完成中序遍历。注意：在中序遍历的过程中的进栈与出栈过程中会出现栈空状态，但这时遍历没有结束，因为根节点的右子树还没有遍历，此时p非空，根据这一点来维持循环的进行 */
		while(top!=-1||p!=NULL) {
			while(p!=NULL) { // 左孩子存在，则左孩子入栈
				stack[++top]=p;
				p=p->lchild;
			}
			if(top!=-1) { // 在栈不空的情况下输出栈顶结点
				p=stack[top--];
				printf("%c",p->data);// 打印出栈结点的数据
				p=p->rchild;
			}
		}
	}
}

（3）后序遍历非递归算法

首先手工写出对上图中二叉树进行先序和后序遍历的序列。

先序遍历序列: 1、 2、3、5、4

后序遍历序列: 3、5、2、4. 1

把后序遍历序列逆序得:

逆后序遍历序列: 1、4、2、5、3

观察发现，逆后序遍历序列和先序遍历序列有一定的联系，遵后序遍历序列只不过是先序遍历过程中对左右子树遍历顺序交换所得到的结果。

因此，只需要将前边讲到的非递归先序遍历算法中对左右子树的遍历顾序交换就可以得到逆后序遍历序列，然后将逆后序遍历序列逆序就得到了后字海历字列。因此我们需要两个栈，个栈 stackl 用来辅助做逆后序遍历(将先序遍历的左、右子树遍历顺序交换的遍历方式称为逆后序遍历)并将遍历结果序列压入另一个栈stack2, 然后将stack2 中的元素全部出栈，所得到的序列即为后序遍历序列。具体的过程如下：

核心代码如下：

/* 后序遍历非递归算法 */
void postOrderNonrecursion(BTNode *bt) {
	if(bt!=NULL) {
		/* 定义两个栈 */
		BTNode *stack1[maxSize];
		int top1=-1;// 初始化栈
		BTNode *stack2[maxSize];
		int top2=-1;
		BTNode *p=NULL;
		stack1[++top1]=bt;// 将根节点入栈1
		while(top1!=-1) {
			p=stack1[top1--];// 出栈栈顶结点
			stack2[++top2]=p;// 注意这里和先序遍历的区别，输出改为如stack2
			/* 注意：下边这两个if语句和先序遍历的区别，左、右孩子的入栈顺序相反 */
			if(p->lchild!=NULL) {
				stack1[++top1]=p->lchild;
			}
			if(p->rchild!=NULL) {
				stack1[++top1]=p->rchild;
			}
		}
		while(top2!=-1) {
			/* 出栈序列即为后序遍历序列 */
			p=stack2[top2--];
			printf("%c",p->data);// 打印结点的值
		}
	}
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

#define maxSize 20

/* 数结构体类型定义*/
typedef struct BTNode {
	char data;// 这里默认结点data域为char类型
	struct BTNode *lchild;// 左孩子指针域
	struct BTNode *rchild;// 右孩子指针域
} BTNode,*BiTree;

/* 根据输入创建二叉树 */
/* 例：123##5##4## */
void CreatBiNode(BTNode **Node) { //此处应注意传递的参数（二重指针）
	char data;
	scanf("%c", &data);

	*Node = (BiTree)malloc(sizeof(BTNode));
	if (data == '#') {
		*Node = NULL;
	} else if ((data != '#') && (*Node)) {
		(*Node)->data = data;
		(*Node)->lchild = NULL;
		(*Node)->rchild = NULL;
		CreatBiNode(&(*Node)->lchild);
		CreatBiNode(&(*Node)->rchild);
	}
}

/* 先序遍历非递归算法 */
void preOrderNonrecursion(BTNode *bt) {
	if(bt!=NULL) {
		BTNode *stack[maxSize];// 定义一个栈
		int top=-1;// 初始化一个栈
		BTNode *p;
		stack[++top]=bt;// 根节点入栈
		while(top!=-1) { // 当栈不空的时候执行循环，栈空循环退出
			p=stack[top--];// 出栈并输出栈顶结点
			printf("%c",p->data);// 访问p结点的数据
			if(p->rchild!=NULL) { // 栈顶结点的右孩子存在，则右孩子入栈
				stack[++top]=p->rchild;
			}
			if(p->lchild!=NULL) { // 栈顶结点的左孩子存在，则左孩子入栈
				stack[++top]=p->lchild;
			}
		}
	}
}

/* 中序遍历非递归算法 */
void inOrderNonrecursion(BTNode *bt) {
	if(bt!=NULL) {
		BTNode *stack[maxSize];// 定义栈
		int top=-1;// 初始化栈
		BTNode *p=bt;
		/* 下边这个循环完成中序遍历。注意：在中序遍历的过程中的进栈与出栈过程中会出现栈空状态，但这时遍历没有结束，因为根节点的右子树还没有遍历，此时p非空，根据这一点来维持循环的进行 */
		while(top!=-1||p!=NULL) {
			while(p!=NULL) { // 左孩子存在，则左孩子入栈
				stack[++top]=p;
				p=p->lchild;
			}
			if(top!=-1) { // 在栈不空的情况下输出栈顶结点
				p=stack[top--];
				printf("%c",p->data);// 打印出栈结点的数据
				p=p->rchild;
			}
		}
	}
}

/* 后序遍历非递归算法 */
void postOrderNonrecursion(BTNode *bt) {
	if(bt!=NULL) {
		/* 定义两个栈 */
		BTNode *stack1[maxSize];
		int top1=-1;// 初始化栈
		BTNode *stack2[maxSize];
		int top2=-1;
		BTNode *p=NULL;
		stack1[++top1]=bt;// 将根节点入栈1
		while(top1!=-1) {
			p=stack1[top1--];// 出栈栈顶结点
			stack2[++top2]=p;// 注意这里和先序遍历的区别，输出改为如stack2
			/* 注意：下边这两个if语句和先序遍历的区别，左、右孩子的入栈顺序相反 */
			if(p->lchild!=NULL) {
				stack1[++top1]=p->lchild;
			}
			if(p->rchild!=NULL) {
				stack1[++top1]=p->rchild;
			}
		}
		while(top2!=-1) {
			/* 出栈序列即为后序遍历序列 */
			p=stack2[top2--];
			printf("%c",p->data);// 打印结点的值
		}
	}
}

int main() {
	printf("先序输入二叉树(空结点用'#'表示):");
	BiTree T=NULL;
	CreatBiNode(&T);// 创建二叉树

	/* 先序遍历 */
	printf("先序遍历：");
	preOrderNonrecursion(T);

	/* 中序遍历 */
	printf("\n中序遍历：");
	inOrderNonrecursion(T);

	/* 后序遍历 */
	printf("\n后序遍历：");
	postOrderNonrecursion(T);

	return 0;
}

运行结果如下：

线索树

线索二叉树可以将用户栈也省掉，把二叉树的遍历过程线性化，进一步提高效率。

线索二叉树是利用二叉链表的空链域。

（1）中序线索二叉树的构造

线索二叉树的结点构造如下：

lchild

ltag

data

rtag

rchild

在二叉树线索化的过程中会把树中的空指针利用起来作为寻找当前结点前驱或后继的线索，这样就出现了一个问题，即线索和树中原有指向孩子结点的指针无法区分。上边的结点设计就是为了区分这两类指针，其中，Itag 和rtag为标识域，它们的具体意义如下:

1)如果Itag=0, 则表示lchild为指针，指向结点的左孩子；如果ltag=1, 则表示lchild 为线索，指向结点的直接前驱。

2)如果rtag=0,则表示rchild为指针，指向结点的石孩子；如果rtag=1,则表示rchild为线索，指向结点的直接后继。

对应的线索二叉树的结点定义如下:

typedef struct TBTNode
{
    char data;// 结点信息
    int ltag;// 如果ltag为0表示lchild为指针，指向结点的左孩子；如果ltag为1，则表示lchild为线索，指向结点的直接前驱
    int rtag;// 如果rtag为0表示rchild为指针，指向结点的右孩子；如果rtag为0，则表示rchild为线索，指向结点的直接后继
    struct TBTNode *lchild;// 左孩子
    struct TBTNode *rchild;// 右孩子
}TBTNode;

线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树。对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树。

二叉树线索化的图解如下：

二叉树中序线索化分析:

1) 既然要对二又树进行中序线索化，首先要有个中序遍历的框架，这里采用二叉树中序递归遍历算法，在遍历过程中连接上合适的线索即可。

2) 线索化的规则是，左线索指针指向当前结点在中序遍历序列中的前驱结点，右线索指针指向后继结点。因此我们需要一个指针P指向当前正在访问的结点，pre指向p的前驱结点，p的左线索如果存在则让其指向pre, pre 的右线索如果存在则让其指向p，因为p是pre的后继结点，这样就完成了一对线索的连接。如上图所示，某一时刻p指向A, pre 指向了中序遍历过程中A的前驱D，A是D的后继，D的右线索存在则指向A。按照这样的规则一直进行下去，当整棵二叉树遍历完成的时候，线索化也就完成了。

3)上一步中保持pre始终指向P前驱的具体过程是，当p将要离开一个访问过的结点时，pre指向p；当p来到一个新结点时，pre显然指向的是此时P所指结点的前驱结点。

故通过中序遍历二叉树线索化的递归算法代码如下：

/* 通过中序遍历对二叉树线索化的递归算法 */ 
void inThread(TBTNode *p,TBTNode *&pre) {
	if(p!=NULL) {
		inThread(p->lchild,pre); // 递归，左子树线索化
		if(p->lchild==NULL) { // 建立当前结点前驱线索
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL) { // 建立前驱结点的后继线索
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;// pre指向当前的p，作为p将要指向的下一个结点的前驱结点指示指针
		inThread(p->rchild,pre);// p指向一个新的结点，此时pre和p分别指向的结点形成了一个前驱后继对为下一次线索的连接做准备。递归，右子树线索化
	}
}

通过中序遍历建立中序线索二叉树的主程序如下：

/* 通过中序遍历建立中序线索二叉树 */
void createThread(TBTNode *root){
	TBTNode *pre=NULL;// 前驱结点指针
	if(root!=NULL){
		inThread(root,pre);
		pre->rchild=NULL;// 非空二叉树，线索化
		pre->rtag=1; 
	} 
} 

（2）遍历中序线索二叉树

访问运算主要是为遍历中序线索二叉树服务的。这种遍历不再需要栈，因为它利用了隐含在线索二叉树的前驱和后继信息。

求以p为根的中序线索二叉树中，中序序列下的第一个结点的算法如下：

TBTNode *First(TBTNode *p){
	while(p->ltag==0){
		p=p->lchild;// 最左下结点（不一定是叶结点） 
	}
	return p;
}

求在中序线索二叉树中，结点p在中序下的后继结点的算法如下：

TBTNode *Next(TBTNode *p){
	if(p->rtag==0){
		return First(p->rchild);
	}else{
		return p->rchild;// rtag==1，直接返回后继线索 
	}
}

如果把程序中First 的ltag和lchild换成rtag和rchild,同时把函数名First 换成Last,则可得到求中序序列下最后一个结点的函数Last(;如果把程序中Next的rtag和rchild换成ltag和lchild.并同时把函数First(换成函数Last(,再把函数名Next改为Prior则可得到求中序序列下前驱结点的函数Prior0)。

在中序线索二叉树上执行中序遍历的算法：

void Inorder(TBTNode *root){
	for(TBTNode *p=First(root);p!=NULL;p=Next(p)){
		printf("%c",p->data);
	}
}

（3）前序线索二叉树

前序线索二叉树和中序线索二叉树代码相似，最大的区别就是把连接线索的代码提到了两递归入口前边。

void preThread(TBTNode *p,TBTNode *&pre){
	if(p!=NULL){
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(p!=NULL&&pre->rchild==NULL){
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
		/* 注意：这里在递归入口处有限制条件，左、右指针不是线索才继续递归 */
		if(p->ltag==0){
			preThread(p->lchild,pre);
		} 
		if(p->rtag==0){
			preThread(p->rchild,pre);
		}
	}
} 

在前序线索二叉树上执行前序遍历的算法如下：

void preOrder(TBTNode *root){
	if(root!=NULL){
		TBTNode *p=root;
		while(p!=NULL){
			while(p->ltag==0){// 左指针不是线索，则边访问边左移
				printf("%c",p->data);
				p=p->lchild; 
			}
			printf("%c",p->data);// 此时p左指针必为线索，但还没有被访问，则访问
			p=p->rchild;// 此时p左孩子不存在，则右指针若非空，则不论是否为线索都指向其后继 
		}
	}
}

（4）后序线索二叉树

后序线索二叉树代码和中序线索化代码极为相似，最大的区别就是把连接线索的代码放到了两递归入口后边。

void postThread(TBTNode *p,TBTNode *&pre){
	if(p!=NULL){
		postThread(p->lchild,pre);// 递归，左子树线索化
		postThread(p->rchild,pre);// 递归，右子树线索化
		if(p->lchild==NULL){// 建立当前结点的前驱线索
			p->lchild=pre;
			p->ltag=1; 
		} 
		if(pre!=NULL&&pre->rchild==NULL){// 建立前驱结点的后继线索 
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;
	}
}