专栏首页爱写Bug树的遍历 Traverse a Tree

树的遍历 Traverse a Tree

前序遍历

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

树的前序遍历FBADCEGIH

中序遍历

中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。

树的中序遍历ABCDEFGHI

通常来说,对于二叉搜索树,我们可以通过中序遍历得到一个递增的有序序列。

后序遍历

后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。

树的后序遍历ACEDBHIGF

值得注意的是,当删除树中的节点时,删除过程将按照后序遍历的顺序进行。也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。

另外,后序遍历思想在数学表达中被广泛使用。因为编写程序来解析后缀表示法更容易:

中序: 4*7-2+5

虽然使用中序遍历可以找出原始表达式, 但程序很难处理这个表达式,因为必须考虑操作符号的优先级。

后序: 4 7 2 - * 5 +

  • 数字栈: 4 7 2 5
  • 符号栈: - * +

如果对这棵树进行后序遍历并使用栈来处理表达式会非常容易。每遇到一个操作符,从栈中弹出栈顶两个元素,计算并将结果返回到栈中。

层序遍历

层序遍历就是逐层遍历树结构。

广度优先搜索是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。该算法从一个根节点开始,首先访问节点本身。然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。

树中进行广度优先搜索,则访问的节点的顺序即层序遍历顺序。

树的层序遍历FBGADICEH


递归的两种思路

递归是树的特性之一。许多树问题可以通过递归的方式来解决。

在树的问题中, 递归可以 “自顶向下” 或 “自底向上”

自顶向下

“自顶向下” 意味着在每个递归层级,我们将首先访问节点来计算一些值,并在递归调用函数时将这些值传递到子节点。所以 “自顶向下” 的解决方案可以被认为是一种前序遍历

例如, 给定一个二叉树,寻找它的最大深度:

private int answer;        // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        answer = Math.max(answer, depth);
    }
    maximum_depth(root.left, depth + 1);
    maximum_depth(root.right, depth + 1);
}

根节点的深度是1。对于每个节点,如果我们知道某节点的深度,那我们将知道它子节点的深度。因此,在调用递归函数的时候,将节点的深度传递为一个参数,那么所有的节点都知道它们自身的深度。

自底向上

“自底向上”在每个递归层次上,我们首先对所有子节点递归地调用函数,然后根据返回值和根节点本身的值得到答案。这个过程可以看作是后序遍历的一种。

例如, 给定一个二叉树,寻找它的最大深度:

public int maximum_depth(TreeNode root) {
    if (root == null) {
        return 0;                                   // return 0 for null node
    }
    int left_depth = maximum_depth(root.left);
    int right_depth = maximum_depth(root.right);
    return Math.max(left_depth, right_depth) + 1;   // return depth of the subtree rooted at root
}

如果我们知道一个根节点,以其子节点为根的最大深度为l和以其子节点为根的最大深度为r,也可以求得二叉树最大深度, 我们可以选择它们之间的最大值,再加上1来获得根节点所在的子树的最大深度。即 x = max(l,r)+ 1

这意味着对于每一个节点来说,我们都可以在解决它子节点的问题之后得到答案。

总结

树的前序, 中序, 后序, 层序遍历是操作 N 叉树的基础, 关于树的算法题基本都是这种思想的扩展, 所以一定要熟练掌握

对于递归的两种解题思路, 如果你不确定是使用自顶向下自底向上, 你可以先思考:

  • 你能确定一些参数,从该节点自身解决出发寻找答案吗?
  • 你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗? 如果答案都是肯定的,那么请尝试使用 “自顶向下” 的递归来解决此问题。

或者:

  • 对于树中的任意一个节点,如果你知道它子节点的答案,你能计算出该节点的答案吗? 如果答案是肯定的,那么请尝试使用 “自底向上” 的递归来解决此问题。

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 752:打开转盘锁 Open the Lock

    你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字:'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每...

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • ADS1256,引起了通信丢失

    最近在项目中用到了TI的ADS1256, SPI接口的24位高精度AD和NXP的K64来采集扭矩传感器正负20mv的电压信号,调试中发现Modbus通讯会丢失,...

    用户1605515
  • [LeetCode] Symmetric Tree

    1、题目名称 Symmetric Tree https://leetcode.com/problems/symmetric-tree/ 2、题目内容 Give...

    程序员小王
  • Neo4j学习(1):Neo4j是什么

      最简单的图是单节点的,一个记录,记录了一些属性。一个节点可以从单属性开始,成长为成千上亿,虽然会有一点点麻烦。从某种意义上讲,将数据用关系连接起来分布到不同...

    海天一树
  • 安装单机版 Skywalking

    •前往 http://skywalking.apache.org/downloads/ ,根据自己的操作系统,下载即可。•对于网络不好的童鞋,可用如下百度盘地址...

    用户1516716
  • Linux上安装rz和sz命令

    人生不如戏
  • 李岩:CynosDB for MySQL高可用系统介绍

    3月16日在北京举行的腾讯云自研数据库CynosDB交流会圆满落下帷幕。现将技术团队分享的内容整理如下。

    云加社区技术沙龙
  • 使用Python爬取社交网络数据分析

    数据抓取 一、直接抓取数据 二、模拟浏览器抓取数据 三、基于API接口抓取数据 数据预处理 可视化 数据分析 扩散深度 扩散速度 空间分布 节点属性 网络属性...

    机器学习AI算法工程

扫码关注云+社区

领取腾讯云代金券