二叉树的非递归遍历（前序，后序，中序,层序）_二叉树层序遍历非递归

目录

一.先序遍历 

二.中序遍历

三.后序遍历 

四.层序遍历 

---

二叉树的遍历是指访问树中的每一个结点元素，且每个结点元素被访问一次。二叉树的遍历分为以下四种方法：

（1）先序遍历：先访问根结点，然后访问左子树，最后访问右子树。

（2）中序遍历：先访问左子树，然后访问根结点，最后访问右子树。

（3）后序遍历：先访问左子树，然后访问右子树，最后访问根结点。

（4）层序遍历：二叉树层序遍历，又称为广度优先遍历，其节点访问按照二叉树的层次，从第一层根结点开始向下逐层访问每层结点，同层结点按照从左到右的规则顺序访问。

给出一棵树：

一.先序遍历 

 那么先序遍历的顺序是：FCADBEHGM

在用代码建立的过程是：

（1）遇到一个结点，先输出，再把它压栈，并去遍历它的左子树。

（2）当左子树遍历结束后，从栈顶弹出这个结点。

（3）然后按其右指针再去先序遍历它的右子树。

先序遍历的代码如下：

void preorder(Bintree BT)
{
	stack s;
	Bintree PT=BT;
	s=createstack(s);//先向左
	while(PT||s->top!=-1){
		while(PT){
			printf("%c",PT->data);
			instack(s,PT);
			PT=PT->left;
		}
		if(s->top!=-1){
			PT=popstack(s);
			PT=PT->right;
		}
	}
	
}

代码解读：由于先序遍历的顺序是根左右，所以先访问根结点F，并把F压入栈，继续遍历F的左子树，并输出压栈，此时栈里面的元素有：F，C，A；但A的左节点是空，所以退出循环，开始弹出栈顶元素，访问栈顶元素的右子树，即A的右子树，为空，再继续重复操作。便可以访问到它的每一个元素。

二.中序遍历

中序遍历的顺序是：ACBDFHEMG

代码建立的过程是：

（1）遇到一个结点，就把它压入栈，并去遍历它的左子树。

（2）当左子树遍历结束后，从栈顶弹出这个结点，并输出它。

（3）然后按其右指针再去中序遍历该结点的右子树。

中序遍历的代码如下：

void preorder(Bintree BT)
{
	stack s;
	Bintree PT=BT;
	s=createstack(s);
	while(PT||s->top!=-1){
		while(PT){
			instack(s,PT);
			PT=PT->left;
		}
		if(s->top!=-1){
			PT=popstack(s);
			printf("%c",PT->data);
			PT=PT->right;
		}
	}
	
}

三.后序遍历 

后序遍历的顺序是：ABDCHMGEF

得知后序遍历，我们可以知道逆后序遍历的顺序为：FEGMHCDBA，对比于前序遍历的根左右来说，逆后序遍历为根右左。则就需要调换一下左右子树便可以实现逆后序遍历的操作，但是我们得到的结果是逆后序倒置过来的结果，我们可以设置两个堆栈，也可以设置一个数组。下面我们看代码：

void postorder(Bintree BT)
{
	stack s;
	char ch[maxsize];
	Bintree PT=BT;
	int i=0,j;
	s=createstack(s);
	while(PT||s->top!=-1){
		while(PT){
			ch[i++]=PT->data;
			instack(s,PT);
			PT=PT->right;
		}
		if(s->top!=-1){
			PT=popstack(s);
			PT=PT->left;
		}
	}
	ch[i]='\0';
	for(j=i-1;j>=0;j--)
	printf("%c",ch[j]);
}

四.层序遍历 

层序遍历二叉树的具体算法执行步骤如下：

(1).初始化队列为空

(2).从队列中取出一个元素，访问该元素所指结点

(3).若该元素所指结点的左右孩子结点非空，则将其左，右孩子的指针顺序入队。

代码如下：

void cengxu(Bintree BT)
{
	queue Q;
	Bintree PT=BT;
	if(BT==NULL)
	return;
	Q=createqueue(Q);
	enqueue(Q,PT);
	while(Q->front!=Q->rear){
		PT=deletequeue(Q);
		printf("%c",PT->data);
		if(PT->left!=NULL)
		enqueue(Q,PT->left);
		if(PT->right!=NULL)
		enqueue(Q,PT->right);
	}
}