登录 注册

我有一棵树，进行先序遍历，对每个结点进行前后标记，怎么实现比较好

本贴最后更新于 2830 天前，其中的信息可能已经东海扬尘

如题，求大神们思路，能有伪代码更好，没办法，数据结构实在太差

要是能顺便计算出每个节点的层级（深度）就更好了

e7fdc2b0f7154186bb476ed9a25dfa85-UAOMTTXPRPLPL.png

北京 位置
1 收藏
30 回帖
13
9
6
7.2k 31 528 1.8k 2 1.4k 736 2 1.4k 1.4k

相关帖子

30 回帖
我有一棵树，进行先序遍历，对每个结点进行前后标记，怎么实现比较好

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
  • flhuoshan •

    Class Node{
    Node left;
    Node mid;
    Node right;
    Node parent;
    }

    类似这样

    1 回复
  • gaosheng •

    Class Node{
    Node parent;
    List childNodes;
    int lft;
    int right;
    }

    1 回复
  • ZephyrJung •
    支持者

    这里有现成的：先序遍历

    2 回复
  • meikaiyipian •
    作者

    呃。。。这是树节点类的伪代码吧，遍历呢

  • meikaiyipian •
    作者

    。。。这也是树节点类的伪代码吧，还有遍历呢

  • meikaiyipian •
    作者

    这个 github 账号不错，好多算法呀，可以借鉴一下，多谢橙子兄啦

  • meikaiyipian •
    作者

    不一样呀，那个是二叉树，我这个是普通树，遍历的时候，我怎么取到前一个结点呢

    1 回复
  • ZephyrJung •
    支持者

    如果不是二叉树，还有先序遍历的概念么

    1 回复
  • meikaiyipian •
    作者

    怎么没有，也有呀，先序不就是先根遍历吗

    你看我上面的那些数字按顺序连起来不就是先序了

    1 回复
  • ZephyrJung •
    支持者

    上图还是二叉树，树的遍历是要递归的，如果不是二叉树，先根情况下，第二级取哪个根？

    1 回复
  • ZephyrJung •
    支持者

    或者说，中根遍历的时候，哪个放前面？

  • ZephyrJung •
    支持者

    好像是没有中根哈。。。

  • meikaiyipian •
    作者

    二叉树只是有左右子树，上图也是类似的呀，只不过有三个子树了，从左到右子树继续先根遍历进去，不是吗

    中根倒是不好办，可以半中根试试 E B F G C H J A D I

    1 回复
  • ZephyrJung •
    支持者

    干脆用一个 list 来维护子节点，然后把二叉树例子中的先 left 后 right 那段改成一个循环遍历

    1 回复
  • gaosheng •

    按我的数据结构不就是了

    1 回复
  • meikaiyipian •
    作者

    我试过，但要能获取到前一个经过的结点呀，一用 list 遍历的话，若 list 里的结点有子结点，前一个结点就不一样了

    1 回复
  • meikaiyipian •
    作者

    呃。。。数据结构倒是可以，但怎么实现先序遍历进行每个节点如图标记数字呢

    1 回复
  • gaosheng •

    跟二叉树那个算法里一样啊，非递归要用栈

    1 回复
  • meikaiyipian •
    作者

    我用了栈，可以进行先序遍历，就是标记结点，不知道怎么标记节点旁边的数字

    1 回复
  • gaosheng •

    其实递归和非递归核心是一样的，只是「栈」是由谁来维护的

  • gaosheng •

    i++ 啊

    1 回复
  • meikaiyipian •
    作者

    。。。没这么简单吧，我写了，每个节点的左边数字需要上一遍历节点的右边数字，那怎么取到上一节点的右边数字呢

    1 回复
  • gaosheng •

    不用取上一个节点的右数字啊，数字由全局变量来维护，随着遍历递增，跟便利顺序是一样的啊

    1 回复
  • vanlin •

    class Node{Node parent; List childs; int level; int left; int right;} 递归遍历一遍

  • gaosheng • • 1 • 1 赞同

    节点入栈 lft=index++; 出栈 rgt=index++;

  • meikaiyipian •
    作者

    咦。。。这是一个思路，我倒陷入思维误区了，一直想要上一节点

    那么节点深度应怎么求呢

    1 回复
  • gaosheng •

    提示：当前节点深度跟「栈」当前的 size 的关系，你懂的

    1 回复
  • meikaiyipian •
    作者

    有道理，大神你真是天才，让我茅塞顿开呀

    1 回复
  • gaosheng •

    只是我遍历的树比你早而已

  • meikaiyipian •
    作者

    @participants 多谢各位大神

