递归方式和迭代方式实现无限极分类

首先来说说什么是无限极分类。按照我的理解，就是对数据完成多次分类，如同一棵树一样，从根开始，到主干、枝干、叶子……

完成无限极分类，主要运用了两种方法，一是递归方式，二是迭代方式。而主要运用无限极分类的地方有地址解析，面包屑导航等等。下面就来具体介绍两种方法的原理及实现方法。

家谱树与子孙树

家谱树是无限极分类的表现形式之一，另一个是子孙树。一开始学习无限极分类时，我时常弄混这两棵树，现在看来自然是明白很多。从汉语的意思也能够看出其中的区别。

家谱，现在很多地方都流行起修家谱，那怎么修家谱，按照我理解，就是给自己找一个祖宗，一代代找上去，形成了一个体系，这样编篡而成的叫家谱。家谱树就与之类似，从某个节点开始向上寻找其父节点，再找父节点的父节点，直到找不到为止。按照这种寻找，形成的一个类似树状的结构，就叫做家谱树。

而子孙树与其相反，子孙树类似于生物书中的遗传图，从某个节点开始寻找它的子节点，再找子节点的子节点，直到寻找完毕。这样形成的树状结构就叫做子孙树。

从上面对家谱树与子孙树的描述，将其转换为代码时，我的第一印象就是利用递归方式，家谱树，找父节点的父节点，子孙树，找子节点的子节点。完全符合递归思想。所以首先我们来说说利用递归方式完成家谱树与子孙树。

递归方式

家谱树的实现

为更清楚的讲解，我先将即将分类的数据贴在下面，是关于地址的数据：

$address = array(
    array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0),
    array('id'=>2  , 'address'=>'江苏' , 'parent_id' => 0),
    array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),
    array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3),
    array('id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4),
    array('id'=>6  , 'address'=>'南京' , 'parent_id' => 2),
    array('id'=>7  , 'address'=>'玄武区' , 'parent_id' => 6),
    array('id'=>8  , 'address'=>'梅园新村街道', 'parent_id' => 7),
    array('id'=>9  , 'address'=>'上海' , 'parent_id' => 0),
    array('id'=>10 , 'address'=>'黄浦区' , 'parent_id' => 9),
    array('id'=>11 , 'address'=>'外滩' , 'parent_id' => 10)
    array('id'=>12 , 'address'=>'安庆' , 'parent_id' => 1)
    );

按照上文的介绍，对上面数据进行家谱树无限极分类，假设我们想要寻找大杨镇的家谱树，先找到与之相关的信息。

'id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4

可以看出它的父节点的id，即parent_id == 4，那么id==4的节点就是其父节点，由此找到庐阳区：

'id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3

与上面类似，寻找id=3的节点，依次向上寻找，找到大杨镇的家谱

大杨镇 -> 庐阳区 -> 合肥 -> 安徽

那么怎么用代码来完成它呢？其实很简单，只需要判断寻找的父id是否与节点的id相等，即parent_id ?= id，相等就是要寻找的父节点，并把该节点的parent_id作为寻找的id，递归进行寻找。如下面的流程图：

递归方法求家谱树

下面就开始编写代码：

/**
 * 获取家谱树
 * @param   array        $data   待分类的数据
 * @param   int/string   $pid    要找的祖先节点
 */
function Ancestry($data , $pid) {
    static $ancestry = array();

    foreach($data as $key => $value) {
        if($value['id'] == $pid) {
            $ancestry[] = $value;

            Ancestry($data , $value['parent_id']);
        }
    }
    return $ancestry;
}

根据流程图，代码编写完成。注意上面存储结点的数组，即$ancestry，要添加静态化关键字static，否则每次递归都会将该数组初始化。当然也可以使用array_merge将每次返回的数组与上一次的进行合并。

寻找家谱的关键就是条件判断，寻找的parent_id等于某个节点的id值，显然该节点就是要寻找的父节点。

代码编写完成，来看看是否符合我们的预期，来寻找大杨镇的家谱：

Ancestry($address , 4);

结果：

Array
(
    [0] => Array
        (
            [id] => 4
            [address] => 庐阳区
            [parent_id] => 3
        )
    [1] => Array
        (
            [id] => 3
            [address] => 合肥
            [parent_id] => 1
        )
    [2] => Array
        (
            [id] => 1
            [address] => 安徽
            [parent_id] => 0
        )
)

可以看出结果与我们预期相符。那么家谱树的递归方法就完成了，下面来讲子孙树的实现。

子孙树的实现

依然使用上面的数据，子孙树是从父节点开始，向下寻找其子孙节点，而形成的一个树状图形。

假设寻找id=0的子孙节点，那么就要注意所有parent_id=0的节点，这些节点都是id=0的子节点。然后，把parent_id=0节点的id作为查询id继续向下查询，直到查不到任何子节点为止。如下：

子孙树

流程图如下：

子孙树流程图

