您的位置: 首页  >  IT文章  >  二叉树前序、中序跟后序的遍历方法（递归、用栈和使用线索化）

二叉树前序、中序跟后序的遍历方法（递归、用栈和使用线索化）

分类: IT文章 • 2022-07-29 09:08:16
二叉树前序、中序和后序的遍历方法（递归、用栈和使用线索化）

0、二叉树数据结构定义

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

1、二叉树遍历的递归法

二叉树遍历的递归法比较简单，这里直接贴出代码。

先序遍历——按照“根节点-左孩子-右孩子”的顺序进行访问。
vector<int> pre_Traversal_Recursive(TreeNode* root)
{
    vector<int> result;//存放遍历之后结点的值
    pre_Traversal_Recursive_core(root, result);
    return result;
}

void pre_Traversal_Recursive_core(TreeNode* node, vector<int> &result)
{
    if (!node) return;
    result.push_back(node->val);
    pre_Traversal_Recursive_core(node->left, result);
    pre_Traversal_Recursive_core(node->right, result);
}
这里是根据LeetCode上的要求写的，因为需要一个vector容器返回遍历的结果，所以这里使用了两个函数实现。
中序遍历——按照“左孩子-根节点-右孩子”的顺序进行访问。 
vector<int> in_Traversal_Recursive(TreeNode* root)
{
    vector<int> result;//存放遍历之后结点的值
    pre_Traversal_Recursive_core(root, result);
    return result;
}

void in_Traversal_Recursive_core(TreeNode* node, vector<int> &result)
{
    if (!node) return;
    pre_Traversal_Recursive_core(node->left, result);
    result.push_back(node->val);
    pre_Traversal_Recursive_core(node->right, result);
}
后序遍历——按照“左孩子-右孩子-根节点”的顺序进行访问。 
vector<int> post_Traversal_Recursive(TreeNode* root)
{
    vector<int> result;//存放遍历之后结点的值
    pre_Traversal_Recursive_core(root, result);
    return result;
}

void post_Traversal_Recursive_core(TreeNode* node, vector<int> &result)
{
    if (!node) return;
    pre_Traversal_Recursive_core(node->left, result);
    pre_Traversal_Recursive_core(node->right, result);
    result.push_back(node->val);
}

2、用栈来实现二叉树的非递归遍历

先序遍历的非递归实现
先序遍历原理：对于任一结点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。
先序遍历的非递归代码实现
vector<int> pre_Traversal_Stack(TreeNode* root)
{
    stack<BTree> s;//用于存放树结点指针的栈
    TreeNode* pCur = root;//定义访问当前结点的指针
    vector<int> result;//存放遍历之后结点的值
    //直到当前结点pCur为NULL且栈为空时，循环结束
    while(pCur || !s.empty())
    {
        //从根结点开始，输出当前结点，并将其入栈
        //同时置其左孩子为当前结点，直至其没有左孩子，即当前结点为NULL
        result.push_back(pCur->val);//push_back函数会在容器尾部创建一个新元素，并使容器的长度加1
        s.push(pCur);
        pCur = pCur->left;
        //如果当前结点pCur为NULL且栈不空，则将栈顶结点出栈，
        //同时置其右孩子为当前结点，循环判断，直至pCur不为空
        while(!pCur && !s.empty())
        {
            pCur = s.top();
            s.pop();
            pCur = pCur->right;
        }
    }

    return result;
}
中序遍历的非递归实现
中序遍历实现原理：对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看其是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。
中序遍历非递归代码实现
vector<int> in_Traversal_Stack(TreeNode *root)
{
    TreeNode* pCur = root;
    stack<TreeNode*> s;
    vector<int> result;
    while(pCur || !s.empty())
    {
        if(pCur->left == NULL)
        {
            result.push_back(pCur->val);
            pCur = pCur->right;
        }
        else
        {
            s.push(pCur);
            pCur = pCur->left;
        }

        //如果当前结点pCur为NULL且栈不空，则将栈顶结点出栈，
        //同时置其右孩子为当前结点，循环判断，直至pCur不为空
        while(!pCur && !s.empty())
        {
            pCur = s.top();
            s.pop();
            result.push_back(pCur->val);
            pCur = pCur->right;
        }
    }
    return result;
}
后序遍历的非递归实现
后序遍历实现原理：对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。
后序遍历非递归代码实现
vector<int> post_Traversal_Stack(TreeNode* root)
{
    TreeNode* pCur = root;//记录当前正在处理的结点
    TreeNode* pre_Visited = NULL;//记录上一次已访问的结点
    stack<TreeNode*> s;//用于遍历
    vector<int> result;//记录遍历结果

    if(!pCur)//根结点为空，直接返回
        return result;
    s.push(pCur);
    while(!s.empty())
    {
        pCur = s.top();
        //case 1:当前结点的左右孩子都为空
        //case 2：或者当前结点的左孩子或右孩子已经被访问
        //则访问当前结点
        if(pCur->left == NULL && pCur->right == NULL ||
                pre_Visited && (pCur->left == pre_Visited || pCur->right == pre_Visited))
        {
            result.push_back(pCur->val);
            s.pop();
            pre_Visited = pCur;
        }
        else//如果条件不满足，则依次将其右孩子和左孩子入栈
        {
            if(pCur->right)
                s.push(pCur->right);
            if(pCur->left)
                s.push(pCur->left);
        }
    }
    return result;
}

