前言
在学习二叉树的过程中，二叉树的遍历是最基础的，但大多数人只学会了递归的写法，甚至不理解其根本，本篇文章带来二叉树遍历的非递归写法，无非就是借助栈或队列，标记域来完成非递归写法。
文章目录
一、二叉树的设计
typedef char ElemType;
typedef struct BtNode
{
ElemType data;
struct BtNode* leftchild;
struct BtNode* rightchild;
}BtNode, * BinaryTree;
二、二叉树的中序遍历
中序遍历，访问方式为 左子树——根节点——右子树。
1.方法
非递归写法：借用栈来实现
- 若结点和栈不为NULL， 将根结点入栈，如果，左子树不为NULL，则一直将左子树入栈，如果为NULL了，说明已经到了将要打印的结点
- 这时候取出栈顶的结点，打印该值
- 将该结点的右子树入栈，循环前两步。
2.图示
初始状态
一直入左子树结点，直到为NULL
2结点有右子树，所以将右子树继续入栈。
再重复规则，直到循环退出。
3.代码
// 非递归中序遍历
void NiceInOrder(BtNode* ptr)
{
if (ptr == NULL) return;
std::stack<BtNode*> st;
while (ptr != NULL || !st.empty())
{
while (ptr != NULL)
{
st.push(ptr);
ptr = ptr->leftchild;
}
ptr = st.top(); st.pop();
cout << ptr->data << " ";
ptr = ptr->rightchild;
}
cout << endl;
}
三、二叉树的先序遍历（非递归）
和中序遍历一样借用一个栈。
先序遍历顺序为：根节点——左子树——右子树。所以先打印数据，再入栈左子树。其他与中序遍历相同。
// 非递归先序遍历
void NicePreOrder(BtNode* ptr)
{
if (ptr == NULL) return;
std::stack<BtNode*> st;
while (ptr != NULL || !st.empty())
{
while (ptr != NULL)
{
cout << ptr->data << " ";
st.push(ptr);
ptr = ptr->leftchild;
}
ptr = st.top();
st.pop();
ptr = ptr->rightchild;
}
cout << endl;
}
四、二叉树的后序遍历（非递归）
后序遍历稍微复杂，若也是借用栈来实现，由于遍历方式是左子树——右子树——根节点。 所以在对某个结点出栈后，我们并不知道是否对该结点的右子树访问了没有。
1.方法一 ：栈＋标记
- 在利用栈的基础上，利用一个标记指针来跟踪当前结点
- 循环一直入栈左子树，左子树为NULL后，判断栈顶结点
- 如果当前结点右子树不为NULL或标记位在右子树，就可以打印该结点，并将标记位指向该结点。
- 如果不满足条件，说明右子树还有数据，那么就访问右子树。
- 循环上述步骤。
图示
初始状态
一直对左子树入栈直至左子树为NULL
打印该结点值，将标记位指向当前节点，并将ptr置为NULL
继续出栈后
发现标记位不在当前结点的右子树，那么继续将该结点入栈
重复上述规则
代码
// 非递归后序遍历
void NicePastOrder(BtNode* ptr)
{
if (ptr == NULL) return;
std::stack<BtNode*> st;
// 跟踪标记位
BtNode* tag = NULL;
while (ptr != NULL || !st.empty())
{
// 先入栈左子树
while (ptr != NULL)
{
st.push(ptr);
ptr = ptr->leftchild;
}
ptr = st.top(); st.pop();
// 如果当前结点右子树不为NULL或标记位在右子树
// 就可以打印该结点，并将标记位指向该结点
if (ptr->rightchild == NULL || ptr->rightchild == tag)
{
cout << ptr->data << " ";
tag = ptr;
ptr = NULL;
}
else // 否则就继续入栈，并访问它的右子树
{
st.push(ptr);
ptr = ptr->rightchild;
}
}
cout << endl;
}
2. 方法二：栈＋计数
在后序遍历过程中可以发现，每个结点都出栈了三次。
- 第一次入栈出栈，说明没有访问左子树，如果存在左子树，那么将左子树入栈。
- 当左子树成为叶子结点（即没有左右子树后），对其第二次入栈出栈，代表要访问右子树。
- 若右子树为NULL，则出栈后进行第三次入栈出栈，这个时候打印的就是该结点的值。
如图，1，2，3代表出栈次数
代码
设计一个类型，表示要存到栈里的类型，有二叉树类型的指针成员和计数成员pos，这个计数值代表出栈次数。
// 计数加栈
struct StkNode
{
BtNode* pnode;
int pos;
public:
StkNode(BtNode* node = nullptr, int n = 0)
: pnode(node), pos(n)
{
}
};
void StkPastOrder(BtNode* root)
{
if (root == nullptr) return;
std::stack<StkNode> st;
st.push(StkNode(root));
while (!st.empty())
{
StkNode node = st.top();
st.pop();
if (++node.pos == 3)
{
cout << node.pnode->data << " ";
}
else
{
st.push(node);
if (node.pos == 1 && node.pnode->leftchild != nullptr)
{
st.push(node.pnode->leftchild);
}
else if (node.pos == 2 && node.pnode->rightchild != nullptr)
{
st.push(node.pnode->rightchild);
}
}
}
cout << endl;
}
END
参考自leetcode:二叉树的遍历
