今天一时兴起上百度知道回答了好多问题，赚了不少财富值，虽然并没有什么卵用，可是从别人的问题中也学到了不少东西。例如遇到这样一个非常有意思的算法题目：求php+mysql 的二叉树每一层的叶子统计

提问者还发了几幅图片：

如图，数字为id，想要实现的效果就是假如我输入id为2 ，那么我就要获取每一层的个数，

从ID是2开始，那么他的下层为第一层 个数是2  第二层个数是4 第三层个数2，......最多显示5层

下面是mysql数据库中的记录：

问题很明显，无限极分类，求指定深度的每一层叶子节点的个数。以前有研究过无限极分类，但是没有求过叶子节点这种莫名其妙的问题。看到楼主给的奖励财富值这么高，200财富值啊，于是便认真分析了一下，使用函数顺便模拟了一下mysql的select语法，结果如下：

<?php
header("Content-type:text/html;charset=utf-8");
 
$data = array(
    array('id'=>1, 'pid'=> 0, 'name'=> 'name1'),
    array('id'=>2, 'pid'=> 1, 'name'=> 'name2'),
    array('id'=>3, 'pid'=> 2, 'name'=> 'name3'),
    array('id'=>4, 'pid'=> 3, 'name'=> 'name4'),
    array('id'=>5, 'pid'=> 2, 'name'=> 'name5'),
    array('id'=>6, 'pid'=> 2, 'name'=> 'name6'),
    array('id'=>7, 'pid'=> 2, 'name'=> 'name7'),
    array('id'=>8, 'pid'=> 7, 'name'=> 'name8'),
    array('id'=>9, 'pid'=> 8, 'name'=> 'name9'),
    array('id'=>10, 'pid'=> 9, 'name'=> 'name10'),
    array('id'=>11, 'pid'=> 10, 'name'=> 'name11'),
    array('id'=>12, 'pid'=> 11, 'name'=> 'name12'),
    array('id'=>13, 'pid'=> 12, 'name'=> 'name13'),
    array('id'=>14, 'pid'=> 13, 'name'=> 'name14'),
    array('id'=>15, 'pid'=> 14, 'name'=> 'name15'),
    array('id'=>16, 'pid'=> 1, 'name'=> 'name16'),
    array('id'=>17, 'pid'=> 16, 'name'=> 'name17'),
    array('id'=>18, 'pid'=> 17, 'name'=> 'name18'),
    array('id'=>19, 'pid'=> 18, 'name'=> 'name19'),
    array('id'=>20, 'pid'=> 3, 'name'=> 'name20'),
    array('id'=>21, 'pid'=> 3, 'name'=> 'name21'),
    array('id'=>22, 'pid'=> 2, 'name'=> 'name22'),
);
 
$result = array();
$id = 2;
$lv = 20;
 
get_child_node_nums($id, $lv, $result);
 
foreach($result as $no => $row)
{
    echo '第'.($lv-$no+1).'层有'.count($row).'个叶子节点'.'';
}
 
p($result);
 
//模拟mysql根据pid获取多行记录
function fetch_rows($pid=0)
{
    global $data;
    $pid = (int)$pid;
    $items = array();
    //相当于sql语句:select * from test where pid=$pid
    echo "select * from test where pid=$pid;";
    foreach($data as $row)
    {
        if($row['pid'] == $pid)
        {
            $items[] = $row;
        }
    }
    return $items;
}
 
//$id为父节点id, $lv为深度, $result为引用传值结果数组
function get_child_node_nums($id, $lv, &$result)
{
    //首先根据其id作为子节点的pid获取其所有子节点
    $children = fetch_rows($id);
     
    if($children)
    {
        //存储其叶子节点
        if(isset($result[$lv]))
        {
            $result[$lv] = array_merge($result[$lv], $children);
        }else{
            $result[$lv] = $children;
        }
        $lv--;
        if($lv > 0)
        {
            foreach($children as $child)
            {
                $id = $child['id'];
                get_child_node_nums($id, $lv, $result);
            }
        }
    }
}
 
function p($var)
{
    echo '<pre>';
    if($var === false)
    {
        echo 'false';
    }else if($var === null){
        print_r("null");
    }else if($var === ''){
        print_r("''");
    }else{
        print_r($var);
    }
    echo '</pre>';
}

输出结果如下：

select * from test where pid=2;
select * from test where pid=3;
select * from test where pid=4;
select * from test where pid=20;
select * from test where pid=21;
select * from test where pid=5;
select * from test where pid=6;
select * from test where pid=7;
select * from test where pid=8;
select * from test where pid=9;
select * from test where pid=10;
select * from test where pid=11;
select * from test where pid=12;
select * from test where pid=13;
select * from test where pid=14;
select * from test where pid=15;
select * from test where pid=22;
第1层有5个叶子节点
第2层有4个叶子节点
第3层有1个叶子节点
第4层有1个叶子节点
第5层有1个叶子节点
第6层有1个叶子节点
第7层有1个叶子节点
第8层有1个叶子节点
第9层有1个叶子节点
Array
(
    [20] => Array
        (
            [0] => Array
                (
                    [id] => 3
                    [pid] => 2
                    [name] => name3
                )
 
            [1] => Array
                (
                    [id] => 5
                    [pid] => 2
                    [name] => name5
                )
 
            [2] => Array
                (
                    [id] => 6
                    [pid] => 2
                    [name] => name6
                )
 
            [3] => Array
                (
                    [id] => 7
                    [pid] => 2
                    [name] => name7
                )
 
            [4] => Array
                (
                    [id] => 22
                    [pid] => 2
                    [name] => name22
                )
 
        )
 
    [19] => Array
        (
            [0] => Array
                (
                    [id] => 4
                    [pid] => 3
                    [name] => name4
                )
 
            [1] => Array
                (
                    [id] => 20
                    [pid] => 3
                    [name] => name20
                )
 
            [2] => Array
                (
                    [id] => 21
                    [pid] => 3
                    [name] => name21
                )
 
            [3] => Array
                (
                    [id] => 8
                    [pid] => 7
                    [name] => name8
                )
 
        )
 
    [18] => Array
        (
            [0] => Array
                (
                    [id] => 9
                    [pid] => 8
                    [name] => name9
                )
 
        )
 
    [17] => Array
        (
            [0] => Array
                (
                    [id] => 10
                    [pid] => 9
                    [name] => name10
                )
 
        )
 
    [16] => Array
        (
            [0] => Array
                (
                    [id] => 11
                    [pid] => 10
                    [name] => name11
                )
 
        )
 
    [15] => Array
        (
            [0] => Array
                (
                    [id] => 12
                    [pid] => 11
                    [name] => name12
                )
 
        )
 
    [14] => Array
        (
            [0] => Array
                (
                    [id] => 13
                    [pid] => 12
                    [name] => name13
                )
 
        )
 
    [13] => Array
        (
            [0] => Array
                (
                    [id] => 14
                    [pid] => 13
                    [name] => name14
                )
 
        )
 
    [12] => Array
        (
            [0] => Array
                (
                    [id] => 15
                    [pid] => 14
                    [name] => name15
                )
 
        )
 
)

实现起来并不难，用到了递归和引用传值，但是不知道这样是不是最省内存。还有，打印出的17条sql语句量相当大了，对于数据量小的分类最好不要在递归中查询sql语句，要像本文一样一次性将所有的分类查询出来后再到内存中进行递归。

文章地址:http://blog.zhengshuiguang.com/php/binary-tree.html

转载随意^^请带上本文地址!