请输入回帖内容 ...
meikaiyipian
几根瘦骨撑天地，一点寒香透古今 北京
回帖
297
 帖子
15
 积分
12592

近期热议

推荐标签 标签

  • Python

    Python 是一种面向对象、直译式电脑编程语言，具有近二十年的发展历史，成熟且稳定。它包含了一组完善而且容易理解的标准库，能够轻松完成很多常见的任务。它的语法简捷和清晰，尽量使用无异义的英语单词，与其它大多数程序设计语言使用大括号不一样，它使用缩进来定义语句块。

    543 引用 • 672 回帖
  • 学习

    “梦想从学习开始，事业从实践起步” —— 习近平

    169 引用 • 506 回帖
  • 新人

    让我们欢迎这对新人。哦，不好意思说错了，让我们欢迎这位新人！
    新手上路，请谨慎驾驶！

    52 引用 • 228 回帖
  • 阿里云

    阿里云是阿里巴巴集团旗下公司，是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务，以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖
  • 脑图

    脑图又叫思维导图，是表达发散性思维的有效图形思维工具 ，它简单却又很有效，是一种实用性的思维工具。

    26 引用 • 84 回帖
  • IBM

    IBM（国际商业机器公司）或万国商业机器公司，简称 IBM（International Business Machines Corporation），总公司在纽约州阿蒙克市。1911 年托马斯·沃森创立于美国，是全球最大的信息技术和业务解决方案公司，拥有全球雇员 30 多万人，业务遍及 160 多个国家和地区。

    17 引用 • 53 回帖 • 135 关注
  • 以太坊

    以太坊（Ethereum）并不是一个机构，而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity，使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物：投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖
  • Solidity

    Solidity 是一种智能合约高级语言，运行在 [以太坊] 虚拟机（EVM）之上。它的语法接近于 JavaScript，是一种面向对象的语言。

    3 引用 • 18 回帖 • 399 关注
  • HTML

    HTML5 是 HTML 下一个的主要修订版本，现在仍处于发展阶段。广义论及 HTML5 时，实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    107 引用 • 295 回帖
  • 深度学习

    深度学习（Deep Learning）是机器学习的分支，是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。

    53 引用 • 40 回帖
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations，简称 DJI)，成立于 2006 年，是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商，客户遍布全球 100 多个国家。通过持续的创新，大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • 国际化

    i18n（其来源是英文单词 internationalization 的首末字符 i 和 n，18 为中间的字符数）是“国际化”的简称。对程序来说，国际化是指在不修改代码的情况下，能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖
  • 微软

    微软是一家美国跨国科技公司，也是世界 PC 软件开发的先导，由比尔·盖茨与保罗·艾伦创办于 1975 年，公司总部设立在华盛顿州的雷德蒙德（Redmond，邻近西雅图）。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • CAP

    CAP 指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可兼得。

    11 引用 • 5 回帖 • 607 关注
  • 运维

    互联网运维工作，以服务为中心，以稳定、安全、高效为三个基本点，确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    149 引用 • 257 回帖
  • V2Ray
    1 引用 • 15 回帖
  • Ubuntu

    Ubuntu（友帮拓、优般图、乌班图）是一个以桌面应用为主的 Linux 操作系统，其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词，意思是“人性”、“我的存在是因为大家的存在”，是非洲传统的一种价值观，类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    125 引用 • 169 回帖 • 1 关注
  • PHP

    PHP（Hypertext Preprocessor）是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点，主要适用于 Web 开发领域，据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 488 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 166 关注
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug（漏洞）。

    75 引用 • 1737 回帖 • 5 关注
  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案，后端采用 Go 编写，采用 MIT 许可证。

    4 引用 • 16 回帖 • 2 关注
  • 钉钉

    钉钉，专为中国企业打造的免费沟通协同多端平台， 阿里巴巴出品。

    15 引用 • 67 回帖 • 338 关注
  • 面试

    面试造航母，上班拧螺丝。多面试，少加班。

    325 引用 • 1395 回帖
  • OnlyOffice
    4 引用 • 2 关注
  • CentOS

    CentOS（Community Enterprise Operating System）是 Linux 发行版之一，它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码，因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • 创造

    你创造的作品可能会帮助到很多人，如果是开源项目的话就更赞了！

    179 引用 • 995 回帖
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 31 关注

最新标签