递归: Treefy.php
<?php
class Treefy {
const ID = 'id';
const PID = 'pid';
const LEVEL = 'level';
const CHILDREN = 'children';
/** @var $mapKeyItem array assoc */
private $mapKeyItem;
public function __construct($rows) {
$this->mapKeyItem = self::groupBy($rows, self::PID);
}
private static function groupBy($rows, $column) {
$mapKeyItem = array();
foreach ($rows as $row) {
$key = $row[$column];
if (!isset($mapKeyItem[$key])) {
$mapKeyItem[$key] = array();
}
array_push($mapKeyItem[$key], $row);
}
return $mapKeyItem;
}
public static function findItems($mapKeyItem, $pid) {
// find items by pid
if (isset($mapKeyItem[$pid])) {
return $mapKeyItem[$pid];
}
return array();
}
/**
* @param $mapPidItem array assoc
* @param $a array index
* @param $pid int
* @param $level int
*/
private static function tree($mapPidItem, &$a, /* int */$pid, /* int */$level) {
$a = self::findItems($mapPidItem, $pid);
$level += 1;
foreach ($a as &$it) {
$it[self::LEVEL] = $level;
$list = [];
self::tree($mapPidItem, $list, $it[self::ID], $level);
$it[self::CHILDREN] = $list;
}
}
public function getTree($pid = 0, $level = 0) {
$a = [];
self::tree($this->mapKeyItem, $a, $pid, $level);
return $a[0];
}
}测试用例:
// test
$items = [
['id' => 1, 'pid' => 0, 'name' => 'PHP'],
['id' => 2, 'pid' => 1, 'name' => 'PHP_Framework'],
['id' => 42, 'pid' => 1, 'name' => 'DevTools'],
['id' => 3, 'pid' => 2, 'name' => 'ThinkPHP5'],
['id' => 4, 'pid' => 2, 'name' => 'Laravel'],
['id' => 5, 'pid' => 4, 'name' => 'Eloquent ORM'],
['id' => 43, 'pid' => 42, 'name' => 'PHPStorm'],
['id' => 44, 'pid' => 42, 'name' => 'EclipsePDT'],
['id' => 10, 'pid' => 4, 'name'=> 'illuminate']
];
$tree = new Treefy($items);
$t = $tree->getTree();
echo json_encode($t);输出:
{"id":1,"pid":0,"name":"PHP","level":1,"children":[{"id":2,"pid":1,"name":"PHP_Framework","level":2,"children":[{"id":3,"pid":2,"name":"ThinkPHP5","level":3,"children":[]},{"id":4,"pid":2,"name":"Laravel","level":3,"children":[{"id":5,"pid":4,"name":"Eloquent ORM","level":4,"children":[]},{"id":10,"pid":4,"name":"illuminate","level":4,"children":[]}]}]},{"id":42,"pid":1,"name":"DevTools","level":2,"children":[{"id":43,"pid":42,"name":"PHPStorm","level":3,"children":[]},{"id":44,"pid":42,"name":"EclipsePDT","level":3,"children":[]}]}]}迭代
<?php
class Classification {
const PARENT_ID = 'parentid';
const ID = 'id';
const CHILDREN = 'children';
public static function getTree($items) {
$children = [];
// group by parent id
foreach ($items as &$item) {
$children[ $item[self::PARENT_ID] ][] = &$item;
unset($item);
}
foreach ($items as &$item) {
$pid = $item[self::ID];
if (array_key_exists($pid, $children)) {
$item[self::CHILDREN] = $children[ $pid ];
}
unset($item);
}
return $children[0];
}
}
test:
<?php
$items = [
['id' => 1, 'parentid' => 0, 'name' => 'PHP'],
['id' => 2, 'parentid' => 1, 'name' => 'PHP_Framework'],
['id' => 42, 'parentid' => 1, 'name' => 'DevTools'],
['id' => 3, 'parentid' => 2, 'name' => 'ThinkPHP5'],
['id' => 4, 'parentid' => 2, 'name' => 'Laravel'],
['id' => 43, 'parentid' => 42, 'name' => 'PHPStorm'],
['id' => 44, 'parentid' => 42, 'name' => 'EclipsePDT'],
];
shuffle($items);
echo '<pre>';
$a = array_map(function($item) {
return $item['name'];
}, $items);
print_r($a);
$t = Classification::getTree($items);
var_dump($t);
// echo json_encode($t);
Thinkphp Model
<?php
namespace app\model;
use think\Model;
class Link extends Model {
protected $pk = 'id';
protected $field = ['des', 'source', 'target', 'structid'];
/**
* @param $items
* $items = array(
* array('id' => 42, 'parentid' => 1),
* array('id' => 43, 'parentid' => 42),
* array('id' => 1, 'parentid' => 0));
* @return mixed
* Array (
* [0] => Array(
* [id] => 1
* [parentid] => 0
* [childs] => Array(
* [0] => Array (
* [id] => 42
* [parentid] => 1
* [childs] => Array(
* [0] => Array(
* [id] => 43
* [parentid] => 42
* )
* )
* )
* )
* )
* )
*/
public static function buildTree($items) {
$childs = array();
foreach($items as &$item) {
$childs[$item['parentid']][] = &$item;
unset($item);
}
foreach($items as &$item) {
if (isset($childs[$item['id']])) {
$item['childs'] = $childs[$item['id']];
}
unset($item);
}
return $childs[0];
}
/**
* 节点id下一级节点id数组
*/
public function listChildNodeId_r($nodeid) {
$a = $this->listChildNodeId($nodeid);
$list = []; // recursively
foreach ($a as $it) {
array_push($list, $it);
$ca = $this->listChildNodeId($it);
foreach ($ca as $ci) {
array_push($list, $ci);
}
}
return $list;
}
// 节点id下一级节点id数组
private function listChildNodeId($parentid) {
$where = ['source' => $parentid];
$a = $this->field('target')->where($where)->select();
$t = [];
foreach ($a as $item) {
array_push($t, $item['target']);
}
unset($a);
return $t;
}
}
CREATE TABLE `user` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '序号',
`phone` varchar(50) NOT NULL DEFAULT '0' COMMENT '手机号',
`name` varchar(20) NOT NULL DEFAULT '无' COMMENT '姓名',
`idcard` varchar(18) NOT NULL DEFAULT '无' COMMENT '身份证号码',
`auth` int(11) NOT NULL DEFAULT '0' COMMENT '是否认证,0未认证/1已认证',
`password` varchar(32) NOT NULL DEFAULT '0' COMMENT '登录密码',
`password2` varchar(32) NOT NULL DEFAULT '0' COMMENT '交易密码',
`top` int(11) NOT NULL DEFAULT '0' COMMENT '推荐人',
`member` int(11) NOT NULL DEFAULT '0' COMMENT '会员等级',
`money` decimal(10,2) NOT NULL DEFAULT '0.00' COMMENT '余额',
`value` int(11) NOT NULL DEFAULT '0' COMMENT '成长值',
`income` decimal(10,2) NOT NULL DEFAULT '0.00' COMMENT '总收益金额',
`logintime` varchar(20) NOT NULL DEFAULT '0' COMMENT '登录时间',
`clock` int(11) NOT NULL DEFAULT '0' COMMENT '是否锁定,0否/1是',
`qiandao` varchar(20) NOT NULL DEFAULT '0' COMMENT '签到时间',
`time` varchar(20) NOT NULL DEFAULT '0000-00-00 00:00:00' COMMENT '注册时间',
`reg_ip` varchar(20) NOT NULL,
`jifen` varchar(200) DEFAULT NULL,
`dongjiemoney` varchar(100) DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE=MyISAM AUTO_INCREMENT=9 DEFAULT CHARSET=utf8 COMMENT='会员表';
private static function getChildUsers($uid, &$list) {
$children = getData('user', 'all', sprintf("top=%d", $uid), '');
// 没有下级节点 直接返回
if (empty($children)) {
return;
}
// 有下级节点，push进去当前节点, 调用自己
foreach ($children as $child) {
array_push($list, $child);
self::getChildUsers($child['id'], $list);
}
}
