二叉树的前,中,后序的非递归实现(c++)

这篇具有很好参考价值的文章主要介绍了二叉树的前,中,后序的非递归实现(c++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

        对于二叉树来说,遍历它有多种方式,其中递归遍历是比较简单的,但是非递归的实现就有一定的难度,在这里介绍一种非递归实现二叉树遍历的方式。

1.前序遍历

        1.1思路

        其实对于二叉树的非递归实现,实际上就是用代码来模拟操作系统压栈和弹栈的过程。让我们一起来看看吧,首先将一棵树 分为左边节点和左边节点的右子树。如图:二叉树的前,中,后序的非递归实现(c++),c++,数据结构,开发语言

        然后借助于一个栈,先将左边节点入栈,入栈时要将节点的值存到数组中。将左边节点全部入栈后,再来将左边节点的右子树入栈,重复上述过程。直至栈为空并且,当前的指针也为空,此时完成二叉树的前序遍历。如图:二叉树的前,中,后序的非递归实现(c++),c++,数据结构,开发语言 

        1.2代码实现 

        

    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> v;
        stack<TreeNode*> sT;
        //1.处理左边节点
        //2.处理左边节点的右子树
        TreeNode * cur = root;
        while(cur ||  !sT.empty()  )
        {
            while(cur)
            {
                //左边节点入栈
                sT.push(cur);
                v.push_back(cur->val);
                
                cur = cur -> left;
            }
            TreeNode* p = sT.top();
            sT.pop();
            cur = p -> right;
            //左边节点的右子树入栈
        }
        return v;
    }

2.中序遍历

        2.1思路        

        中序遍历的思路和前序遍历基本相同,就是此时左边节点入栈时不会将左边节点的val插到数组中,而是在栈中将节点的指针取出时再尾插到数组中。 

        2.2代码实现 

        

  vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack< TreeNode* > sT;
        TreeNode* cur = root;
        while(cur || !sT.empty())
        {
            //树的左边节点入栈
            while(cur)
            {
                sT.push(cur);
                cur = cur -> left;
            }
            //取出栈顶节点的指针
            //将栈顶节点指针的val尾插到数组中
            TreeNode * top = sT.top();
            sT.pop();
            //左边节点的右子树入栈
            cur = top -> right;
            ret.push_back(top->val);
        }
        return ret;
    }

3.后序遍历 

        3.1思路

        后序遍历沿用了中序遍历的思路,唯一不同的是将左边节点依次入栈后,出栈时先处理当前节点的左子树,然后将右子树入栈,等处理完右子树后再来处理当前节点。

        3.2代码实现 


    vector<int> postorderTraversal(TreeNode* root) 
    {
        TreeNode * cur = root;
        TreeNode * back = nullptr;//用来记录处理上一个节点
        vector<int> ret;
        stack<TreeNode*> sT;
        while(cur || !sT.empty() )
        {
            //左边节点入栈
            while(cur)
            {
                sT.push(cur);
                cur = cur->left;
            }
            //取出栈顶数据
            TreeNode* top = sT.top();
            
            if(top->right == nullptr || top->right == back)
            {
                ret.push_back(top->val);
                back = top;//记录处理过的节点
                sT.pop();
            }
            else
            {
                //左边节点的右子树入栈
                cur = top -> right;
            }
        }
        return ret;
    }

        后续遍历需要注意的是在什么时候来对当前节点进行处理,要先处理左右节点之后对当前节点进行处理,如果右节点为空很好办直接判断右节点为不为空就可以了,但是如果右节点不为空呢?怎么确保右节点已经处理过了再来对当前节点进行处理呢,这里提供一种较为简单的思路,通过一个指针来记录上次处理的节点,因为后序遍历总是按照左子树,右子树和根的处理顺序来的所以我们只需要处理比较上一个处理的节点是不是当前节点的右子树就可以知道 当前节点的右子树是否已经被处理过了,来判断当前节点是否需要处理。

        讲的不好,希望不要喷我。

二叉树的前,中,后序的非递归实现(c++),c++,数据结构,开发语言 

 文章来源地址https://www.toymoban.com/news/detail-623016.html

 

