非递归实现二叉树的遍历（前序、中序、后序）-创新互联

树的定义本是递归定义，所以采用递归的方法实现遍历算法，更加让人理解，且代码简单方便。若采用非递归的方法实现，须得利用栈模拟实现。

    栈的特点（后进先出）

    非递归实现二叉树的前序遍历：

    原理如图所示：

    参考代码如下：

    void _PrevOrder(Node* root)//非递归实现前序遍历

    {

stack s;

if(root == NULL)

    return;

s.push(root);

while (!s.empty())

{

    root = s.top();

    cout<_data<<" ";

    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 s;

Node* cur = root;

while (cur || !s.empty())

{

    while (cur)

    {

        s.push(cur);

cur = cur->_left;

    }

    Node* top = s.top();

    cout<_data<<" ";

    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 s;

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<_data<<" ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;

}

}

    }

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。