登录 注册

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

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

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

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
    127 引用 • 386 回帖 • 3 关注
北京 位置
1 关注
1 收藏
9 回帖
5
3
2.8k 15 195 702 531 362 423 555

相关帖子

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

欢迎来到这里！

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

注册 关于
请输入回帖内容 ...
  • gaosheng • via macOS
    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

近期热议

推荐标签 标签

  • AngularJS

    AngularJS 诞生于 2009 年，由 Misko Hevery 等人创建，后为 Google 所收购。是一款优秀的前端 JS 框架，已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性，最为核心的是：MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 499 关注
  • WebClipper

    Web Clipper 是一款浏览器剪藏扩展，它可以帮助你把网页内容剪藏到本地。

    3 引用 • 9 回帖 • 5 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商，致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景，七牛先后推出了对象存储，融合 CDN 加速，数据通用处理，内容反垃圾服务，以及直播云服务等。

    28 引用 • 226 回帖 • 137 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活，连接点滴

    169 引用 • 3834 回帖 • 1 关注
  • IDEA

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

    181 引用 • 400 回帖
  • Access
    1 引用 • 3 回帖 • 5 关注
  • 机器学习

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

    83 引用 • 37 回帖 • 1 关注
  • SMTP

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

    4 引用 • 18 回帖 • 637 关注
  • Chrome

    Chrome 又称 Google 浏览器，是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写，包括 WebKit，目标是提升稳定性、速度和安全性，并创造出简单且有效率的使用者界面。

    62 引用 • 289 回帖
  • uTools

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

    7 引用 • 27 回帖
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架，使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用，例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 32 关注
  • 生活

    生活是指人类生存过程中的各项活动的总和，范畴较广，一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。

    230 引用 • 1454 回帖 • 1 关注
  • Spring

    Spring 是一个开源框架，是于 2003 年兴起的一个轻量级的 Java 开发框架，由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构，分层架构允许使用者选择使用哪一个组件，同时为 JavaEE 应用程序开发提供集成的框架。

    945 引用 • 1460 回帖 • 1 关注
  • sts
    2 引用 • 2 回帖 • 222 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用（如 Word、Excel 和 PowerPoint）与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起，可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言，内置支持类型。它的解释器被称为 JavaScript 引擎，为浏览器的一部分，广泛用于客户端的脚本语言，最早是在 HTML 网页上使用，用来给 HTML 网页增加动态功能。

    729 引用 • 1278 回帖
  • SSL

    SSL（Secure Sockets Layer 安全套接层），及其继任者传输层安全（Transport Layer Security，TLS）是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 414 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本，加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较（vimdiff）、语法高亮、全面的帮助系统、本地脚本（Vimscript）和便于选择的可视化模式。

    29 引用 • 66 回帖 • 1 关注
  • Log4j

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

    20 引用 • 18 回帖 • 34 关注
  • 笔记

    好记性不如烂笔头。

    311 引用 • 796 回帖
  • 宕机

    宕机，多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态，也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态，也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 74 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端，也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • 开源

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

    409 引用 • 3586 回帖 • 1 关注
  • OpenShift

    红帽提供的 PaaS 云，支持多种编程语言，为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 649 关注
  • 面试

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

    325 引用 • 1395 回帖
  • OneNote
    1 引用 • 3 回帖
  • 安全

    安全永远都不是一个小问题。

    203 引用 • 818 回帖

最新标签