二叉树前序、中序和后序的非递归遍历
非递归遍历二叉树利用栈的先进先出特点完成实现
创新互联客户idc服务中心,提供联通服务器托管、成都服务器、成都主机托管、成都双线服务器等业务的一站式服务。通过各地的服务中心,我们向成都用户提供优质廉价的产品以及开放、透明、稳定、高性价比的服务,资深网络工程师在机房提供7*24小时标准级技术保障。
前序比较好理解先压根入栈,在while里面访问根,根出栈,再压入右子树,左子树,这样的遍历二叉树就是前序遍历了。
void PrevOrdr_NonR()
{
stack
s.push(_root);
while(!s.empty())
{
BinaryTreeNode
s.pop();
cout<
if(top->_right)
s.push(top->_right);
if(top->_left)
s.push(top->_left);
}
cout< } 中序的遍历顺序是左子树、根节点、右子树。 void InOreder_NonR() { stack BinaryTreeNode while(cur || !s.empty()) { while(cur)//把左路径的节点全部压入栈 { s.push(cur); cur = cur->_left; } if(!s.empty()) { BinaryTreeNode s.pop(); cout< cur = cur->_right;//把cur指向最后一个左节点的右节点 } } cout< } 后序遍历是左子树、右子树、根节点。 void PostOrder_NonR() { stack BinaryTreeNode BinaryTreeNode while(cur || s.empty()) { while(cur)//左路径的节点入栈 { s.push(cur); cur = cur->_left; } BinaryTreeNode if(top->_right == NULL || top->right == preVisited) //当子树遍历之后回退到上一个没有遍历的子树 { cout< preVisited = tmp; s.pop(); } else { cur = cur->left;//把cur指向右子树继续寻找左节点 } } }
本文名称:二叉树前序、中序和后序的非递归遍历
文章URL:http://pwwzsj.com/article/gescpo.html