其流程与家谱树类似，不同点，也是关键点就是条件语句的执行。家谱树判断的是当前节点的id是否与上一个节点的parent_id相等；子孙树判断的是当前节点的parent_id与上一个节点的id相等，按照这种条件判断子孙树能够有多个子孙节点，而家谱树只能存在一个祖先。代码如下：

/**
 * 获取子孙树
 * @param   array        $data   待分类的数据
 * @param   int/string   $id     要找的子节点id
 * @param   int          $lev    节点等级
 * 懒人建站http://www.51xuediannao.com/
 */
 function getSubTree($data , $id = 0 , $lev = 0) {
     static $son = array();

     foreach($data as $key => $value) {
         if($value['parent_id'] == $id) {
             $value['lev'] = $lev;
             $son[] = $value;
             getSubTree($data , $value['id'] , $lev+1);
         }
     }

     return $son;
 }

在函数中我添加了一个变量lev，为的是给存入的节点标注等级，方便看出子孙树的结构。下面来测试结果：

getSubTree($data , 0 , 0);

因篇幅有限，将结果进行部分处理：

foreach($tree as $k => $v) {
    echo str_repeat('--' , $v['lev']) . $v['address'] . '<br/>';
}

结果：

安徽
--合肥
----庐阳区
------大杨镇
--安庆
江苏
--南京
----玄武区
------梅园新村街道
上海
--黄浦区
----外滩

递归方式的家谱树与子孙树比较容易理解，只要对递归思想比较了解，一步步写下来不是很难。比起递归方式，迭代方式可能更加让人难以理解。下面就来介绍迭代方式的家谱树与子孙树编写。

迭代方式

家谱树

完成跌代方式的家谱树之前，首先说一下寻找祖先节点的终止条件。虽然叫无限极分类，它不是绝对的无限，只是理论的无限。

如同我国上下五千年历史，任一个大的姓氏，向上找其祖先，不是找到炎帝就是找到黄帝，在往前就没有历史记载了。所以在家谱树的寻找中也有终止条件，就是在分类数据中再也找不到它的父节点时，表现在实例数据上，就是不存在parent_id < 0的节点。

这也是完成迭代的关键，以其作为迭代条件，对数据进行循环判断，并把每次找到的节点的parent_id再次作为迭代条件，直到不满足迭代条件。流程图如下：

家谱树迭代流程

理清流程，现在开始完成代码编写：

function Ancestry($data , $pid) {
    $ancestry = array();

    while($pid > 0) {
        foreach($data as $v) {
            if($v['id'] == $pid) {
                $ancestry[] = $v;

                $pid = $v['parent_id'];
            }
        }
    }

    return $ancestry;
}

迭代条件$pid>0，当pid>0时说明还有祖先存在，可以继续迭代，否则说明没有祖先，迭代终止。$pid = $v['parent_id']是迭代继续进行的关键，每次找到祖先节点，就将祖先节点的父id传递给pid，进行下一次迭代。

运行这个函数，结果与使用递归方式的结果一致。

子孙树的实现

使用迭代方式完成子孙树，更为复杂，需要运用的栈的思想。在进行迭代的过程中，将每次寻找的id入栈，找到一个节点，就将该节点从原数据中删除，当寻找到叶子节点时，即不存在子孙节点时，就将该叶子节点对应的id从栈中弹出，再寻找栈顶id的子孙节点，直到栈清空为止，迭代结束。下面用一个例子来说明：

$address = array(
    array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0),
    array('id'=>2  , 'address'=>'江苏' , 'parent_id' => 0),
    array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),
    array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3),
    array('id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4),
    array('id'=>6  , 'address'=>'南京' , 'parent_id' => 2),
    array('id'=>7  , 'address'=>'玄武区' , 'parent_id' => 6),
    array('id'=>8  , 'address'=>'梅园新村街道', 'parent_id' => 7),
    array('id'=>9  , 'address'=>'上海' , 'parent_id' => 0),
    array('id'=>10 , 'address'=>'黄浦区' , 'parent_id' => 9),
    array('id'=>11 , 'address'=>'外滩' , 'parent_id' => 10)
    array('id'=>12 , 'address'=>'安庆' , 'parent_id' => 1)
    );

寻找id=0的子孙节点，id=0入栈，寻找到该节点，为

array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0)

此时栈为[0]，并且将该节点从原数据中删除，再将id=1入栈，寻找id=1的子孙节点，找到为：

array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),

此时栈[0][1],将该节点删除，id=3入栈，寻找id=3的子孙节点，找到：

array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3)

栈[0][1][3]，将该节点删除，id=4入栈，寻找id=4的子孙节点，找到：

array('id'=>5  , 'address'=>'大杨镇'         , 'parent_id' => 4),

栈[0][1][3][4]，将该节点删除，id=5入栈，栈[0][1][3][4][5]，并寻找id=5的子节点，遍历后未找到，于是将id=5出栈，再次寻找id=4的子孙节点，依次进行。最后完成整个迭代。

期间，栈的情况如下：

