登录 注册

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

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

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

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.7k 15 195 685 528 362 422 513

相关帖子

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

近期热议

推荐标签 标签

  • 周末

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

    14 引用 • 297 回帖
  • 新人

    让我们欢迎这对新人。哦，不好意思说错了，让我们欢迎这位新人！
    新手上路，请谨慎驾驶！

    52 引用 • 228 回帖
  • Telegram

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

    5 引用 • 35 回帖
  • 国际化

    i18n（其来源是英文单词 internationalization 的首末字符 i 和 n，18 为中间的字符数）是“国际化”的简称。对程序来说，国际化是指在不修改代码的情况下，能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖 • 1 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统，它问世于 1985 年，起初仅仅是 Microsoft-DOS 模拟环境，后续的系统版本由于微软不断的更新升级，不但易用，也慢慢的成为家家户户人们最喜爱的操作系统。

    223 引用 • 474 回帖
  • Spring

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

    943 引用 • 1460 回帖 • 3 关注
  • 职场

    找到自己的位置，萌新烦恼少。

    127 引用 • 1706 回帖
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架，使用 Node.js 编写。

    21 引用 • 140 回帖 • 3 关注
  • SSL

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

    70 引用 • 193 回帖 • 418 关注
  • VirtualBox

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

    10 引用 • 2 回帖
  • Android

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

    334 引用 • 323 回帖 • 3 关注
  • 禅道

    禅道是一款国产的开源项目管理软件，她的核心管理思想基于敏捷方法 scrum，内置了产品管理和项目管理，同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能，在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来，完整地覆盖了项目管理的核心流程。

    5 引用 • 15 回帖 • 102 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 26 关注
  • JSON

    JSON （JavaScript Object Notation）是一种轻量级的数据交换格式。易于人类阅读和编写。同时也易于机器解析和生成。

    52 引用 • 190 回帖 • 1 关注
  • Dubbo

    Dubbo 是一个分布式服务框架，致力于提供高性能和透明化的 RPC 远程服务调用方案，是 [阿里巴巴] SOA 服务化治理方案的核心框架，每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持，并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 604 关注
  • abitmean

    有点意思就行了

    • 27 关注
  • 服务器

    服务器，也称伺服器，是提供计算服务的设备。由于服务器需要响应服务请求，并进行处理，因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 588 回帖
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 745 关注
  • Vue.js

    Vue.js（读音 /vju ː/，类似于 view）是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    265 引用 • 666 回帖 • 1 关注
  • 持续集成

    持续集成（Continuous Integration）是一种软件开发实践，即团队开发成员经常集成他们的工作，通过每个成员每天至少集成一次，也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建（包括编译，发布，自动化测试）来验证，从而尽早地发现集成错误。

    15 引用 • 7 回帖
  • API

    应用程序编程接口（Application Programming Interface）是一些预先定义的函数，目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力，而又无需访问源码，或理解内部工作机制的细节。

    77 引用 • 430 回帖 • 1 关注
  • Swift

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

    36 引用 • 37 回帖 • 535 关注
  • CodeMirror
    1 引用 • 2 回帖 • 129 关注
  • Docker

    Docker 是一个开源的应用容器引擎，让开发者可以打包他们的应用以及依赖包到一个可移植的容器中，然后发布到任何流行的操作系统上。容器完全使用沙箱机制，几乎没有性能开销，可以很容易地在机器和数据中心中运行。

    492 引用 • 926 回帖
  • etcd

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

    5 引用 • 26 回帖 • 528 关注
  • IDEA

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

    181 引用 • 400 回帖
  • B3log

    B3log 是一个开源组织，名字来源于“Bulletin Board Blog”缩写，目标是将独立博客与论坛结合，形成一种新的网络社区体验，详细请看 B3log 构思。目前 B3log 已经开源了多款产品：Sym、Solo、Vditor 和 思源笔记。

    1063 引用 • 3454 回帖 • 189 关注

最新标签