精华内容
下载资源
问答
  • 二叉树的后序遍历
    2020-07-05 17:13:08

    一、二叉树的应用场景

    1.前序遍历:可以用来实现目录结构的显示。

    2.中序遍历:一颗二叉搜索树,被中序遍历之后,就是value从小到大的排列,当然也可以用来做表达式树,在编译器底层实现的时候用户可以实现基本的加减乘除,比如 a*b+c。

    3.后序遍历:可以用来实现计算目录内的文件占用的数据大小。

    二、后续遍历的实现

    定义二叉树的结构

     

       // Definition for a binary tree node.
         struct TreeNode {
             int val;
             TreeNode *left;
             TreeNode *right;
             TreeNode(int x) : val(x), left(NULL), right(NULL) {}
         };

    后序遍历:左子树---> 右子树  ---> 根结点

    上图的后序遍历:4  5  2  6  3  1

    一、非递归的方法

    void postorderTraversalNew(TreeNode *root, vector<int> &path)
    {
        stack< pair<TreeNode *, bool> > s;
        s.push(make_pair(root, false));
        bool visited;
        while(!s.empty())
        {
            root = s.top().first;
            visited = s.top().second;
            s.pop();
            if(root == NULL)
                continue;
            if(visited)
            {
                path.push_back(root->val);
            }
            else
            {
                s.push(make_pair(root, true));
                s.push(make_pair(root->right, false));
                s.push(make_pair(root->left, false));
            }
        }
    }
    

    二、递归的方法

    //后续遍历
    void postorder(TreeNode *root, vector<int> &path)
    {
        if(root != NULL)
        {
            postorder(root->left, path);
            postorder(root->right, path);
            path.push_back(root->val);
        }
    }
    

    参考:

    https://blog.csdn.net/czy47/article/details/81254984

    https://blog.csdn.net/zhangxiangDavaid/article/details/37115355?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-6.edu_weight&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-6.edu_weight

     

     

    更多相关内容
  • 数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
  • 有一个整数型列表,判断该列表是否为对应二叉搜索树的后序遍历结果 ''' 二叉搜索树 二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i...
  • 主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 从中序与后序遍历序列构造二叉树 1 题目地址 https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你...
  • 较难较易混淆的二叉树部分经典例题,不会的童鞋~~
  • 目录 一、题目 二、后序遍历讲解 三、递归实现后序遍历 1、递归思路 ...四、迭代实现后序遍历 ...五、欢迎访问我的java二叉树专栏 ...给你一棵二叉树的根...(1)后序遍历下图二叉树,结果:5--2--6--3--1 (2......

    目录

     

     一、题目

    二、后序遍历讲解

    三、递归实现后序遍历

     1、递归思路

    2、代码实现

     四、迭代实现后序遍历

    1、迭代思路

    2、代码实现

    五、欢迎访问我的java二叉树专栏


     

    一、题目

    1、链接:力扣

    2、内容:

    给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

     

    示例 1:

    914ae8d37a1620a8c578d26eb72fd0aa.png

    输入:root = [1,null,2,3]
    输出:[3,2,1]
    

    二、后序遍历讲解

    (1)后序遍历下图二叉树,结果: 5--2--6--3--1

    7af027d47fed46ad9668048dac38099b.png

     (2)后序遍历顺序:左右中

    三、递归实现后序遍历

     1、递归思路

     (1)确定递归放回值以及参数:根据题目需要返回遍历的节点,所以需要List集合存储节点的值,同时需要将二叉树头节点传入;

    postOrder(TreeeNode root,List<Integer> result)

    (2)确定递归终止条件:遍历二叉树节点为空,表明已经无节点,直接return

    if(root==null)
        return;

    (3)确定递归逻辑:递归顺序为左,右,中,递归开始时,先将根节点添加List集合,然后遍历左子树,最后遍历右子树。

            postOrder(treeNode.left,result);//左
            postOrder(treeNode.right,result);//右
            result.add(treeNode.val);//中

    2、代码实现

        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result=new ArrayList<>();
            postOrder(root,result);
            return result;
        }
    
        //后序遍历
        public static void postOrder(TreeNode treeNode,List<Integer> result){
            if (treeNode==null){
                return;
            }
            postOrder(treeNode.left,result);//左
            postOrder(treeNode.right,result);//右
            result.add(treeNode.val);//中
        }
    

     四、迭代实现后序遍历

    1、迭代思路

    (1)借助栈实现迭代遍历,先序遍历为中左右,改变顺序为:中右左,然后反转结果,即为后序遍历:左右中;

    (2)判断二叉树是否为空,不为空,头节点入栈

    f851e7ae32eb41c8a2f11733ee684eb3.png

    (3)栈不为空,栈顶元素弹出,并将元素添加到list集合,判断左子树是否为空,不为空入栈,判读右子树是否为空,不为空入栈

    15ce6521dc964e599fd5054e514aa5c9.png

     

     (4)重复以上操作

    a644f805cc2e4b9c9cbe426c156c476d.png

     

     

    40156aeda72c45219b2bc60163b0a642.png 

    c0601a79e87a448f8a5e981f74043649.png 

     

    d0ca7e8b819749eca59eb39ec46860a5.png 

    最后到这里,不要忘记将集合反转 

     

    2、代码实现

     

    class Solution {
        public List<Integer> postorderTraversal(TreeNode treeNode) {
            List<Integer> result=new ArrayList<>();
            Stack<TreeNode> stack=new Stack<>();
            if(treeNode==null)
                return result;
            stack.push(treeNode);
            while (!stack.isEmpty()){
                TreeNode root=stack.pop();
                result.add(root.val);
                if (root.left!=null){
                    stack.push(root.left);
                }
                if (root.right!=null){
                    stack.push(root.right);
                }
            }
    
            Collections.reverse(result);
            for (Integer integer : result) {
                System.out.println(integer);
            }
            return result;
        }
    }

    五、欢迎访问我的java二叉树专栏

    https://blog.csdn.net/weixin_50616848/category_11818403.html

     

    展开全文
  • C语言实现数据结构中根据中序、后序遍历构建树,并进行先序与层次遍历,以树形结构输出,附有详细中文注释
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • Java 二叉树后序遍历(递归/非递归)

    Java 二叉树后序遍历(递归/非递归)

    简介: 遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。

    设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有几种情况:DLR(称为先序遍历),LDR(称为中序遍历),LRD (称为后序遍历),层次遍历。

    后序遍历

    后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点。

    如图所示二叉树的后序遍历结果为:[8,9,4,15,7,20,3]

    在这里插入图片描述

    代码实现

    递归方式

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
    
    

    非递归方式

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
    
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
    
    

    完整代码:

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(8);
        TreeNode n4 = new TreeNode(15);
        TreeNode n5 = new TreeNode(7);
        TreeNode n6 = new TreeNode(4);
        root.left = n1;
        root.right = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n4.left = n6;
    
        List<Integer> rs = postorderTraversal(root);
        System.out.println("递归中序遍历结果:" + rs);
    
        rs = postorderTraversal02(root);
        System.out.println("非递归中序遍历结果:" + rs);
    }
    
    // 递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
    
    // 非递归
    public List<Integer> postorderTraversal02(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
    
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
    
    

    运行结果:

    展开全文
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • /* 二叉树后序遍历递归算法 */ /* 初始条件: 二叉树T存在 */ /* 操作结果: 后序递归遍历T */ void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /* 先后序遍历左子树 ...

    我的首发平台是公众号【CodeAllen】,学习交流QQ群:736386324

    后序遍历的代码

    /* 二叉树的后序遍历递归算法 */
    /* 初始条件: 二叉树T存在 */
    /* 操作结果: 后序递归遍历T */
    void PostOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return;
        PostOrderTraverse(T->lchild);   /* 先后序遍历左子树  */
        PostOrderTraverse(T->rchild);   /* 再后序遍历右子树  */
        printf("%c",T->data);           /* 显示结点数据,可以更改为其它对结点操作 */
    }
    

    二叉树后序遍历的实现思想是:从根节点出发,依次遍历各节点的左右子树,直到当前节点左右子树遍历完成后,才访问该节点元素。
    在这里插入图片描述
    如上图中,对此二叉树进行后序遍历的操作过程为:

    • 从根节点 1 开始,遍历该节点的左子树(以节点 2 为根节点);
    • 遍历节点 2 的左子树(以节点 4 为根节点);
    • 由于节点 4 既没有左子树,也没有右子树,此时访问该节点中的元素 4,并回退到节点 2 ,遍历节点 2 的右子树(以 5 为根节点);
    • 由于节点 5 无左右子树,因此可以访问节点 5 ,并且此时节点 2 的左右子树也遍历完成,因此也可以访问节点 2;
    • 此时回退到节点 1 ,开始遍历节点 1 的右子树(以节点 3 为根节点);
    • 遍历节点 3 的左子树(以节点 6 为根节点);
    • 由于节点 6 无左右子树,因此访问节点 6,并回退到节点 3,开始遍历节点 3 的右子树(以节点 7 为根节点);
    • 由于节点 7 无左右子树,因此访问节点 7,并且节点 3 的左右子树也遍历完成,可以访问节点 3;节点 1 的左右子树也遍历完成,可以访问节点 1;
    • 到此,整棵树的遍历结束。

    由此,对上图中二叉树进行后序遍历的结果为:
    4 5 2 6 7 3 1

    展开全文
  • 2.后序遍历 3.中序遍历 4.层序遍历 口诀: 后序:左右根 后序遍历:若树为空,则空操作返回,否则从左到右先叶子后结点的方式访问遍历左右子树,最后访问根节点。 后序遍历结果:H I D J E B K F G C A 后序遍历:8...
  • 前序、中序、后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中。方法有很多,这里只举一种,先定义栈结点的数据结构 代码如下:typedef struct{...
  • 数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
  • 4二叉树后序遍历.swf
  • C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序、中序、后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中。 方法有很多,这里只举一...
  • 二叉树后序遍历(递归+非递归)Java

    千次阅读 2019-10-25 08:39:43
    后序遍历(递归)代码图解功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个...
  • 二叉树的后续遍历,是先遍历左子树,在遍历右子数,最后遍历根节点。 后续遍历的过程中我们需要借助栈来辅助 #include<iostream> #include<stack> //先构建一个二叉树结构体 struct BTreeNode{ int ...
  • 二叉树后序遍历_C++课程设计_源代码_亲测可用.zip
  • js代码-二叉树后序遍历
  • 二叉树后序遍历详细过程.xlsx
  • 二叉树后序遍历(非递归)

    万次阅读 2018-08-14 10:03:48
    二叉树的递归遍历算法就不用说了;在非递归算法中,后序遍历难度大,很多书上只给出思想或者几段无法直接调试的代码,甚至有些书上是错的,当时我在研究的过程中,就是按着书上错误的代码绕了好半天,几预抓狂
  • - PAGE PAGE 2 欢迎下载 数据结构实验报告 实验题目: 创建并遍历二叉树 实验目的熟悉二叉树存储结构熟悉二叉树的三种遍历方法并能用非递归的方法建立并且遍历二叉树 实验内容用先序和中序建立二叉树后序遍历并输出...
  • 二叉树后序遍历的非递归算法。.doc
  • 首先我们从两个方面讲解二叉树后序遍历(递归+迭代) 一.二叉树后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,...
  • 主要介绍了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作,涉及Python基于先序遍历和中序遍历构造二叉树,再后序遍历输出相关操作技巧,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,550
精华内容 40,220
关键字:

二叉树的后序遍历