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

本贴最后更新于 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 关注

相关帖子

欢迎来到这里!

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

注册 关于
请输入回帖内容 ...
  • 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
几根瘦骨撑天地,一点寒香透古今 北京

推荐标签 标签

  • 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 回帖