3、利用线索化实现二叉树的遍历（空间复杂度为o(1)）

先序遍历
先序遍历实现步骤：
1）如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2）如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。
3）重复以上1、2直到当前节点为空。
线索化实现二叉树先序遍历的代码实现：
vector<int> pre_Traversal(TreeNode* root)
{
    TreeNode* pCur = root;
    TreeNode* pre;//用于找到当前结点中序遍历的直接前驱
    vector<int> result;//存放遍历结果
    while(pCur)
    {
        if(pCur->left == NULL)//case 1
        {
            result.push_back(pCur->val);
            pCur = pCur->right;
        }
        else
        {
            pre = pCur->left;//找左子树最右结点
            while(pre->right != NULL && pre->right != pCur)
                pre = pre->right;
            if(pre->right == NULL)//case 2a:构成线索二叉树
            {
                pre->right = pCur;
                result.push_back(pCur->val);
                pCur = pCur->left;
            }
            else//case 2b:当前结点左子树遍历完成，断开线索
            {
                pre->right = NULL;
                pCur = pCur->right;
            }

        }
    }
    return result;
}
中序遍历
中序遍历实现步骤（和先序遍历操作步骤几乎一样，唯一差别就在输出结点的时机）：
1）如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2）如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
3）重复以上1、2直到当前节点为空。
线索化实现二叉树中序遍历的代码实现：
vector<int> in_Traversal(TreeNode *root)
{
    TreeNode* pCur = root;
    TreeNode* pre;//用于找到当前结点中序遍历的直接前驱
    vector<int> result;//存放遍历结果
    while(pCur)
    {
        if(pCur->left == NULL)//case 1
        {
            result.push_back(pCur->val);
            pCur = pCur->right;
        }
        else
        {
            pre = pCur->left;//找左子树最右结点
            while(pre->right != NULL && pre->right != pCur)
                pre = pre->right;
            if(pre->right == NULL)//case 2a:构成线索二叉树
            {
                pre->right = pCur;
                pCur = pCur->left;
            }
            else//case 2b:当前结点左子树遍历完成，再遍历当前结点，断开线索
            {
                result.push_back(pCur->val);
                pre->right = NULL;//前序和中序不同之处就在遍历结点的时机
                pCur = pCur->right;
            }

        }
    }
    return result;
}
后序遍历
后序遍历实现步骤：
首先新创建一个临时结点dump，并令其左孩子指向根节点，右孩子指向NULL。
1）如果当前节点的左孩子为空，则将其右孩子作为当前节点。
2）如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
   a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
   b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
3）重复以上1、2直到当前节点为空。
线索化实现二叉树后序遍历的代码实现：
vector<int> post_Traversal(TreeNode* root)
{
    TreeNode* dump = new TreeNode(-1);
    dump->left = root;
    TreeNode* pCur = dump;
    TreeNode* pre = NULL;//保存当前结点中序遍历的直接前驱结点
    vector<int> result;//保存遍历结果

    while(pCur)
    {
        //case 1:当前结点的左孩子为NULL，直接令当前结点
        //的右孩子为当前结点
        if(!pCur->left)
            pCur = pCur->right;
        else
        {
            pre = pCur->left;
            while(pre->right && (pre->right != pCur))
                pre = pre->right;
            if(!pre->right)//case 2a
            {
                pre->right = pCur;
                pCur = pCur->left;
            }
            else//case 2b
            {
                printReverse(pCur->left, pre, result);
                pre->right = NULL;
                pCur = pCur->right;
            }
        }
    }

    dump->left = NULL;//删除辅助结点
    delete(dump);
    dump = NULL;//消除野指针

    return result;
}

void printReverse(TreeNode* from, TreeNode* to, vector<int> &res)
{
    reverse(from, to);

    TreeNode* p = to;
    while(1)
    {
        res.push_back(p->val);
        if(p == from)
            break;
        p = p->right;
    }

    reverse(to, from);
}

void reverse(TreeNode* from, TreeNode* to)
{//将from到to的结点的右孩子指针逆转
    if(from == to)
        return;
    TreeNode* x = from, *y = from->right, *z;
    while(x != to)
    {
        z = y->right;
        y->right = x;
        x = y;
        y = z;
    }
}

——————————————————
参考博客
http://comsci.liu.edu/~murali/algo/Morris.htm
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://blog.csdn.net/ns_code/article/details/12977901
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html


相关推荐