【数据结构C语言版本】手把手教你实现二叉树的非递归前中后序遍历 （附完整代码）_数据结构先中后非递归法二叉树代码

写在前面

1.递归前序遍历

三句话实现递归前序遍历，我是一个精通人性的好代码！

1.1 原理，从递归遍历说起

1.1.1. 不撞NULL不回头

我们应明确，DLR的遍历法则需要运用到每一个结点上，即当用根结点访问到其左孩子结点后，其左孩子成为新的根结点，我们重新根据DLR顺序访问其左孩子的左孩子…如此重复，直到某左孩子结点没有它的左孩子，这才完成了DLR中对L的遍历访问。
此时此刻，我们停留在了二叉树最左端的叶子结点。

1.1.2. 你妈喊你回家吃饭啦

假设一位妈妈有两个孩子，开饭时妈妈能叫老大吃饭，必定也能叫老二吃饭。同理，能通过D结点遍历访问左孩子，必能通过D结点访问右孩子。
第一步结束后，我们对左孩子的访问结束，接下来我们通过该左孩子的D结点，去访问D结点的右孩子，对D结点的右孩子使用DLR法则进行左右子树的遍历，到这里，我们完成了三个结点的最小二叉树单元的前序遍历。接着，我们再找到当前D结点的D结点，再通过当前D结点的D结点找到右孩子，对D结点当前D结点的D结点的右孩子使用DLR法则进行左右子树的遍历…如是重复,从最左端的叶子结点处进行回溯

1.2 先序递归遍代码实现

//先序递归
void PreOrder1(BTreeNode *b)
{
	if(b!=NULL){
		printf("%c",b->data);	//访问根结点并打印 
		PreOrder1(b->lchild);   //遍历处理左孩子 
		PreOrder1(b->rchild);   //遍历处理左孩子 		
	}
}
1
2
3
4
5
6
7
8
9

1.3 手把手带您分析递归前序遍历算法

1.4 脑对脑带您分析递归前序遍历代码

正所谓“大道至简，知易行难，知行合一，得到功成”。为了让读者深入理解前序遍历优美的C语言三行诗，Joe树皮建立了一棵A(B,C)的简单小树带读者一同把玩把玩。

调用PreOrder1(b)
当前b为A结点，当前实参为A结点
printf("%c",b->data);直接访问打印A结点的值

调用PreOrder1(b->lchild)；访问到B结点
当前b为A结点，当前实参为B结点
printf("%c",b->data);直接访问打印B结点的值
调用PreOrder1(b->lchild)；访问到NULL
当前b为B结点，当前实参为NULL
本次调用结束
调用PreOrder1(b->rchild)；访问到NULL
当前b为B结点，当前实参为NULL
本次调用结束
完成对B的DLR

调用PreOrder1(b->rchild)；访问到C结点
完成对A的DLR
当前b为A结点，当前实参为C结点
printf("%c",b->data);直接访问打印C结点的值
调用PreOrder1(b->lchild)；访问到NULL
当前b为C结点，当前实参为NULL
本次调用结束
调用PreOrder1(b->rchild)；访问到NULL
当前b为C结点，当前实参为NULL
本次调用结束
完成对C的DLR

2.非递归遍历

引言

透过现象看本质，如何手动实现递归的重复调用、访问打印与回溯？

1）重复相同的操作，毫无疑问，在代码中我们应使用while、for之类的循环语句实现。
2)而对于访问，通过之前分析我们不难发现，这实则是将D结点、L结点、R结点按照规定顺序依次存进一片连续的存储单元。3)还需明确一个关系：当前孩子结点是下一个的根结点，当前根结点是上一个孩子结点，将此关系映射到数组内发现这两个结点在数组中位于相邻存储单元,因此我们可借数组解决回溯的问题。

回忆之前学习的数据结构知识，什么是运用数组对元素进行基本操作？我们不妨大胆猜想------栈 ！

按照这个思路继续分析下去，我们会发现：1）依次将元素存储进数组正是 入栈操作；2）当前访问的结点位于栈顶，我们将其打印后出栈，这正是取栈顶操作。3）每轮循环取栈顶操作之后，新的栈顶元素成为它按DLR顺序进栈的前一个结点，通过取栈顶操作，我们完成了对新栈顶元素R结点的回溯。4）除上述外，我们还需注意栈特有的先进后出的特点，在入栈操作时，先输出的应后入栈。

