二叉树的非递归遍历算法C语言实现（详细注释版）

二叉树的非递归算法遍历分为：先序遍历，中序遍历，后序遍历。

此文章我会根据先、中、后的顺序为大家用C语言实现全部代码。

顾名思义先序遍历是先遍历根节点，随后是左孩子，右孩子 。

中序遍历与后序遍历可以通过类比改变根节点相对左右孩子的遍历顺序。

我不为大家讲解先、中、后遍历的实现思想了。

我为我所写的每一行代码都书写了详细的注释，为大家看懂代码的目的及功能提供便利。

所写注释可能会有少部分错别字，如果发现欢迎大家及时提出。

先为大家附上代码实现结果图：

马上为大家附上全部代码：

#include 
#include 

//创建节点结构体

typedef struct{
	char data;                            //节点数据
	struct BTNode * LChild, * RChild;	  //左右孩子
}BTNode;

//创建树
BTNode *CreateTree(void){
	BTNode *T,*head,*s[50];		//T：用于储存和返回创建的树。  head：用于创建节点。  s[50]：用于储存树。
	char ch; 					//用于获取树的节点的data数据
	int i,j; 					//i：用于定位树节点的序号（i=0时退出）。  j：用于定位该树节点的父节点
	while (1){ 
		printf("please enter a number:");				
		scanf("%d", &i);								//输入节点插入位置。
		getchar();										//吸取输入后的回车符 防止回车符对数据影响
		if (i==0) 										//当i=0时结束输入数据
			break;
		else{ 
			printf("please enter a char:");
			ch=getchar();								//ch用于获取节点的储存数据
			head=(BTNode *)malloc(sizeof(BTNode));		//为head分配内存
			head->data=ch;								//将ch获取的值赋给head的data数据
			head->LChild=head->RChild=NULL;				//将head的左右孩子节点指向空（初始化左右孩子节点）
			s[i]=head;									//将该节点对应的位置赋值到树的列表中
			if (i==1) 									//如果i=1则该节点为树的根
				T=head; 
			else { 
				j=i/2;									//否则用i/2定位到本次赋值节点的父节点并将父节点的位置赋值给j
				if (i%2==0) 							//如果i可以被2整除则该节点是其父节点的左孩子
					s[j]->LChild=head;					
				else 									//否则该节点是其父节点的右孩子
					s[j]->RChild=head;
			}
		}
	}
	return(T) ;		//将创建好的树返回
}

//非递归算法的先序遍历
void LeftShow(BTNode *head){
	BTNode * rchildlist[50];		//创建一个用于储存右孩子的栈。因为输出父节点，然后输出左孩子。所以需要将右孩子储存起来。
	BTNode * show=head;				//将show指针初始化为head的地址。 show用于遍历时储存正在遍历的节点。从根节点开始遍历。
	int i=0;						//i为rchildlist栈顶。
	while(1){
		if(show==NULL){				//当遍历到的节点是NULL时。进行分情况判定
			if(i==0)						//如果栈此时也为空。则已经遍历完整个树。就可以退出循环。
				break;
			else{							//如果栈此时不为空。则执行退栈 *** 作。将退栈的值赋值为下一个需要遍历的节点。此时是左孩子已经遍历完，需要遍历右孩子。
				show=rchildlist[i];						//将退栈的值赋值为下一个需要遍历的节点。
				i--;									//执行退栈 *** 作
			}
		}else {						//当遍历到的节点不为NULL时。
			printf("%c\t",show->data);		//输出该节点储存的值
			if(show->RChild!=NULL){			//判断该节点有没有右孩子。如果有右孩子则使右孩子进栈。
				i++;									//执行进栈 *** 作
				rchildlist[i]=(BTNode *)show->RChild;	//将右孩子进栈。
			}
			show=(BTNode *)show->LChild;	//将该节点的左孩子赋值为下一个需要遍历的节点。
		}
	}
}

