二叉树遍历相关算法题|后序遍历非递归|下到上左到右层次遍历|先序遍历非递归(C)

后序遍历非递归

编写后序遍历二叉树的非递归算法

算法思想

后序非递归遍历二叉树先访问左子树，再访问右子树，最后访问根节点

1. 沿着根的左孩子，依次入栈，直到左孩子为空。此时栈内元素依次为ABD
2. 读栈顶元素：若其右孩子不空且未被访问过，将右子树转执行1；否则，栈顶元素出栈并访问
   栈顶D的右孩子为空，出栈并访问，它是后序序列的第一个节点；栈顶B的右孩子不空且未被访问过，E入栈，栈顶E的左右孩子均为空，出栈并访问；栈顶B的右孩子不空但已被访问，B出栈并访问；栈顶A的右孩子不空且未被访问过，C入栈，栈顶C的左右孩子均为空，出栈并访问；栈顶A的右孩子不空但已被访问，A出栈并访问。由此得到后序序列DEBCA

必须要分清返回时是从左子树返回还是从右子树返回的，因此设定一个辅助指针r，用于指向最近访问过的节点。也可在节点中增加一个标志域，记录是否已被访问

初始化一个栈S，用工作指针cur指向根节点T，创建一个标记指针r初始化为NULL

开始遍历二叉树，当cur没有走到空节点，或者栈S不为空的时候，开始循环
首先cur指针从根节点开始每次都遍历左孩子，直到指向最高层的第一个节点D
cur每次指向cur的left来遍历，如果cur不为空，全部入栈，A，B，D，直到cur指向D的左孩子是NULL

之后走else的逻辑
让cur指向栈的栈顶元素，存的是D的位置，也就是cur指向D

因为后序是要左右中的顺序遍历，现在读取栈顶的D，是后序遍历的第一个节点，已经确保D没有左孩子，再看D有没有右孩子，因为D没有右孩子，D出栈，并访问D节点的数据，这表示以D为根节点的子树已经遍历完毕
将r指向cur也就是D节点，将cur指针置为NULL

因为cur为NULL，走else逻辑
指向栈顶元素指向的二叉树节点，也就是B

已知B的左子树D已经遍历完毕，现在应该遍历B的右子树，E
B有右孩子，且没有被访问过，将cur指向E节点

然后再循环走if逻辑，以E为根节点沿着左孩子遍历，全部入栈，由于E的左孩子为NULL，只把E入栈

由于cur指向NULL，再走else逻辑
读取E节点，由于E节点没有右孩子，所以判断E子树已被遍历完毕
将E弹出，访问E的数据，将r指向E，将cur置空

由于cur指向NULL，再走else逻辑，读取栈顶元素B，由于B有右孩子但是已经被访问过，直接弹出B，访问B的数据，将r指向B，cur指向NULL

后面同理遍历

void PostOrder(BTNode T)
{
	STInit(S);
	BTNode* cur = T;
	BTNode* r = NULL;
	while (cur || !STEmpty(S))
	{
		// 走到最左边
		if (cur)
		{
			STPush(S, cur);
			cur = cur->left;
		}
		// 向右
		else
		{
			// 读栈顶节点
			STTop(S, cur);
			// 若右子树存在，且未被访问过
			if (cur->right && cur->right != r)
				// 转向右
				cur = cur->right;
			// 否则弹出节点并访问
			else
			{
				// 将节点弹出
				STPop(S, cur);
				// 访问该节点
				visit(cur->data);
				// 记录最近访问过的节点
				r = cur;
				// 节点访问完后重置cur指针
				cur = NULL;
			}
		}
	}
}

• 每次入栈的都是要遍历以此为根节点的子树
• 首先将二叉树每一层的第一个节点都入栈，然后以最高层的第一个节点为根节点的子树也就是栈顶元素开始遍历
• 每次读取一个栈顶元素，要先判断它有没有右子树，如果没有右子树，则直接读取这个子树的根节点，并出栈，标记已被访问
• 每次出栈访问完一个节点就相当于遍历完以该节点为根的子树，需要将cur置为NULL
• 然后遍历下一个节点，也就是上一层的子树的根节点，如果有右子树，且没有被访问过，需要将这个节点入栈，直到把这棵子树的每一层的第一个节点都入栈
• 然后再次读栈顶元素，如果有右节点且已经被访问过，表示这个子树已经的左右已经遍历完毕，可以读取根节点
  先将每一层的左入栈，先遍历左，然后判断根有没有右，如果没有，直接访问根，弹出栈，然后继续访问栈里的左，如果有右，如果没有遍历过，将右入栈，遍历完右，弹出右，再读取栈顶的根，以次循环。

下到上左到右层次遍历

给出二叉树的自下而上，从右到左的层次遍历算法

算法思想

利用原有的层次遍历算法，出队的同时将各节点入栈，在所有节点入栈后再从栈顶开始依次访问

1. 把根节点入队列
2. 把一个元素出队列，遍历这个元素
3. 依次把这个元素的左孩子，右孩子入队列
4. 若队列不空，跳到2，否则结束
   要想下到上，右到左的顺序遍历树，就将树按上到下，左到右的层次遍历的顺序入栈，因为是曾自遍历，所以要先把根节点入队列，出队列入栈的时候再读取下一层的节点
   初始化栈和队列，用cur指针指向T
   

将根节点入队

根节点出队，入栈

每次入栈，将该节点的左右孩子依次入队

B出队入栈，把B的左右孩子入队

C入栈，因为C没有孩子，不需要入队

直到最后全部入栈，也就是队列为空

然后依次弹出栈里的节点并读取，完成遍历

void InvertLevel(BTNode* T)
{
	ST S;
	Que Q;
	BTNode* cur = T;
	if (T)
	{
		// 栈初始化，栈中存放二叉树节点的指针
		STInit(S);
		// 队列初始化，队列中存放二叉树节点的指针
		QueInit(Q);
		EnQueue(Q, T);
		// 从上而下层次遍历
		while (!QueEmpty(Q))
		{
			// 出队
			DeQueue(Q, cur);
			// 入栈
			STPush(S, cur);
			if (cur->left)
				// 若左子女不空，则入队列
				EnQueue(Q, cur->left);
			if (cur->right)
				// 若右子女不空，则入队列
				EnQueue(Q, cur->right);
		}
		
		while (!STEmpty(S))
		{
			STPop(S, cur);
			visit(cur->data);
		}
	}
}

先序遍历非递归

利用栈的操作写出先序遍历二叉树的非递归算法

算法思想

先将根节点入栈

根节点出栈访问，右左孩子依次入栈

B出栈访问，然后ED入栈

然后D，E出栈访问，再到C，先序遍历完毕

先将根节点入栈，遍历根节点，然后右左孩子顺序入栈，出栈遍历的时候先出左，再出右
然后每次出一个节点，要把它的节点右左顺序入栈，
这样每棵子树都得按照根左右的顺序遍历

void PrevOrder(TNode* root)
{
	if (root = NULL)
		return;

	ST S;
	STInit(S);

	STPush(S, root);

	while (!STEmpty(S))
	{
		TNode* cur = STPop(S);
		visit(cur);

		if (cur->right)
			STPush(S, cur->right);
		if (cur->left)
			STPush(S, cur->left);
	}
}