登录 注册

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

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

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

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

e7fdc2b0f7154186bb476ed9a25dfa85-UAOMTTXPRPLPL.png

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

相关帖子

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

欢迎来到这里！

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

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

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

    类似这样

    1 回复
  • gaosheng • via macOS

    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 • via macOS

    按我的数据结构不就是了

    1 回复
  • meikaiyipian •
    作者

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

    1 回复
  • meikaiyipian •
    作者

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

    1 回复
  • gaosheng • via macOS

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

    1 回复
  • meikaiyipian •
    作者

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

    1 回复
  • gaosheng • via macOS

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

  • gaosheng • via macOS

    i++ 啊

    1 回复
  • meikaiyipian •
    作者

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

    1 回复
  • gaosheng • via macOS

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

    1 回复
  • vanlin •

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

  • gaosheng • • 1 • 1 赞同 via macOS

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

  • meikaiyipian •
    作者

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

    那么节点深度应怎么求呢

    1 回复
  • gaosheng • via macOS

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

    1 回复
  • meikaiyipian •
    作者

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

    1 回复
  • gaosheng • via macOS

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

  • meikaiyipian •
    作者

    @participants 多谢各位大神

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

近期热议

推荐标签 标签

  • 锤子科技

    锤子科技（Smartisan）成立于 2012 年 5 月，是一家制造移动互联网终端设备的公司，公司的使命是用完美主义的工匠精神，打造用户体验一流的数码消费类产品（智能手机为主），改善人们的生活质量。

    4 引用 • 31 回帖 • 5 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘（Capacitive Keyboard）。

    5 引用 • 74 回帖 • 503 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息，资讯有时效性和地域性。

    56 引用 • 85 回帖
  • WebComponents

    Web Components 是 W3C 定义的标准，它给了前端开发者扩展浏览器标签的能力，可以方便地定制可复用组件，更好的进行模块化开发，解放了前端开发者的生产力。

    1 引用 • 9 关注
  • RIP

    愿逝者安息！

    8 引用 • 92 回帖 • 399 关注
  • 周末

    星期六到星期天晚，实行五天工作制后，指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖 • 1 关注
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    411 引用 • 3588 回帖
  • Solidity

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

    3 引用 • 18 回帖 • 437 关注
  • 以太坊

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

    34 引用 • 367 回帖 • 4 关注
  • Swift

    Swift 是苹果于 2014 年 WWDC（苹果开发者大会）发布的开发语言，可与 Objective-C 共同运行于 Mac OS 和 iOS 平台，用于搭建基于苹果平台的应用程序。

    36 引用 • 37 回帖 • 546 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具，支持本地 Markdown 文件编辑，支持双向链接和关系图。

    A second brain, for you, forever.

    24 引用 • 241 回帖
  • Flume

    Flume 是一套分布式的、可靠的，可用于有效地收集、聚合和搬运大量日志数据的服务架构。

    9 引用 • 6 回帖 • 653 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用，而且功能强大。你无需专门学习，只需看上几眼，就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 633 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统，最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统，最初是设计给 iPhone 使用的，后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样，属于类 Unix 的商业操作系统。

    89 引用 • 150 回帖 • 1 关注
  • Oracle

    Oracle（甲骨文）公司，全称甲骨文股份有限公司（甲骨文软件系统有限公司），是全球最大的企业级软件公司，总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年，甲骨文已超越 IBM，成为继 Microsoft 后全球第二大软件公司。

    107 引用 • 127 回帖 • 339 关注
  • 996

    “工作 996， 生病 ICU”

    13 引用 • 200 回帖 • 5 关注
  • Git

    Git 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。

    211 引用 • 358 回帖 • 2 关注
  • Gitea

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

    5 引用 • 16 回帖 • 2 关注
  • 面试

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

    325 引用 • 1395 回帖
  • PWA

    PWA（Progressive Web App）是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术，在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 178 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ，专注在碎片化时代，促进你的记录，帮你积累更多知识资产。

    6 引用 • 141 回帖
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件，让构建、部署、自动化集成项目变得简单易用。

    54 引用 • 37 回帖 • 1 关注
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣，为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 57 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件，打造你得心应手的工具集合。

    7 引用 • 27 回帖
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储，专门用于在分布式系统中保存关键数据。

    6 引用 • 26 回帖 • 544 关注
  • 心情

    心是产生任何想法的源泉，心本体会陷入到对自己本体不能理解的状态中，因为心能产生任何想法，不能分出对错，不能分出自己。

    59 引用 • 369 回帖
  • 阿里云

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

    84 引用 • 324 回帖 • 1 关注

最新标签