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
转载随意^^请带上本文地址!
评论已关闭