数据结构：二叉树，递归转迭代

1. 二叉树的迭代法比较好理解，不详细说，

void PreOrderTraverse(BiTreeNode* pBiTree)
{
	if (!pBiTree) return;
	printf("%d ", pBiTree->data);
	PreOrderTraverse(pBiTree->left);
	PreOrderTraverse(pBiTree->right);
}

void InOrderTraverse(BiTreeNode* pBiTree)
{
	if (!pBiTree) return;
	InOrderTraverse(pBiTree->left);
	printf("%d ", pBiTree->data);
	InOrderTraverse(pBiTree->right);
}

void PostOrderTraverse(BiTreeNode* pBiTree)
{
	if (!pBiTree) return;
	PostOrderTraverse(pBiTree->left);
	PostOrderTraverse(pBiTree->right);
	printf("%d ", pBiTree->data);
}

2. 迭代法的说明：

通用方法中，用一个栈帧保存当前的一些数据，比如局部变量，返回值等，完全是机械式翻译。
二叉树的先序遍历，不需要额外信息保存，因为不用返回到父节点，因为已经处理完了，右左右子节点已在栈上，信息够了。而中序与后序是需要保存额外信息的。但通常不用保存栈帧的方法，有点技巧性，如下：

1. 后序访问：只要用一个指针记录上次访问的节点即可，等返回到父节点时，根据prev是左节点还是右节点即可满足遍历需要的信息了。这里用到了后序访问的特性，即父节点的前驱是左孩子，后继是右孩子。
2. 中序访问：中序访问时，访问完父节点后，就不需要再保存这个节点信息。所以可以每次访问时，可以向左走到头，访问完节点后，将其右孩子进栈，自己不需要再进栈了。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/s634772208/article/details/170636041