非递归实现二叉树的遍历(前序、中序、后序)-创新互联
树的定义本是递归定义,所以采用递归的方法实现遍历算法,更加让人理解,且代码简单方便。若采用非递归的方法实现,须得利用栈模拟实现。
网站建设、成都网站建设的开发,更需要了解用户,从用户角度来建设网站,获得较好的用户体验。成都创新互联公司多年互联网经验,见的多,沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司,打造的就是网站建设产品直销的概念。选择成都创新互联公司,不只是建站,我们把建站作为产品,不断的更新、完善,让每位来访用户感受到浩方产品的价值服务。栈的特点(后进先出)
非递归实现二叉树的前序遍历:
原理如图所示:
参考代码如下:
void _PrevOrder(Node* root)//非递归实现前序遍历
{
stack
if(root == NULL)
return;
s.push(root);
while (!s.empty())
{
root = s.top();
cout<
s.pop();
if (root->_right)
{
s.push(root->_right);
}
if(root->_left)
{
s.push(root->_left);
}
}
}
非递归实现二叉树的中序遍历
原理:
先从二叉树的最左边进行遍历(1、2、3),且一边遍历,一边入栈,当当到达结点3时,因为3的左右子树都为空,此时需弹出结点3,栈顶元素变为2,再遍历2的右子树的左结点,因为4的左右子树都为空,此时需弹出2,压人4,左子树已遍历结束,弹出4,再弹出1,依照遍历左子树,遍历右子树。
参考代码如下:
void _InOrder(Node* root)//非递归实现中序遍历
{
stack
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
cout<
s.pop();
cur = top->_right;
}
}
非递归实现二叉树的后序遍历
步骤:
1、借助栈实现后序遍历,先找到最左边且为最下边的结点3(一边找,一边入栈)
2、若3没有右子树,则弹出3且打印结点3,还需要引入一个指向当前弹出结点的指针prev
3、若3有右子树,则需要遍历右子树,遍历结束才可以打印并弹出结点3,重复此三步骤可完成后序遍历。
参考代码如下:
void _PosOrder(Node* root)//非递归实现后序遍历
{
Node* cur = root;
Node* prev = NULL;
stack
if(root == NULL)
return;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();
if(cur->_right == NULL || cur->_right == prev)
{
cout<
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前标题:非递归实现二叉树的遍历(前序、中序、后序)-创新互联
分享URL:http://pwwzsj.com/article/ieioe.html