登录 注册

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

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

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

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
    126 引用 • 381 回帖 • 3 关注
北京 位置
1 关注
1 收藏
9 回帖
5
3
2.7k 15 195 668 525 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

近期热议

推荐标签 标签

  • RIP

    愿逝者安息！

    8 引用 • 92 回帖 • 351 关注
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似，也就是用各类命令预先放入到一个文件中，方便一次性执行的一个程序文件，主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大，比用其他编程程序编辑的程序效率更高，因为它使用了 Linux/Unix 下的命令。

    122 引用 • 74 回帖
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现，服务器端用 Erlang 语言编写，支持多种语言客户端，如：Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息，在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 362 关注
  • flomo

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

    5 引用 • 107 回帖
  • 30Seconds

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

    • 精选常见面试题，帮助您准备下一次面试
    • 精选常见交互，帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段，帮助你获取最佳实践
    • 精选常见代码集，帮助您提高打码效率
    • 整理前端界的最新资讯，邀您一同探索新世界
    488 引用 • 384 回帖 • 8 关注
  • gRpc
    11 引用 • 9 回帖 • 73 关注
  • GAE

    Google App Engine（GAE）是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 764 关注
  • Bug

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

    75 引用 • 1737 回帖 • 5 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    340 引用 • 708 回帖
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    6 引用 • 63 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用，支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖
  • danl
    • 132 关注
  • 大疆创新

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

    2 引用 • 14 回帖
  • Python

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

    543 引用 • 672 回帖 • 1 关注
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统，主要使用于便携设备。2005 年由 Google 收购注资，并拉拢多家制造商组成开放手机联盟开发改良，逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 1 关注
  • 微软

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

    8 引用 • 44 回帖 • 1 关注
  • SMTP

    SMTP（Simple Mail Transfer Protocol）即简单邮件传输协议，它是一组用于由源地址到目的地址传送邮件的规则，由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇，它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 614 关注
  • Angular

    Angular 是 AngularJS 的新版本。

    26 引用 • 66 回帖 • 537 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织，“用爱发电”象征开源与贡献精神，加入组织，代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入：用爱发电组织邀请帖。
    用爱发电组织官网：https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力：

    • 遵守开源守则，体现开源&贡献精神：以分享为目的，拒绝非法牟利。
    • 自我保护：使用适当的 License 保护自己的原创作品。
    • 尊重他人：不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露；以礼相待，尊重所有对社区做出贡献的开发者；通过他人的分享习得知识，要留下足迹，表示感谢。
    • 热爱编程、热爱学习：加入组织，热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友，也同样欢迎默默成就的朋友。
    • 倾听：正确并恳切对待、处理问题与建议，及时修复开源项目的 Bug ，及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视：不诋毁、轻视、嘲讽其他开发者，主动提出建议、施以帮助，以和谐为本。只要他人肯努力，你也可能会被昔日小看的人所超越，所以请保持谦虚。
    • 乐观且活跃：你的努力决定了你的高度。不要放弃，多年后回头俯瞰，才会发现自己已经成就往日所仰望的水平。积极地将项目开源，帮助他人学习、改进，自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”，在线用户由 1999 年的 2 人（马化腾和张志东）到现在已经发展到上亿用户了，在线人数超过一亿，是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖 • 67 关注
  • IDEA

    IDEA 全称 IntelliJ IDEA，是一款 Java 语言开发的集成环境，在业界被公认为最好的 Java 开发工具之一。IDEA 是 JetBrains 公司的产品，这家公司总部位于捷克共和国的首都布拉格，开发人员以严谨著称的东欧程序员为主。

    180 引用 • 400 回帖
  • Q&A

    提问之前请先看《提问的智慧》，好的问题比好的答案更有价值。

    8112 引用 • 37001 回帖 • 160 关注
  • VirtualBox

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

    10 引用 • 2 回帖 • 6 关注
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    17 引用 • 236 回帖 • 328 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎，支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 16 关注
  • MySQL

    MySQL 是一个关系型数据库管理系统，由瑞典 MySQL AB 公司开发，目前属于 Oracle 公司。MySQL 是最流行的关系型数据库管理系统之一。

    690 引用 • 535 回帖
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis，2010 年这个项目由 Apache 软件基金会迁移到了 google code，并且改名为 MyBatis ，2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 387 关注

最新标签