二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历

目录

1.前序遍历

2.中序遍历

3.后序遍历

4.层序遍历

二叉树的遍历是指从根节点出发， 按照某种次序依次访问二叉树中所有结点， 使得每个结点被访问一次且仅被访问一次。二叉树的遍历方式很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：

1.前序遍历

前序遍历的规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示的二叉树遍历的顺序为ABDGHCEIF。

void PreOrder(tnode* t)
{
	if (t != NULL)
	{
		printf("%d ", t->data);
		PreOrder(t->left);
		PreOrder(t->right);
	}
}
           

非递归前序遍历：根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。对于任一结点P：

     1)访问结点P，并将结点P入栈;

     2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;

     3)直到P为NULL并且栈为空，则遍历结束。

void preOrder2(tnode* t)     //非递归前序遍历 
{
	stack<tnode*> s;
	tnode *p = t;
	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			cout << p->data << " ";
			s.push(p);
			p = p->left;
		}
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			p = p->right;
		}
	}
}
           

2.中序遍历

中序遍历的规则是若树为空，则空操作返回，否则从根结点开始中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示的二叉树遍历的顺序为：GDHBAEICF。

void inOrder(tnode* t)
{
	if (t != NULL)
	{
		inOrder(t->left);
		printf("%d ", t->data);
		inOrder(t->right);
	}
}
           

非递归中序遍历：根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

   对于任一结点P，

  1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；

  2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；

  3)直到P为NULL并且栈为空则遍历结束

void inOrder2(tnode* t)      //非递归中序遍历
{
	stack<tnode*> s;
	tnode *p = t;
	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			p = p->left;
		}
		if (!s.empty())
		{
			p = s.top();
			cout << p->data << " ";
			s.pop();
			p = p->right;
		}
	}
}
           

3.后序遍历

后序遍历的规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。如图所示的二叉树遍历的顺序为：GHDBIEFCA。

void PostOrder(tnode* t)
{
	if (t != NULL)
	{
		PostOrder(t->left);
		PostOrder(t->right);
		printf("%d ", t->data);
	}
}
           

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

void postOrder2(tnode *t)//后序遍历的非递归算法
{
	stack<tnode*> s;
	tnode *temp = t;
	while (temp != NULL || !s.empty())
	{
		while (temp != NULL)
		{
			temp->cishu = 1;       // 当前节点首次被访问
			s.push(temp);
			temp = temp->left;
		}
		if (!s.empty())
		{
			temp = s.top();
			if (temp->cishu == 1)   // 第一次出现在栈顶
			{

				temp->cishu++;
				s.push(temp);
				temp = temp->right;
			}
			
			if (temp->cishu == 2)//第二次输出并制空，防止陷入死循环
			{
				cout << temp->data;
				temp = NULL;
			}
		}
	}
}
           

另外一种遍历方法。

void postOrder3(tnode *t)
{
	if (t == NULL)
		return;
	stack<tnode*> s;
	//pCur:当前访问节点，pLastVisit:上次访问节点
	tnode* pCur, *pLastVisit;
	//pCur = root;
	pCur = t;
	pLastVisit = NULL;
	//先把pCur移动到左子树最下边
	while (pCur)
	{
		s.push(pCur);
		pCur = pCur->left;
	}
	while (!s.empty())
	{
		//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
		pCur = s.top();
		s.pop();
		//一个根节点被访问的前提是：无右子树或右子树已被访问过
		if (pCur->right == NULL || pCur->right == pLastVisit)
		{
			cout << pCur->data;
			//修改最近被访问的节点
			pLastVisit = pCur;
		}
		else
		{
			//根节点再次入栈
			s.push(pCur);
			//进入右子树，且可肯定右子树一定不为空
			pCur = pCur->right;
			while (pCur)
			{
				s.push(pCur);
				pCur = pCur->left;
			}
		}
	}
	cout << endl;
}
           

4.层序遍历

层序遍历的规则是若树为空，则空操作返回，否则从树的第一层，也就是树的根结点开始访问，从上而下逐层遍历，从左到右的顺序对结点逐个访问。如图所示的二叉树遍历的顺序为：ABCDEFGHI。

仔细看看层序遍历过程，其实就是从上到下，从左到右依次将每个数放入到队列中，然后按顺序依次打印就是想要的结果。

实现过程

1、首先将二叉树的根节点push到队列中，判断队列不为NULL，就输出队头的元素，

2、判断节点如果有孩子，就将孩子push到队列中，

3、遍历过的节点出队列，

4、循环以上操作，直到Tree == NULL。

void FloorPrint(tnode* t) //层序遍历_队列实现
{
	queue<tnode*> q;
	if (t != NULL)
	{
		q.push(t);   //根节点进队列
	}

	while (q.empty() == false)  //队列不为空判断
	{
		cout << q.front()->data << " → ";

		if (q.front()->left != NULL)   //如果有左孩子，leftChild入队列
		{
			q.push(q.front()->left);
		}

		if (q.front()->right != NULL)   //如果有右孩子，rightChild入队列
		{
			q.push(q.front()->right);
		}
		q.pop();  //已经遍历过的节点出队列
	}
}