//非递归算法的中序遍历
void MiddleShow(BTNode * head){
	BTNode * fatherlist[50];		//创建一个用于储存父节点的栈。因为需要先输出左孩子。所以需要将父节点储存起来。同时可以通过父节点找到右孩子。
	BTNode * show =head;			//将show指针初始化为head的地址。 show用于遍历时储存正在遍历的节点。从根节点开始遍历。
	int i=0;						//i为fatherlist的栈顶。
	while (1) {
		if(show ==NULL){			//当遍历到的节点是NULL时。进行分情况判定。
			if(i==0)						//如果此时栈也为空。则已经遍历完整个树。就可以退出循环。
				break;
			else{							//如果此时栈不为空。进行退栈 *** 作。将退栈的值赋值为当前便利的节点。此时左孩子已经遍历完，需要最后一个输出父节点的值。
				show=fatherlist[i];						//将退栈的值赋值为当前便利的节点。
				printf("%c\t",show->data);				//输出该节点的data值。
				i--;									//执行退栈 *** 作。
				if(show->RChild!=NULL){		//判断该节点是否存在右孩子。
					show=(BTNode *)show->RChild;		//如果有右孩子。则将右孩子赋值为下一个需要遍历的节点。
				}else{
					show=NULL;							//否则继续返回为NULL。此时的目的为继续退栈。用于输出上一个父节点的值。
				}
			}
		}else {						//当遍历到的节点不为NULL时。
			i++;							//执行进栈 *** 作。
			fatherlist[i]=show;				//将该遍历节点进栈。
			show=(BTNode *)show->LChild;	//将该遍历节点的左孩子赋值为下一个需要遍历的节点。
		}
	}
}

//非递归算法的后续遍历
void RightShow(BTNode * head){
	BTNode * fatherlist[50];		//创建一个用于储存父节点的栈。因为需要先输出左、右孩子。所以需要将父节点储存起来。
	BTNode * show=head;				//将show指针初始化为head的地址。 show用于遍历时储存正在遍历的节点。从根节点开始遍历。
	int taglist[50];				//创建一个与父节点同步的栈。用于判断该父节点是第几次被访问。因为父节点需要退出两次。只有第二次才需要输出值。第一次用于寻找右孩子。
	int i=0;						//i为fatherlist的栈顶。同时也是taglist的栈顶。
	int tag=0;						//tag用于判断父节点被访问的次数。第一次被取出为0，第二次被取出为1。为1时可以输出值。
	while (1) {
		if(show==NULL){				//当遍历到的节点是NULL时。进行分情况判定。
			if(i==0)						//如果此时栈也为空。则已经遍历完整个树。就可以退出循环。
				break;
			else{							//如果此时栈不为空。进行退栈 *** 作。将退栈的值赋值为当前遍历的节点。此时左孩子已经遍历完，需要分情况判断。
				show=fatherlist[i];						//将退栈的值赋值为当前遍历的节点。
				if(taglist[i]==0){						//如果此时该父节点是第一次访问则为其tag值+1。并将该节点的右孩子赋值为下一个需要遍历的节点。
					taglist[i]++;								//为其tag值+1。
					show=(BTNode *)show->RChild;				//将该节点的右孩子赋值为下一个需要遍历的节点。
				}else{									//如果此时该父节点是第二次访问。则输出该节点对应的data值，并执行退栈 *** 作。
					printf("%c\t",show->data);					//输出该节点对应的data值。
					i--;										//执行退栈 *** 作。
					show=NULL;									//继续返回为NULL。此时的目的为继续退栈。用于输出上一个父节点的值。
				}
			}
		}else{						//当遍历到的节点不为NULL时。
			i++;							//执行进栈 *** 作
			fatherlist[i]=show;				//将该遍历到的节点进栈。
			taglist[i]=tag;					//同时将该节点的tag值进栈。初始为0.
			show=(BTNode *)show->LChild;	//将该遍历节点的左孩子赋值为下一个需要遍历的节点。
		}
	}
}

int main(){
	printf("Create Tree::\n");
	BTNode * head=CreateTree();
	printf("\nLeftShow::\n");
	LeftShow(head);
	printf("\nMiddleShow::\n");
	MiddleShow(head);
	printf("\nRightShow::\n");
	RightShow(head);
	return 0;
}