php+mysql实现二叉树之叶子节点统计
今天一时兴起上百度知道回答了好多问题，赚了不少财富值，虽然并没有什么卵用，可是从别人的问题中也学到了不少东西。例如遇到这样一个非常有意思的算法题目：求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
转载随意^^请带上本文地址!
评论已关闭