到了这里,关于二叉树的前,中,后序的非递归实现(c++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法练习第13天|递归实现 144.二叉树的前序遍历(opens new window)145.二叉树的后序遍历(opens new window)94.二叉树的中序遍历

    二叉树的存储方式:链式存储和顺序存储。链式存储用指针,顺序存储用数组。其结构如下图所示。 链式存储: 顺序存储: 顺序存储时,若父节点下表为i,则其左孩子下标为 2*i + 1,右孩子下标为2*i + 2. 二叉树主要有两种遍历方式: 深度优先遍历:先往深走,遇到叶子节点

    2024年02月22日
    浏览(51)
  • 【Java数据结构】二叉树的前中后序遍历(递归和非递归)

    二叉树遍历是二叉树的一种重要操作 必须要掌握 二叉树的遍历可以用递归和非递归两种做法来实现 前序遍历的遍历方式是 先根节点 在左节点 在右节点 述这棵树前序遍历的结果是: A B D E C F G 递归的思想就是把问题拆分成一个个小问题来解决 treeNode是一个内部类 具体实现

    2023年04月26日
    浏览(52)
  • 算法刷题Day14 二叉树的前序、中序、后序遍历(递归、迭代、统一迭代方法)

    二叉树的定义 递归 迭代 普通的遍历(包括前序,中序和后续)迭代方法都需要借助到栈 统一迭代 统一迭代使用标记法,在栈中要处理的结点压入空指针 递归 迭代 中序遍历的迭代方法稍微特殊一点 中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问

    2024年02月15日
    浏览(48)
  • LeetCode:二叉树的前、中、后序遍历——如何创建一棵【二叉树】

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 二叉树是一种树形数据结构,其每个节点 最多只有两个子节点 。通常将节点分为三种类型:根节点、内部节点和叶子节点。其中,根节点是二叉树的唯一访问起点,内部节点具有一个父

    2023年04月09日
    浏览(45)
  • 力扣(144. 二叉树的前序遍历&&94.二叉树的中序遍历&&145. 二叉树的后序遍历)

    题目链接 题目1: 思路:较简单的思路,就是先将左孩子全部入栈,然后出栈访问右孩子,右孩子为空,再出栈,不为空,右孩子入栈,然后再次循环访问左孩子。 题目链接 题目2: 思路:同前序遍历一样,只不过访问结点,改为出栈时访问。 题目3链接 题目3: 思路1:同样

    2024年01月19日
    浏览(52)
  • 二叉树先序,中序,后序遍历的非递归算法(一)

    思路: 二叉树的前序遍历过程: 从树根开始沿着左子树一直深入,直到最左端无法深入时,返回; 进入最近深入时遇到结点的右子树,再进行如此的深入和返回; 直到最后从根节点的右子树返回到根节点为止; 由其深入返回的过程我们知道可以用一个栈来帮助我们消除递

    2023年04月14日
    浏览(78)
  • 二叉树的前序/中序/后序遍历新手入门介绍

    前序遍历简介也叫先序遍历 前序遍历 可以分为三部分: 根、左子树、右子树 先遍历根节点 、再遍历左子树、再遍历右子树 左/右 子树遍历方法:先访问根节点,再访问 左孩子节点,访问到左孩子节点之后判断该左孩子节点 是否是 叶子节点 (叶子节点 也就是说 这个节点下

    2024年01月17日
    浏览(49)
  • 算法D14 | 二叉树1 | 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历

    理论基础  需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义  文章讲解: 二叉树既可以链式存储(利用指针,类似栈和队列),也可以用数组表示。 深度优先遍历 前序遍历(递归法,迭代法) 中序遍历(递归法,迭代法) 后序遍历(递归法,迭代法)

    2024年02月20日
    浏览(38)
  • 用java实现二叉树的后序遍历(递归和迭代)

    目录 1.题目内容 2.用递归实现后序遍历 2.1解题思路 2.2代码 3.用迭代实现后序遍历 3.1解题思路 3.2代码 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 输入:root = [1,null,2,3] 输出:[3,2,1] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1]

    2024年02月08日
    浏览(57)
  • 二叉树的非递归遍历算法

    二叉树的遍历是指访问二叉树的每个结点,且每个结点仅被访问一次。二叉树的遍历可按二叉树的构成以及访问结点的顺序分为4种方式:先序遍历、中序遍历、后序遍历和层次遍历。请至少给出其中一种遍历方式的非递归算法的思路和代码,并举例演示算法的执行过程。 算

    2023年04月24日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包