登录 注册

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

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

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

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

e7fdc2b0f7154186bb476ed9a25dfa85-UAOMTTXPRPLPL.png

北京 位置
1 收藏
30 回帖
13
9
6
7.2k 31 528 1.7k 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

近期热议

推荐标签 标签

  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架，它对 JDBC 进行了非常轻量级的对象封装，使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 705 关注
  • 新人

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

    52 引用 • 228 回帖
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计，是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 723 关注
  • 阿里云

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

    89 引用 • 345 回帖
  • 支付宝

    支付宝是全球领先的独立第三方支付平台，致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验，及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • 安装

    你若安好，便是晴天。

    132 引用 • 1184 回帖
  • TensorFlow

    TensorFlow 是一个采用数据流图（data flow graphs），用于数值计算的开源软件库。节点（Nodes）在图中表示数学操作，图中的线（edges）则表示在节点间相互联系的多维数据数组，即张量（tensor）。

    20 引用 • 19 回帖
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎，它支持自动化部署、大规模可伸缩、应用容器化管理。

    110 引用 • 54 回帖 • 3 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 31 关注
  • 深度学习

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

    52 引用 • 40 回帖
  • 服务器

    服务器，也称伺服器，是提供计算服务的设备。由于服务器需要响应服务请求，并进行处理，因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖 • 1 关注
  • Electron

    Electron 基于 Chromium 和 Node.js，让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目，兼容 Mac、Windows 和 Linux，它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖 • 1 关注
  • CSS

    CSS（Cascading Style Sheet）“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。

    197 引用 • 547 回帖 • 1 关注
  • CodeMirror
    1 引用 • 2 回帖 • 126 关注
  • 30Seconds

    📙 前端知识精选集，包含 HTML、CSS、JavaScript、React、Node、安全等方面，每天仅需 30 秒。

    • 精选常见面试题，帮助您准备下一次面试
    • 精选常见交互，帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段，帮助你获取最佳实践
    • 精选常见代码集，帮助您提高打码效率
    • 整理前端界的最新资讯，邀您一同探索新世界
    488 引用 • 383 回帖 • 6 关注
  • 倾城之链
    23 引用 • 66 回帖 • 138 关注
  • 游戏

    沉迷游戏伤身，强撸灰飞烟灭。

    176 引用 • 815 回帖
  • 设计模式

    设计模式（Design pattern）代表了最佳的实践，通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    200 引用 • 120 回帖 • 1 关注
  • 机器学习

    机器学习（Machine Learning）是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。

    83 引用 • 37 回帖 • 1 关注
  • 书籍

    宋真宗赵恒曾经说过：“书中自有黄金屋，书中自有颜如玉。”

    77 引用 • 390 回帖
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系，基于确定和自然的设计价值观上的模块化解决方案，让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架，基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 388 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件，最早由德国 Innotek 公司开发，由 Sun Microsystems 公司出品的软件，使用 Qt 编写，在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 12 关注
  • 前端

    前端技术一般分为前端设计和前端开发，前端设计可以理解为网站的视觉设计，前端开发则是网站的前台代码实现，包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1347 回帖
  • C

    C 语言是一门通用计算机编程语言，应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发，并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例： https://wide.b3log.org

    30 引用 • 218 回帖 • 625 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议，它实现了浏览器与服务器之间的全双工通信（full-duplex）。

    48 引用 • 206 回帖 • 346 关注

最新标签