登录 注册

大神们，树的检索问题请教

本贴最后更新于 2811 天前，其中的信息可能已经天翻地覆

我有很多棵这样的树存储在数据库里

CREATE TABLE tree (
id int(11) NOT NULL AUTO_INCREMENT,
name varchar(20) NOT NULL,
lft int(11) NOT NULL,
rgt int(11) NOT NULL,
PRIMARY KEY (id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

1、如何根据根结点查询出整棵树？

2、如何用 SQL 算出某一树结点的深度？

3、如何根据某一结点查询出从根结点到这棵树路径 + 深度？

4、如何查询出结点的所有直接子结点 + 深度？

8ca79fbcb662410688f1708f52af7eff.png

  • 树
    3 引用 • 39 回帖
  • 检索
    1 引用 • 9 回帖
  • 算法
    428 引用 • 254 回帖 • 24 关注
  • SQL
    125 引用 • 378 回帖 • 3 关注
北京 位置
1 关注
1 收藏
9 回帖
5
3
2.7k 15 195 661 521 362 422 510

相关帖子

9 回帖
大神们，树的检索问题请教

欢迎来到这里！

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

注册 关于
请输入回帖内容 ...
  • gaosheng •
    1. select t.* from tree t inner join tree root ON t.lft >= root.lft and t.rgt <= root.rgt order by t.lft asc;
    2. select count(1) from tree t inner join tree child ON t.lft <= child.lft and t.rgt >= child.rgt;
    3. select t.* from tree t inner join tree child ON t.lft <= child.lft and t.rgt >= child.rgt order by t.lft asc; 查询结果就是树路径，结果 size 就是深度
    4. 子节点查询方法跟 1 一样啊，深度建议在表中单加一字段维护
    2 回复
  • meikaiyipian •
    作者

    ON t.lft >= root.lft and t.rgt <= root.rgt 这样会查出不同树之间的结点

    c7bf91b536864eefae149c9c41de4e30.png

  • meikaiyipian •
    作者

    加上 `root.name = 'A'
    也不行

    d65d22cd4cc3422c87d136f1736618f3.png

  • eddy •
    • 按照你的表设计来看应该是二叉树，这就和你的树形结构图不符（根结点有三个树枝节点）
    • 按照你的表设计，虽然可以满足二叉树的存储，但是按照你的查询需求 SQL 会很复杂，建议表扩展一个字段，定义为当前节点的所有父节点，如 E 的父节点字段记为：A:B
      • 根结点查询出这个树是否使用新增字段均可
      • 深度使用新增字段
      • 路径使用新增字段
      • 查询子节点不需使用新增字段，查询深度使用新增节点
    1 回复
  • meikaiyipian •
    作者

    呃。。。不是二叉树，就是普通树

    1 回复
  • eddy •

    我的思路就是，不单单只存储子节点信息，同时存储父节点信息，这样无论是查找路径还是查找深度，或者是构建整棵树（从根结点由上至下构建）都会简单些

    1 回复
  • meikaiyipian •
    作者

    你的意思是再加一个字段存取父结点 `id 是吗

    1 回复
  • eddy •

    嗯，存当前节点所有父节点的 ID，如你文章中的截图，叶子节点 E 存储 父节点信息：A 和 B

    1 回复
  • meikaiyipian •
    作者

    明白了，多谢

请输入回帖内容 ...
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 关注

最新标签