到这里，我想读者应该能明白：对二叉树的非递归操作，是通过栈的基本操作实现的。

2.1 前序遍历

2.1.1 先序遍历非递归代码实现

//先序非递归
void PreOrder2(BTreeNode *b)
{
	
	SqStack *s;			//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;	//用于读取栈顶元素结点
	BTreeNode *PNode;	//用于读取目标操作结点 
	
	if(b!=NULL){
		//（1）根结点进栈 
	//直接操作 
		/*
		s->top++;
		s->ST[s->top]=b;
		*/ 
	//Push函数操作
		Push(&s,&b); 		    
		//栈不为空循环进行 
		while(s->top>-1){
			//（2）取栈顶元素（D结点） 
			
			//直接操作 
			/*
			 TopNode=s->ST[s->top];
			 s->top--;
			 printf("%c",TopNode->data);
			*/
			
			//调用GetTop函数 
			printf("%c",GetTop(&s,&TopNode)->data);
			 
//因栈是先入后出 故DLR需先Push右子树再Push左子树
 
			//(3)通过TopNode处理右子树 Push
			
			if(TopNode->rchild!=NULL){
			//直接操作
			/* 
				s->top++;
				s->ST[s->top]=TopNode->rchild;
			*/
			//调用Push函数
				PNode=TopNode->rchild;
				Push(&s,&PNode); 
			} 
			
			//(4)通过TopNode处理左子树 Push
			if(TopNode->lchild!=NULL){
			//直接操作	
			/*
				s->top++;
				s->ST[s->top]=TopNode->lchild;
			*/
			//调用Push函数
				PNode=TopNode->lchild;
				Push(&s,&PNode); 
			} 
			
		} 
				
	} 
	printf("\n"); 
	StackDestory(&s);	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2.1.2 手把手带您分析非递归前序算法

Step1：创建树A(B(D,E),C(,F))
（若无特殊声明，此后前中后序遍历都研究这棵树）

Step2：初始化虚拟栈（前中后序都需要初始化栈操作，故此操作在之后的中后序算法分析里省略）

Step3：手工操作实现先序遍历过程

打印结果：ABDECF

2.1.3 脑对脑带您分析非递归前序代码

原理：先打印根结点的值，因栈是先入后出，根据DLR顺序得知需先右子树入栈再左子树入栈。

（1）根结点进栈
（栈Push 操作：top指针++，通过top指针控制ST数组下标存入根结点）
while（栈空）
{
（2）栈顶元素出栈并打印
（栈GetTop操作：当前栈顶元素出栈打印，top指针–）
（3）PNode指向当前栈顶元素以进行后续(4)(5)操作
（4）处理右子树
（栈Push 操作：右结点进栈，top指针++，通过top指针控制ST数组下标存入右结点。）
（5）处理左子树
（栈Push 操作：左结点进栈，top指针++，通过top指针控制ST数组下标存入左结点。）
}
}

（声明：栈操作的具体实现在中后序代码分析中省略）

2.2 中序遍历

2.2.1 中序遍历非递归代码实现

