分层数据Hierarchical Data探索(1.递归)

摘要：分层数据探索例如无限级分类多级菜单省份城市引言什么是分层数据类似于树形结构，除了根节点和叶子节点外，所有节点都有一个父节点和一个或多个子节点。接下来我会先通过一般方法和递归方法来实现无限极分类，然后再通过两种数据模型来谈一谈分层数据的处理。

什么是分层数据？

类似于树形结构，除了根节点和叶子节点外，所有节点都有一个父节点和一个或多个子节点。

大多数同学都曾在数据库中处理过分层数据(hierarchical data)，分层数据存在于许多基于数据库的应用程序中，包括论坛和邮件列表中的分类、商业组织图表、内容管理系统的分类、产品分类、无限级分类、多级菜单、省份城市等等。但是因为关系数据库中的表没有层次关系，只是简单的平面化的列表；而分层数据具有父－子关系，显然关系数据库中的表不能自然地表现出其分层的特性。

接下来我会先通过一般方法和递归(recursion)方法来实现无限极分类，然后再通过两种数据模型来谈一谈分层数据的处理。

分层数据Hierarchical Data探索(1.递归 recursion)

分层数据Hierarchical Data探索(2.邻接表模型 Adjacency List Model)

分层数据Hierarchical Data探索(3.嵌套集合模型 Nested Set Model)

& 引用赋值

function doloop1(&$i = 1)
{
    print_r($i);
    $i++;
    if ($i <= 10) {
        doloop1($i);
    }
}
doloop1();

static 静态变量

function doloop2()
{
    static $i = 1;
    print_r($i);
    $i++;
    if ($i <= 10) {
        doloop2();
    }
}

doloop2();

global 全局变量

$i = 1;
function doloop3()
{
    global $i;
    echo $i;
    $i++;
    if ($i <= 10) {
        doloop3();
    }
}
doloop3();

# 模拟数据
       $data = [
            ["id" => 1, "title" => "Electronics", "parent_id" => 0],
            ["id" => 2, "title" => "Laptops & PC", "parent_id" => 1],
            ["id" => 3, "title" => "Laptops", "parent_id" => 2],
            ["id" => 4, "title" => "PC", "parent_id" => 2],
            ["id" => 5, "title" => "Cameras & photo", "parent_id" => 1],
            ["id" => 6, "title" => "Camera", "parent_id" => 5],
            ["id" => 7, "title" => "Phones & Accessories", "parent_id" => 1],
            ["id" => 8, "title" => "Smartphones", "parent_id" => 7],
            ["id" => 9, "title" => "Android", "parent_id" => 8],
            ["id" => 10, "title" => "iOS", "parent_id" => 8],
            ["id" => 11, "title" => "Other Smartphones", "parent_id" => 8],
            ["id" => 12, "title" => "Batteries", "parent_id" => 7],
            ["id" => 13, "title" => "Headsets", "parent_id" => 7],
            ["id" => 14, "title" => "Screen Protectors", "parent_id" => 7],
        ];

/**
 * 值引用获取无限极分类树
 * 
 * @param array $data
 * @return array
 */
function make_tree($data)
{  
    $refer = array();  
    $tree = array();  
    foreach($data as $k => $v){  
        $refer[$v["id"]] = & $data[$k];  //创建主键的数组引用  
    }  

    foreach($data as $k => $v){  
        $parent_id = $v["parent_id"];   //获取当前分类的父级id  
        if($parent_id == 0){  
            $tree[] = & $data[$k];   //顶级栏目
        }else{  
            if(isset($refer[$parent_id])){  
                $refer[$parent_id]["children"][] = & $data[$k];  //如果存在父级栏目，则添加进父级栏目的子栏目数组中  
            }  
        }  
    }  

    return $tree;  
}

/**
 * 递归获取无限极分类树
 * 
 * @param array $data
 * @param int $parent_id
 * @param int $level
 * @return array
 */
function make_tree2($data = [], $parent_id = 0, $level = 0)
{
    $tree = [];
    if ($data && is_array($data)) {
        foreach ($data as $v) {
            if ($v["parent_id"] == $parent_id) {
                $tree[] = [
                    "id" => $v["id"],
                    "level" => $level,
                    "title" => $v["title"],
                    "parent_id" => $v["parent_id"],
                    "children" => make_tree2($data, $v["id"], $level + 1),
                ];
            }
        }
    }
    return $tree;
}

/**
 * 引用赋值方式
 * @param array $data
 * @param int $id
 * @param int $level
 * @return array
 */
function getSubTree($data = [], $id = 0, $level = 0)
{
    static $tree = [];

    foreach ($data as $key => $value) {
        if ($value["parent_id"] == $id) {
            $value["laravel"] = $level;
            $tree[] = $value;
            getSubTree($data, $value["id"], $level + 1);
        }
    }
    return $tree;
}

/**
 * 静态变量方式
 * @param array $data
 * @param int $id
 * @param int $level
 * @return array
 */
function getSubTree($data = [], $id = 0, $level = 0)
{
    static $tree = [];

    foreach ($data as $key => $value) {
        if ($value["parent_id"] == $id) {
            $value["laravel"] = $level;
            $tree[] = $value;
            getSubTree($data, $value["id"], $level + 1);
        }
    }
    return $tree;
}


/**
 * 全局变量方式
 * @param array $data
 * @param int $id
 * @param int $level
 * @return array
 */

$tree = [];  //先申明变量
function getSubTree($data = [], $id = 0, $level = 0)
{
    global $tree;

    foreach ($data as $key => $value) {
        if ($value["parent_id"] == $id) {
            $value["laravel"] = $level;
            $tree[] = $value;
            getSubTree($data, $value["id"], $level + 1);
        }
    }
    return $tree;
}

/**
 * getParentsByParentId2($categories, 9)
 *
 * @param array $data
 * @param $parent_id
 * @return array
 */
function getParentsByParentId($data = [], $parent_id)
{
    static $categories = [];

    if ($data && is_array($data)) {
        foreach ($data as $item) {
            if ($item["id"] == $parent_id) {
                $categories[] = $item;
                getParentsByParentId($data, $item["parent_id"]);
            }
        }
    }
    return $categories;
}

function getParentsByParentId2($data = [], $parent_id)
{
    $categories = [];

    if ($data && is_array($data)) {
        foreach ($data as $item) {
            if ($item["id"] == $parent_id) {
                $categories[] = $item;
                $categories = array_merge($categories, getParentsByParentId2($data, $item["parent_id"]));
            }
        }
    }
    return $categories;
}