php 求深度

Question

CREATE TABLE `tp_user` (
  `id` bigint(20) UNSIGNED NOT NULL,
  `parent_id` bigint(20) UNSIGNED DEFAULT NULL,
  `name` varchar(100) COLLATE utf8mb4_unicode_ci DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

INSERT INTO `tp_user` (`id`, `parent_id`, `name`) VALUES
(1, null, 'alpha1'),
(2, 1, 'alpha2'),
(3, 1, 'alpha3'),
(4, 1, 'alpha4'),
(5, 2, 'alpha5'),
(6, null, 'alpha6'),
(7, 3, 'alpha7'),
(8, 3, 'alpha8'),
(9, 5, 'alpha9'),
(10, 5, 'alpha10'),
(11, 8, 'alpha11');

ALTER TABLE `tp_user`
ADD PRIMARY KEY (`id`),
ADD UNIQUE KEY `id` (`id`);

假设给定 id 为 1(值也可能是3或8)，求深度？
给我一个数据库特性无关的算法伪代码或思路

Answer 1

其实你要求的是给定节点的高度（节点到叶子的最长距离）。这种问题一般考虑用recursive with，比如Postgresql：

with recursive
  tp_user(id, parent_id) as (
    values(1, null), (2, 1), (3, 1), (4, 1), (5, 2), (6, null),
          (7, 3), (8, 3),(9, 5),(10, 5), (11, 8)),
          
  subtree(depth, id, parent_id) as (
    values(0, 3, null::int)
    union
    select subtree.depth + 1, tp_user.id, tp_user.parent_id
    from tp_user inner join subtree
      on tp_user.parent_id = subtree.id)

select max(depth) height from subtree;

values(0, 3, null::int)这一行中的3是指定的节点，可以替换成其它节点。

Answer 2

我理解的深度是指父节点的层级，而看楼主的意思，你所说的深度是指子节点的层级。
写个get_child()的函数，再写个递归的get_deep()去调用就好了。

Answer 3

想了一下, 有个关键词可能是与题主想要的东西类似 无限级菜单 或 树形菜单

建议搜索下相关内容, 简单的递归应用

Answer 4

无限级分类，tp_user 应该新增一个字段 path 。
path值为 0-1、0-1-2 等等。

然后，sql查询：
select id,name, parent_id,path,concat(path,'-',id) as bpath, from tp_user order by bpath

有问题 私信我~

Answer 5

就是一个无限极分类啊

Answer 6

还以为题主要干嘛呢，去递归啊递归

Answer 7

只是一个很简单的递归算法而已，我这边简单的写是这样的：

get_deep($num){
    //查找parent_id=3的记录
    $sql = "select * from tp_user where parent_id={$num}";
    $ret_array = ...;
    $deep = 0;
    if(count($ret_array)==0){
        return 1;
    }
    foreach($ret_array as $ret){
        $ret_deep = get_deep($ret['id']);
        if($ret_deep>$deep){
            $deep = $ret_deep;
        }
    }
    return ++$deep;
}