//中序非递归
void MidOrder2(BTreeNode *b)
{
	SqStack *s;			//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;	//用于读取栈顶元素结点
	BTreeNode *PNode;	//用于读取目标操作结点 
	
	if(b!=NULL){
		PNode=b;
		//栈不为空或者当前结点不为空循环继续 
		while(s->top>-1||PNode!=NULL){
		//(1)左孩子遍历进栈 
			while(PNode!=NULL){
			/*
				s->top++;
				s->ST[s->top]=PNode;
			*/
				Push(&s,&PNode);
				PNode=PNode->lchild;		
			}
		//(2)栈顶结点的右孩子为空可直接出栈
			/*
			TopNode=s->ST[s->top];
			s->top--;
			*/
			printf("%c",GetTop(&s,&TopNode)->data);
		//(3)若不为空则访问右孩子 进入while循环进栈 
			PNode=TopNode->rchild; 							
		}		
	} 
	printf("\n"); 
	StackDestory(&s);		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2.2.2 手把手带您分析非递归中序算法

2.2.3 脑对脑带您分析非递归中序代码

while（栈不为空||当前栈空但有右孩子未访问进栈）
{
每个结点根据LDR循环访问
while（当前根结点存在左(右)孩子）{
(1)左（右）孩子遍历进栈
}
(2)栈顶结点直接出栈
(3)PNode保存当前栈顶结点以便后续执行（4）操作
(4)通过PNode访问栈顶结点右孩子，若右孩子存在则进栈
if（右孩子存在）{
执行（1）操作，右孩子遍历进栈
}
}

2.3 后序遍历

2.3.1 后序遍历非递归代码实现

//后序非递归1

void EndOrder2(BTreeNode *b)
{
	SqStack *s;						//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;				//用于读取栈顶元素结点
	BTreeNode *PNode;				//用于读取目标操作结点 
	BTreeNode *VisitedNode=NULL;	//用于保存已访问结点 
	if(b!=NULL){
		PNode=b; 
		while(PNode!=NULL||s->top>-1){
	//(1)左孩子遍历进栈
			while(PNode!=NULL){
			/*
				s->top++;
				s->ST[s->top]=PNode;
			*/
				Push(&s,&PNode);
				PNode=PNode->lchild;			
			} 
			//取栈顶
			TopNode=s->ST[s->top]; //此处不能用GetTop因为top未变 
	//(2)栈顶元素若无右孩子或其右孩子已访问则可直接出栈 
		if(TopNode->rchild==NULL||VisitedNode==TopNode->rchild){
			/*
				printf("%c",TopNode->data);
				s->top--;
			*/
				printf("%c",GetTop(&s,&TopNode)->data);
				VisitedNode=TopNode;	//标记为已访问 便于下一轮D->rchild的判断 
				PNode=NULL;				//无右孩子进栈PNode置空跳过while循环 
			}
	//(3)否则访问右孩子 到while循环进栈
			else{
				PNode=TopNode->rchild;
			} 
		}
	} 
	printf("\n"); 
	StackDestory(&s);	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2.3.2 手把手带您分析非递归后序算法

2.3.3 脑对脑带您分析非递归后序代码

while(栈不为空||栈空但仍有右孩子未进栈)
{
每个结点根据LRD循环访问
while(当前根结点存在左（右）孩子 ){
(1)左（右）孩子遍历进栈
}
(2)TopNode指向栈顶元素（注意此处top未变）
(3)栈顶元素若无右孩子或其右孩子已访问则可直接出栈
if（栈顶元素若无右孩子||栈顶元素右孩子已访问）{
栈顶元素直接出栈
将出栈结点标记为已访问结点
}
(4)否则访问右孩子 到while循环进栈
else{
执行(1)步骤操作，右孩子进栈
}
}

2.4 简易后序遍历

2.4.1 原理

LRD可看成DRL的倒序，故我们可将结点按DLR遍历顺序先存入Traverse[MaxSize]数组 ，最后将数组元素倒序打印。

2.4.2 算法分析

由此上述分析可知，我们对前序非递归遍历做出两处修改即可实现后序遍历
（1）LRD->DRL->DLR
根据栈先进后出的原理，在DLR我们应先访问进栈右孩子再进栈左孩子，但访问左右孩子具体操作代码实现与先序遍历完全一致，故我们只需要将访问左右孩子的两端代码交换顺序即可。
(2)输出->存储
在先序遍历时，各结点按DLR顺序进栈，每轮循环通过GetTop取栈顶元素问打印。会发现，与前序遍历不同，此时我们不需要打印，我们只需要将原来打印的元素存储起来，其余操作代码实现完全一致。
故我们可定义一个数组，去存储我们原来每轮循环需要打印结点，循环结束，该数组内元素便是按照DRL顺序进行存储，还原成LRD的顺序，我们只需要将此数组倒序输出即可。

2.4.3 代码实现

//后序非递归2 倒序输出法 
void EndOrder3(BTreeNode *b)
{
	SqStack *s;						//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;				//用于读取栈顶元素结点
	BTreeNode *PNode;				//用于读取目标操作结点 
	BTreeNode *Traverse[MaxSize];	//临时按顺序存储结点 
	
	int index=0	;					//用于记录Traverse数组下标
	int i;							//用于倒序输出 
	
	if(b!=NULL){
	//（1）根结点进栈 
		Push(&s,&b); 		    
		//栈不为空循环进行 
		while(s->top>-1){
	//（2）取栈顶元素（D结点） 		
			Traverse[index++] =GetTop(&s,&TopNode);	
				 
//因栈是先入后出 故DRl需先Push左子树再Push右子树
 
	//(3)通过TopNode处理左子树 Push
			
			if(TopNode->lchild!=NULL){
				PNode=TopNode->lchild;
				Push(&s,&PNode); 
			} 
			
	//(4)通过TopNode处理右子树 Push
			if(TopNode->rchild!=NULL){
				PNode=TopNode->rchild;
				Push(&s,&PNode); 
			} 
			
		} 
				
	} 
	//倒序输出
	for(i=index-1;i>=0;i--)	{
		printf("%c",Traverse[i]->data);
	} 
	printf("\n"); 
	StackDestory(&s);	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

附录 （完整代码实现）

#include<stdio.h>
#include<malloc.h>

#define MaxSize 50 	      //虚拟栈最大存储个数 
#define MaxLength 50 	  //字符数组最大存储个数 


typedef char ElemType;//定义数据类型  此处暂定为字符型 

//二叉树存储结构
typedef struct node
{
	
	ElemType data	   ;//数据域 
	struct node *lchild;//左孩子 
	struct node *rchild;//右孩子 
	
}BTreeNode;

//虚拟栈的存储结构
typedef struct {
	int top;				//栈顶指针
	BTreeNode*ST[MaxSize];	//结构体类型的指针数组BTreeNode* 保存指向结点的结构体指针 
}SqStack; 

//创建新结点函数
void CreatNewNode(BTreeNode **b,ElemType data)
{
	(*b)=(BTreeNode*)malloc(sizeof(BTreeNode));
	(*b)->data=data;
	(*b)->lchild=NULL;
	(*b)->rchild=NULL;
}

//初始化虚拟栈
void StackInit(SqStack**s)
{
	(*s)=(SqStack*)malloc(sizeof(SqStack)); 
	(*s)->top=-1;	
}

//取栈顶 返回TopNode结点
//传入&TopNode才能使 GetTop中的TopNode与外部调用函数中的TopNode关联 
BTreeNode* GetTop(SqStack**s,BTreeNode **TopNode)
{
	(*TopNode)=(*s)->ST[(*s)->top];
	(*s)->top--;
	return (*TopNode); 
} 

//入栈

void Push(SqStack**s,BTreeNode **PNode)
{
	(*s)->top++;
	(*s)->ST[(*s)->top]=(*PNode);

} 

//销毁虚拟栈 
void StackDestory(SqStack**s)
{
	free(*s); 	
}

//初始化二叉树
void BTreeInit(BTreeNode **b)
{
	(*b)=(BTreeNode*)malloc(sizeof(BTreeNode));
	(*b)->lchild=NULL;
	(*b)->rchild=NULL;	
}

//建立二叉树
void BTreeCreat(BTreeNode **b,char *str)
{

	int k;			   //用于标记左右子树（k=1左子树，k=2右子树） 
	
	BTreeNode*q;	   //用于生成新结点 
	
	int j=0;		   //用于字符串数组的遍历 
	ElemType ch;	   //用于接收传进的字符
	ch=str[j]; 
	
	SqStack *s;	       //用于存储结点的虚拟栈 	
	StackInit(&s);	   //初始化虚拟栈	

	(*b)=NULL;		   //先将b置空以从根结点重新建立二叉树 

	while(ch!='\0')//字符串未扫描到结尾
	{
	
		switch(ch){
			//入栈 top++ , '('前的结点进栈 ，k=1
			case '(':
				s->top++;
				s->ST[s->top]=q;
				k=1;
				break;
			//出栈	top--		
			case ')':
				s->top--;
				break;
			//处理右孩子 k=2
			case ',':
				k=2; 
				break;
			//生成新结点并建立逻辑关系 
			default:
			    CreatNewNode(&q,ch);   		 //生成新结点
			 //b为空，则p为二叉树根结点 
			 	if((*b)==NULL){
			 		(*b)=q; 
				 } 
				else{
			 	  switch(k){
			 		case 1:
					    s->ST[s->top]->lchild=q;//k=1 q为左孩子
			 	    	break;
			 		case 2:
					 	s->ST[s->top]->rchild=q;//k=2 q为右孩子
					 	break;		  
				 }
			 }
	
		}		
		
	//扫描字符串下一个元素	
	 j++;
	 ch=str[j];
	} 
	//释放临时虚拟栈存储空间 
	StackDestory(&s);	
} 

//打印二叉树
void BTreePrint(BTreeNode *b)
{
	if(b!=NULL){
		//b不为空 打印根结点 
		printf("%c",b->data);
		//有孩子 打印"()" 
		if(b->lchild!=NULL||b->rchild!=NULL){
			printf("(");
			//递归处理左孩子 
			BTreePrint(b->lchild); 
			//如果有右孩子打印"," 
			if(b->rchild!=NULL){
				printf(",");
			}
			//递归处理右孩子 
			BTreePrint(b->rchild); 
		 	printf(")");	
		}		
	} 
		
} 

//先序递归
void PreOrder1(BTreeNode *b)
{
	if(b!=NULL){
		printf("%c",b->data);	//访问根结点并打印 
		PreOrder1(b->lchild);   //遍历处理左孩子 
		PreOrder1(b->rchild);   //遍历处理左孩子 		
	}

}

//先序非递归
void PreOrder2(BTreeNode *b)
{
	
	SqStack *s;			//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;	//用于读取栈顶元素结点
	BTreeNode *PNode;	//用于读取目标操作结点 
	
	if(b!=NULL){
		//（1）根结点进栈 
	//直接操作 
		/*
		s->top++;
		s->ST[s->top]=b;
		*/ 
	//Push函数操作
		Push(&s,&b); 		    
		//栈不为空循环进行 
		while(s->top>-1){
			//（2）取栈顶元素（D结点） 
			
			//直接操作 
			/*
			 TopNode=s->ST[s->top];
			 s->top--;
			 printf("%c",TopNode->data);
			*/
			
			//调用GetTop函数 
			printf("%c",GetTop(&s,&TopNode)->data);
			 
//因栈是先入后出 故DLR需先Push右子树再Push左子树
 
			//(3)通过TopNode处理右子树 Push
			
			if(TopNode->rchild!=NULL){
			//直接操作
			/* 
				s->top++;
				s->ST[s->top]=TopNode->rchild;
			*/
			//调用Push函数
				PNode=TopNode->rchild;
				Push(&s,&PNode); 
			} 
			
			//(4)通过TopNode处理左子树 Push
			if(TopNode->lchild!=NULL){
			//直接操作	
			/*
				s->top++;
				s->ST[s->top]=TopNode->lchild;
			*/
			//调用Push函数
				PNode=TopNode->lchild;
				Push(&s,&PNode); 
			} 
			
		} 
				
	} 
	printf("\n"); 
	StackDestory(&s);	
}



//中序递归
void MidOrder1(BTreeNode *b)
{
		if(b!=NULL){
		MidOrder1(b->lchild);   //遍历处理左孩子 
		printf("%c",b->data);	//访问根结点并打印 
		MidOrder1(b->rchild);   //遍历处理左孩子 		
	}
	
}

//中序非递归
void MidOrder2(BTreeNode *b)
{
	SqStack *s;			//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;	//用于读取栈顶元素结点
	BTreeNode *PNode;	//用于读取目标操作结点 
	
	if(b!=NULL){
		PNode=b;
		//栈不为空或者当前结点不为空循环继续 
		while(s->top>-1||PNode!=NULL){
		//(1)左孩子遍历进栈 
			while(PNode!=NULL){
			/*
				s->top++;
				s->ST[s->top]=PNode;
			*/
				Push(&s,&PNode);
				PNode=PNode->lchild;		
			}
		//(2)栈顶结点的右孩子为空可直接出栈
			/*
			TopNode=s->ST[s->top];
			s->top--;
			*/
			printf("%c",GetTop(&s,&TopNode)->data);
		//(3)若不为空则访问右孩子 进入while循环进栈 
			PNode=TopNode->rchild; 							
		}		
	} 
	printf("\n"); 
	StackDestory(&s);		
}



//后序递归
void EndOrder1(BTreeNode *b)
{
		if(b!=NULL){
		EndOrder1(b->lchild);   //遍历处理左孩子 
		EndOrder1(b->rchild);   //遍历处理左孩子 
		printf("%c",b->data);	//访问根结点并打印 	
	}	
}

//后序非递归1

void EndOrder2(BTreeNode *b)
{
	SqStack *s;						//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;				//用于读取栈顶元素结点
	BTreeNode *PNode;				//用于读取目标操作结点 
	BTreeNode *VisitedNode=NULL;	//用于保存已访问结点 
	if(b!=NULL){
		PNode=b; 
		while(PNode!=NULL||s->top>-1){
	//(1)左孩子遍历进栈
			while(PNode!=NULL){
			/*
				s->top++;
				s->ST[s->top]=PNode;
			*/
				Push(&s,&PNode);
				PNode=PNode->lchild;			
			} 
			//取栈顶
			TopNode=s->ST[s->top]; //此处不能用GetTop因为top未变 
	//(2)栈顶元素若无右孩子或其右孩子已访问则可直接出栈 
		if(TopNode->rchild==NULL||VisitedNode==TopNode->rchild){
			/*
				printf("%c",TopNode->data);
				s->top--;
			*/
				printf("%c",GetTop(&s,&TopNode)->data);
				VisitedNode=TopNode;	//标记为已访问 便于下一轮D->rchild的判断 
				PNode=NULL;				//无右孩子进栈PNode置空跳过while循环 
			}
	//(3)否则访问右孩子 到while循环进栈
			else{
				PNode=TopNode->rchild;
			} 
		}
	} 
	printf("\n"); 
	StackDestory(&s);	
}


 
/*
方法分析： 
LRD可看成DRL的倒序输出
故我们可将结点按DLR遍历顺序先存入Traverse[MaxSize]数组 
最后将数值元素倒序打印 
*/ 

//后序非递归2 倒序输出法 
void EndOrder3(BTreeNode *b)
{
	SqStack *s;						//创建虚拟栈 
	StackInit(&s);
	
	BTreeNode *TopNode;				//用于读取栈顶元素结点
	BTreeNode *PNode;				//用于读取目标操作结点 
	BTreeNode *Traverse[MaxSize];	//临时按顺序存储结点 
	
	int index=0	;					//用于记录Traverse数组下标
	int i;							//用于倒序输出 
	
	if(b!=NULL){
	//（1）根结点进栈 
		Push(&s,&b); 		    
		//栈不为空循环进行 
		while(s->top>-1){
	//（2）取栈顶元素（D结点） 		
			Traverse[index++] =GetTop(&s,&TopNode);	
				 
//因栈是先入后出 故DRl需先Push左子树再Push右子树
 
	//(3)通过TopNode处理左子树 Push
			
			if(TopNode->lchild!=NULL){
				PNode=TopNode->lchild;
				Push(&s,&PNode); 
			} 
			
	//(4)通过TopNode处理右子树 Push
			if(TopNode->rchild!=NULL){
				PNode=TopNode->rchild;
				Push(&s,&PNode); 
			} 
			
		} 
				
	} 
	//倒序输出
	for(i=index-1;i>=0;i--)	{
		printf("%c",Traverse[i]->data);
	} 
	printf("\n"); 
	StackDestory(&s);	
}

int main()
{
	BTreeNode*b;
	printf("(1)初始化二叉树\n"); 
	BTreeInit(&b);
	printf("(2)创建二叉树A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\n"); 
	BTreeCreat(&b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
	printf("(3)打印二叉树\n"); 
	printf("创建的二叉树为："); 
	BTreePrint(b);	
	printf("\n"); 	
	
	//1为递归 2为非递归 	
	printf("(4)前序遍历结果为：\n");
//	PreOrder1(b);	printf("\n"); 
	PreOrder2(b);
	printf("(5)中序遍历结果为:\n");
//	MidOrder1(b);	printf("\n"); 
	MidOrder2(b);
	printf("(6)后序遍历结果为：\n");
//	EndOrder1(b);	printf("\n"); 
	EndOrder2(b);   
//	EndOrder3(b);	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423