CREATE TABLE `menus` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `title` varchar(255) NOT NULL COMMENT ' ',
  `pid` int(11) NOT NULL COMMENT ' id   0',
  `level` int(3) NOT NULL COMMENT ' ',
  `flag` int(4) NOT NULL COMMENT '  2: ( ） 1: ( ） ',
  `created_at` timestamp NULL DEFAULT '2000-01-01 00:00:00',
  `updated_at` timestamp NULL DEFAULT '2000-01-01 00:00:00',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=20 DEFAULT CHARSET=utf8;

class PHPTree{
    protected static $config = array(
        /*   */
        'primary_key'     => 'id',
        /*   */
        'parent_key'      => 'parent_id',
        /*   */
        'expanded_key'  => 'expanded',
        /*   */
        'leaf_key'      => 'leaf',
        /*   */
        'children_key'  => 'children',
        /*   */
        'expanded'        => false
    );

    /*   */
    protected static $result = array();

    /*   */
    protected static $level = array();
    /**
     * @name  
     * @param array  
     * @return mixed  
     */
    public static function makeTree($data,$options=array() ){
        $dataset = self::buildData($data,$options);
        $r = self::makeTreeCore(0,$dataset,'normal');
        return $r;
    }

    /*  ,  HTML ,   */
    public static function makeTreeForHtml($data,$options=array()){

        $dataset = self::buildData($data,$options);
        $r = self::makeTreeCore(0,$dataset,'linear');
        return $r;
    }

    /*  ,   */
    private static function buildData($data,$options){
        $config = array_merge(self::$config,$options);
        self::$config = $config;
        extract($config);

        $r = array();
        foreach($data as $item){
            $id = $item[$primary_key];
            $parent_id = $item[$parent_key];
            $r[$parent_id][$id] = $item;
        }

        return $r;
    }

    /*  ,    */
    private static function makeTreeCore($index,$data,$type='linear')
    {
        extract(self::$config);
        foreach($data[$index] as $id=>$item)
        {
            if($type=='normal'){
                if(isset($data[$id]))
                {
                    $item[$expanded_key]= self::$config['expanded'];
                    $item[$children_key]= self::makeTreeCore($id,$data,$type);
                }
                else
                {
                    $item[$leaf_key]= true;
                }
                $r[] = $item;
            }else if($type=='linear'){
                $parent_id = $item[$parent_key];
                self::$level[$id] = $index==0?0:self::$level[$parent_id]+1;
                $item['level'] = self::$level[$id];
                self::$result[] = $item;
                if(isset($data[$id])){
                    self::makeTreeCore($id,$data,$type);
                }

                $r = self::$result;
            }
        }
        return $r;
    }
}

$data = array(
    array(
        'id' => 1,
        'name' => ' ',
        'parent_id' => 0
    ),
    array(
        'id' => 2,
        'name' => ' ',
        'parent_id' => 1
    ),
    array(
        'id' => 3,
        'name' => ' ',
        'parent_id' => 1
    ),
    array(
        'id' => 4,
        'name' => ' ',
        'parent_id' => 0
    ),
    array(
        'id' => 5,
        'name' => ' ',
        'parent_id' => 4
    ),
    array(
        'id' => 6,
        'name' => ' ',
        'parent_id' => 5
    )
);

$r = PHPTree::makeTreeForHtml($data);

echo '
PHPtree 트리 구조
';
echo '';
foreach($r as $item){
    echo '';
    echo str_repeat('......',$item['level']);
    echo $item['name'];
    echo '';
}
echo '';

// 
$menu_nav = Menu::find($request->id);
$nav[] = $menu_nav->title;
$i=0;
while(($menu_nav->pid)>0){
    $menu_nav = Menu::find($menu_nav->pid);
    array_unshift($nav,$menu_nav->title);
}