<?php /**  * Tanphp framework  *  *  * @category   Tanphp  * @package    Data_structure  * @version    $Id: Tree.php 25024 2012-11-26 22:22:22 tanbo $  */   /**  * 树形结构数据存取类  *   * 用于对树形结构数据进行快速的存取  *   * @param array $arr 参数必须为标准的二维数组，包含索引字段（id）与表示树形结构的字段(path),如example中所示  *   * @example <code>  * $arr = array(  *  array( 'id' => 1, 'name' => 'php', 'path' => '1' ),  *  array( 'id' => 3, 'name' => 'php1', 'path' => '1-3' ),  *  array( 'id' => 2, 'name' => 'mysql', 'path' => '2' ),  *  array( 'id' => 6, 'name' => 'mysql1', 'path' => '2-6' ),  *  array( 'id' => 7, 'name' => 'mysql2', 'path' => '2-7' ),  *  array( 'id' => 5, 'name' => 'php11', 'path' => '1-3-5' ),  *  array( 'id' => 4, 'name' => 'php2', 'path' => '1-4' ),  *   );  *  $cate = new Tree($arr);  *    *  $data = $cate->getChild(2);  *    *  print_r($data->toArray());  * </code>  *   */ class Tree {     public  $_info;                             //节点信息     public  $_child = array();                  //子节点     private $_parent;                           //父节点     private $_data;                             //当前操作的临时数据     private static $_indexs         = array();  //所有节点的索引     private static $_index_key      = 'id';     //索引键     private static $_tree_key       = 'path';   //树形结构表达键     private static $_tree_delimiter = '-';      //属性结构表达分割符          /**      * 构造函数      *       * @param array $arr      * @param boole $force_sort 如果为真，将会强制对$arr 进行排序      * @return void      */     public function __construct(array $arr = array(),  $force_sort=true)     {         if ($force_sort === true) {             $arr=$this->_array_sort($arr, self::$_tree_key);         }         if (!emptyempty($arr)) {             $this->_init($arr);         }     }          /**      * 初始存储树形数据      *       * @param array $arr      * @return void      */     private function _init(array $arr)     {         foreach ($arr as $item) {             $path        = $item[self::$_tree_key];             $paths       = explode(self::$_tree_delimiter, $path);             $count_paths = count($paths);             $parent_id   = isset($paths[$count_paths-2]) ? $paths[$count_paths-2] : NULL;                          if (   $count_paths>1                                   //如果有父级                 && array_key_exists($parent_id, self::$_indexs)      //父级已经被存入索引                 && self::$_indexs[$parent_id] instanceof Tree    //父级为Tree对象             ) {                 self::$_indexs[$parent_id]->addChild($item);             } elseif ($count_paths == 1) {                 $this->addChild($item);             } else {                 throw new Exception("path数据错误".var_export($item, true));             }         }                  //print_r(self::$_indexs);     }          /**      * 添加子节点      *       * @param array $item      * @return void      */     public function addChild(array $item, $parent = NULL)     {         $child          = new Tree();         $child->_info   = $item;         $child->_parent = $parent == NULL ? $this : $parent;         $child->_parent->_child[] =  $child;                  $this->_addIndex($item, $child->_getSelf());      }          /**      * 添加节点到索引      *       * @param array $item      * @param mix $value      * @return void      */     private function _addIndex(array $item, $value)     {         if (array_key_exists(self::$_index_key, $item) && is_int($item[self::$_index_key])) {             self::$_indexs[$item[self::$_index_key]] = $value;         } else {             throw new Exception("id字段不存在或者不为字符串");         }     }          /**      * 获取对自己的引用      *       * @return Tree object quote      */     private function _getSelf()     {         return $this;     }          /**      * 获取指定id的节点的子节点      *       * @param int $id      * @return Tree object      */     public function getChild($id)     {         $data       = self::$_indexs[$id]->_child;         $this->_data = $data;         return $this;     }          /**      * 获取指定id的节点的父节点      *       * @param int $id      * @return Tree object      */     public function getParent($id)     {         $data = self::$_indexs[$id]->_parent;         $this->_data = $data;         return $this;     }          /**      * 获取指定id的节点的同级节点      *      * @param int $id      * @return Tree object      */     public function getBrother($id)     {         $data = self::$_indexs[$id]->_parent->_child;         $this->_data = $data;         return $this;     }          /**      * 将Tree对象转化为数组      *       * @param  object $object      * @return array      */      public function toArray($obj = NULL)      {         $obj  = ($obj === NULL) ? $this->_data : $obj;         $arr  = array();         $_arr = is_object($obj) ? $this->_getBaseInfo($obj) : $obj;                  if (is_array($_arr)) {             foreach ($_arr as $key => $val){                                  $val = (is_array($val) || is_object($val)) ? $this->toArray($val) : $val;                 $arr[$key] = $val;             }         } else {             throw new Exception("_arr不是数组");         }               return $arr;     }          /**      * 过滤_parent等字段，以免造成无限循环      *       * @param object $obj      * @return void      */     private function _getBaseInfo($obj)     {         $vars = get_object_vars($obj);         $baseInfo['_info']  =  $vars['_info'];         $baseInfo['_child'] =  $vars['_child'];         return $baseInfo;     }          /**      * 二维数组排序      *      * 根据指定的键名对二维数组进行升序或者降序排列      *      * @param array  $arr 二维数组      * @param string $keys      * @param string $type 必须为 asc或desc      * @throws 当参数非法时抛出异常      * @return 返回排序好的数组      */     private function _array_sort(array $arr, $keys, $type = 'asc') {         if (!is_string($keys)) {             throw new Exception("非法参数keys:参数keys的类型必须为字符串");         }              $keysvalue = $new_array = array();         foreach ($arr as $k=>$v) {             if (!is_array($v) || !isset($v[$keys])) {                 throw new Exception("参数arr不是二维数组或arr子元素中不存在键'{$keys}'");             }             $keysvalue[$k] = $v[$keys];         }              switch ($type) {             case 'asc':                 asort($keysvalue);                 break;             case 'desc':                 arsort($keysvalue);                 break;             default:                 throw new Exception("非法参数type ：参数type的值必须为 'asc' 或 'desc'");         }              reset($keysvalue);         foreach ($keysvalue as $k=>$v) {             $new_array[$k] = $arr[$k];         }         return $new_array;     } } ?>