1. <?php 
2. /** 
3.  * Tanphp framework 
4.  * 
5.  * 
6.  * @category   Tanphp 
7.  * @package    Data_structure 
8.  * @copyright  Copyright (c) 2012 譚博  tanbo.name 
9.  * @version    $Id: Tree.php 25024 2012-11-26 22:22:22 tanbo $ 
10.  */ 
11.  
12. /** 
13.  * 樹形結構數據存取類 
14.  *  
15.  * 用于對樹形結構數據進行快速的存取 
16.  *  
17.  * @param array $arr 參數必須為標準的二維數組，包含索引字段（id）與表示樹形結構的字段(path),如example中所示 
18.  *  
19.  * @example <code> 
20.  * $arr = array( 
21.  *  array( 'id' => 1, 'name' => 'php', 'path' => '1' ), 
22.  *  array( 'id' => 3, 'name' => 'php1', 'path' => '1-3' ), 
23.  *  array( 'id' => 2, 'name' => 'mysql', 'path' => '2' ), 
24.  *  array( 'id' => 6, 'name' => 'mysql1', 'path' => '2-6' ), 
25.  *  array( 'id' => 7, 'name' => 'mysql2', 'path' => '2-7' ), 
26.  *  array( 'id' => 5, 'name' => 'php11', 'path' => '1-3-5' ), 
27.  *  array( 'id' => 4, 'name' => 'php2', 'path' => '1-4' ), 
28.  *   ); 
29.  *  $cate = new Tree($arr); 
30.  *   
31.  *  $data = $cate->getChild(2); 
32.  *   
33.  *  print_r($data->toArray()); 
34.  * </code> 
35.  *  
36.  */ 
37. class Tree 
38. { 
39.     public  $_info;                             //節點信息 
40.     public  $_child = array();                  //子節點 
41.     private $_parent;                           //父節點 
42.     private $_data;                             //當前操作的臨時數據 
43.     private static $_indexs         = array();  //所有節點的索引 
44.     private static $_index_key      = 'id';     //索引鍵 
45.     private static $_tree_key       = 'path';   //樹形結構表達鍵 
46.     private static $_tree_delimiter = '-';      //屬性結構表達分割符 
47.      
48.      
49.      
50.     /** 
51.      * 構造函數 
52.      *  
53.      * @param array $arr 
54.      * @param boole $force_sort 如果為真，將會強制對$arr 進行排序 
55.      * @return void 
56.      */ 
57.     public function __construct(array $arr = array(),  $force_sort=true) 
58.     { 
59.         if ($force_sort === true) { 
60.             $arr=$this->_array_sort($arr, self::$_tree_key); 
61.         } 
62.         if (!emptyempty($arr)) { 
63.             $this->_init($arr); 
64.         } 
65.     } 
66.      
67.     /** 
68.      * 初始存儲樹形數據 
69.      *  
70.      * @param array $arr 
71.      * @return void 
72.      */ 
73.     private function _init(array $arr) 
74.     { 
75.         foreach ($arr as $item) { 
76.             $path        = $item[self::$_tree_key]; 
77.             $paths       = explode(self::$_tree_delimiter, $path); 
78.             $count_paths = count($paths); 
79.             $parent_id   = isset($paths[$count_paths-2]) ? $paths[$count_paths-2] : NULL; 
80.              
81.             if (   $count_paths>1                                   //如果有父級 
82.                 && array_key_exists($parent_id, self::$_indexs)      //父級已經被存入索引 
83.                 && self::$_indexs[$parent_id] instanceof Tree    //父級為Tree對象 
84.             ) { 
85.                 self::$_indexs[$parent_id]->addChild($item); 
86.             } elseif ($count_paths == 1) { 
87.                 $this->addChild($item); 
88.             } else { 
89.                 throw new Exception("path數據錯誤".var_export($item, true)); 
90.             } 
91.              
92.         } 
93.          
94.         //print_r(self::$_indexs); 
95.     } 
96.      
97.     /** 
98.      * 添加子節點 
99.      *  
100.      * @param array $item 
101.      * @return void 
102.      */ 
103.     public function addChild(array $item, $parent = NULL) 
104.     { 
105.         $child          = new Tree(); 
106.         $child->_info   = $item; 
107.         $child->_parent = $parent == NULL ? $this : $parent; 
108.         $child->_parent->_child[] =  $child; 
109.          
110.         $this->_addIndex($item, $child->_getSelf());  
111.     } 
112.      
113.     /** 
114.      * 添加節點到索引 
115.      *  
116.      * @param array $item 
117.      * @param mix $value 
118.      * @return void 
119.      */ 
120.     private function _addIndex(array $item, $value) 
121.     { 
122.         if (array_key_exists(self::$_index_key, $item) && is_int($item[self::$_index_key])) { 
123.             self::$_indexs[$item[self::$_index_key]] = $value; 
124.         } else { 
125.             throw new Exception("id字段不存在或者不為字符串"); 
126.         } 
127.     } 
128.      
129.      
130.     /** 
131.      * 獲取對自己的引用 
132.      *  
133.      * @return Tree object quote 
134.      */ 
135.     private function _getSelf() 
136.     { 
137.         return $this; 
138.     } 
139.      
140.     /** 
141.      * 獲取指定id的節點的子節點 
142.      *  
143.      * @param int $id 
144.      * @return Tree object 
145.      */ 
146.     public function getChild($id) 
147.     { 
148.         $data       = self::$_indexs[$id]->_child; 
149.         $this->_data = $data; 
150.         return $this; 
151.     } 
152.      
153.     /** 
154.      * 獲取指定id的節點的父節點 
155.      *  
156.      * @param int $id 
157.      * @return Tree object 
158.      */ 
159.     public function getParent($id) 
160.     { 
161.         $data = self::$_indexs[$id]->_parent; 
162.         $this->_data = $data; 
163.         return $this; 
164.     } 
165.      
166.     /** 
167.      * 獲取指定id的節點的同級節點 
168.      * 
169.      * @param int $id 
170.      * @return Tree object 
171.      */ 
172.     public function getBrother($id) 
173.     { 
174.         $data = self::$_indexs[$id]->_parent->_child; 
175.         $this->_data = $data; 
176.         return $this; 
177.     } 
178.      
179.     /** 
180.      * 將Tree對象轉化為數組 
181.      *  
182.      * @param  object $object 
183.      * @return array 
184.      */ 
185.      public function toArray($obj = NULL) 
186.      { 
187.         $obj  = ($obj === NULL) ? $this->_data : $obj; 
188.         $arr  = array(); 
189.         $_arr = is_object($obj) ? $this->_getBaseInfo($obj) : $obj; 
190.          
191.         if (is_array($_arr)) { 
192.             foreach ($_arr as $key => $val){ 
193.                  
194.                 $val = (is_array($val) || is_object($val)) ? $this->toArray($val) : $val; 
195.                      
196.                 $arr[$key] = $val; 
197.             } 
198.         } else { 
199.             throw new Exception("_arr不是數組"); 
200.         } 
201.          
202.       
203.         return $arr; 
204.     } 
205.      
206.     /** 
207.      * 過濾_parent等字段，以免造成無限循環 
208.      *  
209.      * @param object $obj 
210.      * @return void 
211.      */ 
212.     private function _getBaseInfo($obj) 
213.     { 
214.         $vars = get_object_vars($obj); 
215.         $baseInfo['_info']  =  $vars['_info']; 
216.         $baseInfo['_child'] =  $vars['_child']; 
217.         return $baseInfo; 
218.     } 
219.      
220.     /** 
221.      * 二維數組排序 
222.      * 
223.      * 根據指定的鍵名對二維數組進行升序或者降序排列 
224.      * 
225.      * @param array  $arr 二維數組 
226.      * @param string $keys 
227.      * @param string $type 必須為 asc或desc 
228.      * @throws 當參數非法時拋出異常 
229.      * @return 返回排序好的數組 
230.      */ 
231.     private function _array_sort(array $arr, $keys, $type = 'asc') { 
232.         if (!is_string($keys)) { 
233.             throw new Exception("非法參數keys:參數keys的類型必須為字符串"); 
234.         } 
235.      
236.         $keysvalue = $new_array = array(); 
237.         foreach ($arr as $k=>$v) { 
238.             if (!is_array($v) || !isset($v[$keys])) { 
239.                 throw new Exception("參數arr不是二維數組或arr子元素中不存在鍵'{$keys}'"); 
240.             } 
241.             $keysvalue[$k] = $v[$keys]; 
242.         } 
243.      
244.         switch ($type) { 
245.             case 'asc': 
246.                 asort($keysvalue); 
247.                 break; 
248.             case 'desc': 
249.                 arsort($keysvalue); 
250.                 break; 
251.             default: 
252.                 throw new Exception("非法參數type ：參數type的值必須為 'asc' 或 'desc'"); 
253.         } 
254.      
255.         reset($keysvalue); 
256.         foreach ($keysvalue as $k=>$v) { 
257.             $new_array[$k] = $arr[$k]; 
258.         } 
259.         return $new_array; 
260.     } 
261.      
262. } 
263. ?>