[0]
[0][1]
[0][1][3]
[0][1][3][4]
[0][1][3][4][5]
[0][1][3][4]
[0][1][3]
[0][1]
[0][1][12]
[0][1]
[0]
……

代码如下：

function getSubTree($data , $id = 0) {
    $task = array($id);                          # 栈 任务表
    $son = array();
    //懒人建站http://www.51xuediannao.com/
    while(!empty($task)) {
        $flag = false;                           # 是否找到节点标志
        foreach($data as $k => $v) {

            # 判断是否是子孙节点的条件 与 递归方式一致
            if($v['parent_id'] == $id) {
                $son[] = $v;                     # 节点存入数组
                array_push($task , $v['id']);    # 节点id入栈
                $id = $v['id'];                  # 判断条件切换
                unset($data[$k]);                # 删除节点
                $flag = true;                    # 找到节点标志
            }
        }

        # flag == false说明已经到了叶子节点 无子孙节点了
        if($flag == false) {
            array_pop($task);                    # 出栈
            $id = end($task);                    # 寻找栈顶id的子节点
        }
    }
    return $son;
}

这里找到节点后必须把该节点从原数据中删除，否则会造成每次都找到该节点，形成无限迭代的bug。在这里利用数组函数array_push与array_pop模拟进栈与出栈操作。

利用迭代完成子孙树比较复杂，且我没有测试过这个与递归方式谁的效率高，不过利用迭代完成家谱树明显比起递归方法效率高。

无限极分类方法的实际应用

面包屑导航

说完了无限极分类的实现原理与方法，现在来说说在网站中对无限极分类的应用。最常用的就是面包屑导航了。

什么是面包屑导航，这个称呼来自于童话故事"汉赛尔和格莱特"，具体什么故事就不叙述了，有兴趣的可以去谷歌一下。面包屑导航的作用就是告诉访问者他们目前在网站中的位置以及如何返回。下图就是一个典型的面包屑导航。

面包屑导航

面包屑是一个典型家谱树的应用，不要看它是从左到右，分类级数越来越低，就认为它是子孙树应用，要知道子孙树是可能存在多个分支，而面包屑导航要求的是一条主干。

将上面家谱树代码做一定修改，就能够完成面包屑导航。我们采用递归方式的家谱树。代码如下：

function Ancestry($data , $pid) {
    static $ancestry = array();

    foreach($data as $key => $value) {
        if($value['id'] == $pid) {

            Ancestry($data , $value['parent_id']);

            $ancestry[] = $value;                
        }
    }
    return $ancestry;
}

如果先进行递归调用，在递归结束再将找到的节点存入数组中，就能够使祖先节点排列在数组前列，子孙节点排列在数组后列，方便进行提取数据。

简化演示步骤，不从数据库中取出数据，改为模拟数据：

 $tmp = array(
    array('cate_id'=1 , 'name'=>'首页' , 'parent_id'=>'0'),
    array('cate_id'=2 , 'name'=>'新闻中心' , 'parent_id'=>'1'),
    array('cate_id'=3 , 'name'=>'娱乐新闻' , 'parent_id'=>'2'),
    array('cate_id'=4 , 'name'=>'军事要闻' , 'parent_id'=>'2'),
    array('cate_id'=5 , 'name'=>'体育新闻' , 'parent_id'=>'2'),
    array('cate_id'=6 , 'name'=>'博客' , 'parent_id'=>'1'),
    array('cate_id'=7 , 'name'=>'旅游日志' , 'parent_id'=>'6'),
    array('cate_id'=8 , 'name'=>'心情' , 'parent_id'=>'6'),
    array('cate_id'=9 , 'name'=>'小小说' , 'parent_id'=>'6'),
    array('cate_id'=10 , 'name'=>'明星' , 'parent_id'=>'3'),
    array('cate_id'=11 , 'name'=>'网红' , 'parent_id'=>'3')
    );

假设用户点进明星导航，那么在网站显示的导航为：

$tree = Ancestry($tmp , 10);
foreach ($tree as $key => $value) {
    echo $value['name'] . '>';
}

面包屑导航

防止设置父类为子类

在网站建立中，可能会碰到用户进行编辑时出现误操作，将某个栏目的父节点设置成了该栏目的子节点，进行这样的设置后会导致数据库中的数据丢失，因此在进行数据更新之前应该注意这一点。

利用家谱树，就能够避免发生这种错误。在用户提交表单时，我们将即将修改栏目的父节点的家谱树取出，并对家谱树进行遍历，如果发现该家谱树中发现了要修改的节点，就说明是错误操作。有点绕，举个例子来说明：

修改栏目新闻中心的父节点为娱乐新闻，就把娱乐新闻的家谱树取出来：

娱乐新闻 新闻中心 首页

在该家谱树中发现要修改的节点，新闻中心，那么说明出现了错误。具体代码如下：

$data = Ancestry($tmp , 3);
foreach ($data as $key => $value) {
    if($value['cate_id'] == 3) {
        echo  'Error';
        break;
    }
}

原文：http://www.jianshu.com/p/ff07b46666c7