对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对 于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一 点。

创新互联是专业的云龙网站建设公司，云龙接单;提供成都做网站、网站设计、外贸营销网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行云龙网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

二叉树前序：访问根节点->左子树->右子树

（1）递归写法：

依次访问根节点、左子树、右子树，注意递归出口的结束。

void _PrevOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        cout << root->_data << "  ";
        _PrevOrder(root->_left);
        _PrevOrder(root->_right);
    }

（2）非递归写法：

用栈模拟前序遍历，栈是先进后出的特点，则将无条件地入栈根节点，在弹出根节点之前依次将根节点的右孩子节点和左孩子节点入栈……

void _PrevOrder(Node* root)
    {
        stack s;
        if (root == NULL)
        {
            return;
        }

        s.push(root);
        while (!s.empty())
        {
            root = s.top();
            cout << root->_data << "  ";
            s.pop();
            if (root->_right)
            {
                s.push(root->_right);
            }
            if (root->_left)
            {
                s.push(root->_left);
            }
        }
    }

二叉树中序：访问左子树->根节点->右子树

（1）递归写法：

依次访问左子树、根节点、右子树，注意递归出口的结束。

void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_data << "  ";
        _InOrder(root->_right);
    }

（2）非递归写法：

1、借助栈实现，先顺着二叉树找到最左边且最下边的节点3（一边找一边入栈），此时入栈序列为1，2，3。

2、此时按照中序遍历知道要弹出栈顶元素3，则弹出栈顶元素3。

3、下面该右子树了，那我们就要判断它的右子树是否为空，

     若为空，往回返，该打印2了，那就弹出栈顶元素2。

     若不为空，该右子树，指针指向右子树节点，再重复之前的步骤1，2，3……

void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        stack s;
        Node* cur = root;
      
        while (cur || !s.empty())
        {
            while (cur)
            {            
                s.push(cur);                
                cur = cur->_left;
            }

            cur = s.top();    //将栈顶元素保存，以便于后面判断它是否有右孩子
            cout << s.top()->_data << "  ";        
            s.pop();

            if (cur->_right == NULL)
            {
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }
    }

二叉树后序：访问左子树->右子树->根节点

（1）递归写法：

依次访问左子树、右子树、根节点，注意递归出口的结束。

void _PostOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _PostOrder(root->_left);
        _PostOrder(root->_right);
        cout << root->_data << "  ";
    }

（2）非递归写法：

1、后序遍历同样借助栈实现，先找到最左边且为最下面的节点3（一边入栈一边找）。

2、节点3若没有右孩子，那此时就打印节点3了，之后就弹出栈顶节点3

3、节点3若有右孩子，则要去继续遍历它的右子树，等遍历结束才可打印3.遍历重复步骤1，2，3……

void _PostOrderNon_R(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        Node* cur = root;
        Node* prev = NULL;
        stack s;
        
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);                
                cur = cur->_left;                
            }
            
            cur = s.top();
            if (cur->_right == NULL ||cur->_right==prev )
            {
                cout << cur->_data << "  ";
                s.pop();
                prev = cur;
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }                
    }

   

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

分享名称：【数据结构】二叉树(前、中、后）序遍历的递归与非递归算法-创新互联
网页地址：http://scyanting.com/article/cdpehd.html