二叉树遍历（前中后层序／非递归） (二)

stack s;
while(!node && !s.empty())
{
/*如果当前节点不为空，则直接访问，然后将节点存储到栈中（仅仅用来将来寻找右子节点），然后当前节点变为左字节点*/
if(node)
{
visit(node);
s.push(node);
node = node->left;
}
/*如果当前节点为空，则到栈中取出上一个节点，并找出右子节点进行访问*/
else
{
node = s.pop();
node = s.right;
}
}
}

四：中序非递归

[cpp]
/*
中序遍历非递归实现
用栈来实现，这种方式可以用递归的思路来理解
*/
void BT_InOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
while(!s.empty())
{
/*如果当前节点不为空，则不访问，而是将它放入栈中，然后当前节点变为左字节点；
一直采取这种方式，根据栈先进后出的特点，将来访问的时候左字节点在前，当前节点在后；
正好是中序遍历的特性
*/
if(!node)
{
push(node);
node = node->left();
}
/*如果当前节点为空，则去栈里取出节点访问，然后访问右子节点。
这里有些不好理解，其实这里的开端是左字节点为空了，所以访问了当前节点，然后右子节点；
同时当前节点为根的二叉树其实是上层的左字节点，依次类推正好是中序遍历的特性
*/
else
{
node = s.pop();
visit(node);
node = node->right;
}
}
}

/*
中序遍历非递归实现
用栈来实现，这种方式可以用递归的思路来理解
*/
void BT_InOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
while(!s.empty())
{
/*如果当前节点不为空，则不访问，而是将它放入栈中，然后当前节点变为左字节点；
一直采取这种方式，根据栈先进后出的特点，将来访问的时候左字节点在前，当前节点在后；
正好是中序遍历的特性
*/
if(!node)
{
push(node);
node = node->left();
}
/*如果当前节点为空，则去栈里取出节点访问，然后访问右子节点。
这里有些不好理解，其实这里的开端是左字节点为空了，所以访问了当前节点，然后右子节点；
同时当前节点为根的二叉树其实是上层的左字节点，依次类推正好是中序遍历的特性
*/
else
{
node = s.pop();
visit(node);
node = node->right;
}
}
}

五：后序非递归

[cpp]
/*
后序遍历非递归实现
用栈来实现，不是很好理解，但是起码不用借助各种标志位
思路如注释所写
*/
void BT_PostOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
BitTree tmp;//用来标志刚刚访问过的节点
while(!node && !s.empty())
{
//如果当前节点不为空，则压入栈，当前节点变为左字节点
if(node)
{
s.push(node);
node = node->left;
}
//如果为空，则需要根据栈顶的节点来判定下一步
else
{
//获取栈顶节点,不是pop
node = s.getPop();
//如果栈顶节点有右子节点，并且（这不好理解，但很重要）右子节点不是我们刚刚访问过的，
//则，我们要去右子树访问
if(node->right && node->right != tmp)
{
//把右子树当作一个新的开始进行访问：根节点压入栈，访问左字节点
s.push(node->right);
node = node->right->left;
}
//如果栈顶节点没有右子节点，或者我们刚刚访问过右子节点，则达到后序遍历的要求，我们可以访问当前节点
else
{
//访问当前节点，设置标志节点(tmp)为当前节点，当前节点置为空
node = s.pop();
visit(node);
tmp = node;
node = null;
}
}
}
}

/*
后序遍历非递归实现
用栈来实现，不是很好理解，但是起码不用借助各种标志位
思路如注释所写
*/
void BT_PostOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
BitTree tmp;//用来标志刚刚访问过的节点
while(!node && !s.empty())
{
//如果当前节点不为空，则压入栈，当前节点变为左字节点
if(node)
{
s.push(node);
node = node->left;
}
//如果为空，则需要根据栈顶的节点来判定下一步
else
{
//获取栈顶节点,不是pop
node = s.getPop();
//如果栈顶节点有右子节点，并且（这