浜屽弶鏍戝強浜屽弶鎺掑簭鏍戠殑PHP瀹炵幇
鏈€杩戜竴娈垫椂闂村湪鐪嬪緢鍩虹鐨勬暟鎹粨鏋勶紝鏈潵鎯虫妸涓€浜涙暟鎹粨鏋勫拰绠楁硶鐢≒HP瀹炵幇
浣嗘槸google鎼滅储鍚庯紝鍙戠幇涓€涓娇鐢╬hp瀹炵幇鐨勫熀鏈殑鏁版嵁缁撴瀯鍜岀畻娉曪紝浜屽弶鏍戙€佷簩鍙夋悳绱㈡爲銆丄VL鏍戙€丅鏍戙€侀摼琛ㄥ拰甯歌鎺掑簭銆佹悳绱㈢畻娉曠瓑绛夐兘鏈夊疄鐜帮紝鑰屼笖鍏ㄩ儴鏄娇鐢ㄩ潰鍚戝璞℃潵瀹炵幇鐨勶紝鍙兘鑶滄嫓銆?/p>
婧愮爜鍦板潃锛?a href="http://www.brpreiss.com/books/opus11/public/Opus11-1.0.tar.gz">http://www.brpreiss.com/books/opus11/public/Opus11-1.0.tar.gz
鏂囨。鍦板潃锛?a href="http://www.brpreiss.com/books/opus11/">http://www.brpreiss.com/books/opus11/
闃呰鍚庯紝灏嗗叾涓浜庝簩鍙夋爲鍙婁簩鍙夋帓搴忔爲鐨勫疄鐜版彁鍙栧嚭鏉ワ紝浠g爜濡備笅锛?/p>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 | <?php /** * 浜屽弶鏍戠殑瀹氫箟 */ class BinaryTree { protected $key = NULL; // 褰撳墠鑺傜偣鐨勫€?/span> protected $left = NULL; // 宸﹀瓙鏍?/span> protected $right = NULL; // 鍙冲瓙鏍?/span> /** * 浠ユ寚瀹氱殑鍊兼瀯閫犱簩鍙夋爲锛屽苟鎸囧畾宸﹀彸瀛愭爲 * * @param mixed $key 鑺傜偣鐨勫€? * @param mixed $left 宸﹀瓙鏍戣妭鐐? * @param mixed $right 鍙冲瓙鏍戣妭鐐? */ public function __construct( $key = NULL, $left = NULL, $right = NULL) { $this->key = $key; if ($key === NULL) { $this->left = NULL; $this->right = NULL; } elseif ($left === NULL) { $this->left = new BinaryTree(); $this->right = new BinaryTree(); } else { $this->left = $left; $this->right = $right; } } /** * 鏋愭瀯鏂规硶. */ public function __destruct() { $this->key = NULL; $this->left = NULL; $this->right = NULL; } /** * 娓呯┖浜屽弶鏍? **/ public function purge () { $this->key = NULL; $this->left = NULL; $this->right = NULL; } /** * 娴嬭瘯褰撳墠鑺傜偣鏄惁鏄彾鑺傜偣. * * @return boolean 濡傛灉鑺傜偣闈炵┖骞朵笖鏈変袱涓┖鐨勫瓙鏍戞椂涓虹湡锛屽惁鍒欎负鍋? */ public function isLeaf() { return !$this->isEmpty() && $this->left->isEmpty() && $this->right->isEmpty(); } /** * 娴嬭瘯鑺傜偣鏄惁涓虹┖ * * @return boolean 濡傛灉鑺傜偣涓虹┖杩斿洖鐪燂紝鍚﹀垯涓哄亣. */ public function isEmpty() { return $this->key === NULL; } /** * Key getter. * * @return mixed 鑺傜偣鐨勫€? */ public function getKey() { if ($this->isEmpty()) { return false; } return $this->key; } /** * 缁欒妭鐐规寚瀹欿ey鍊?鑺傜偣蹇呴』涓虹┖ * * @param mixed $object 娣诲姞鐨凨ey鍊? */ public function attachKey($obj) { if (!$this->isEmpty()) return false; $this->key = $obj; $this->left = new BinaryTree(); $this->right = new BinaryTree(); } /** * 鍒犻櫎key鍊硷紝浣垮緱鑺傜偣涓虹┖. */ public function detachKey() { if (!$this->isLeaf()) return false; $result = $this->key; $this->key = NULL; $this->left = NULL; $this->right = NULL; return $result; } /** * 杩斿洖宸﹀瓙鏍? * * @return object BinaryTree 褰撳墠鑺傜偣鐨勫乏瀛愭爲. */ public function getLeft() { if ($this->isEmpty()) return false; return $this->left; } /** * 缁欏綋鍓嶇粨鐐规坊鍔犲乏瀛愭爲 * * @param object BinaryTree $t 缁欏綋鍓嶈妭鐐规坊鍔犵殑瀛愭爲. */ public function attachLeft(BinaryTree $t) { if ($this->isEmpty() || !$this->left->isEmpty()) return false; $this->left = $t; } /** * 鍒犻櫎宸﹀瓙鏍? * * @return object BinaryTree 杩斿洖鍒犻櫎鐨勫乏瀛愭爲. */ public function detachLeft() { if ($this->isEmpty()) return false; $result = $this->left; $this->left = new BinaryTree(); return $result; } /** * 杩斿洖褰撳墠鑺傜偣鐨勫彸瀛愭爲 * * @return object BinaryTree 褰撳墠鑺傜偣鐨勫彸瀛愭爲. */ public function getRight() { if ($this->isEmpty()) return false; return $this->right; } /** * 缁欏綋鍓嶈妭鐐规坊鍔犲彸瀛愭爲 * * @param object BinaryTree $t 闇€瑕佹坊鍔犵殑鍙冲瓙鏍? */ public function attachRight(BinaryTree $t) { if ($this->isEmpty() || !$this->right->isEmpty()) return false; $this->right = $t; } /** * 鍒犻櫎鍙冲瓙鏍戯紝骞惰繑鍥炴鍙冲瓙鏍? * @return object BinaryTree 鍒犻櫎鐨勫彸瀛愭爲. */ public function detachRight() { if ($this->isEmpty ()) return false; $result = $this->right; $this->right = new BinaryTree(); return $result; } /** * 鍏堝簭閬嶅巻 */ public function preorderTraversal() { if ($this->isEmpty()) { return ; } echo ' ', $this->getKey(); $this->getLeft()->preorderTraversal(); $this->getRight()->preorderTraversal(); } /** * 涓簭閬嶅巻 */ public function inorderTraversal() { if ($this->isEmpty()) { return ; } $this->getLeft()->preorderTraversal(); echo ' ', $this->getKey(); $this->getRight()->preorderTraversal(); } /** * 鍚庡簭閬嶅巻 */ public function postorderTraversal() { if ($this->isEmpty()) { return ; } $this->getLeft()->preorderTraversal(); $this->getRight()->preorderTraversal(); echo ' ', $this->getKey(); } } /** * 浜屽弶鎺掑簭鏍戠殑PHP瀹炵幇 */ class BST extends BinaryTree { /** * 鏋勯€犵┖鐨勪簩鍙夋帓搴忔爲 */ public function __construct() { parent::__construct(NULL, NULL, NULL); } /** * 鏋愭瀯 */ public function __destruct() { parent::__destruct(); } /** * 娴嬭瘯浜屽弶鎺掑簭鏍戜腑鏄惁鍖呭惈鍙傛暟鎵€鎸囧畾鐨勫€? * * @param mixed $obj 鏌ユ壘鐨勫€? * @return boolean True 濡傛灉瀛樺湪浜庝簩鍙夋帓搴忔爲涓垯杩斿洖鐪燂紝鍚﹀垯涓哄亣鏈? */ public function contains($obj) { if ($this->isEmpty()) return false; $diff = $this->compare($obj); if ($diff == 0) { return true; }elseif ($diff < 0) return $this->getLeft()->contains($obj); else return $this->getRight()->contains($obj); } /** * 鏌ユ壘浜屽弶鎺掑簭鏍戜腑鍙傛暟鎵€鎸囧畾鐨勫€肩殑浣嶇疆 * * @param mixed $obj 鏌ユ壘鐨勫€? * @return boolean True 濡傛灉瀛樺湪鍒欒繑鍥炲寘鍚鍊肩殑瀵硅薄锛屽惁鍒欎负NULL */ public function find($obj) { if ($this->isEmpty()) return NULL; $diff = $this->compare($obj); if ($diff == 0) return $this->getKey(); elseif ($diff < 0) return $this->getLeft()->find($obj); else return $this->getRight()->find($obj); } /** * 杩斿洖浜屽弶鎺掑簭鏍戜腑鐨勬渶灏忓€? * @return mixed 濡傛灉瀛樺湪鍒欒繑鍥炴渶灏忓€硷紝鍚﹀垯杩斿洖NULL */ public function findMin() { if ($this->isEmpty ()) return NULL; elseif ($this->getLeft()->isEmpty()) return $this->getKey(); else return $this->getLeft()->findMin(); } /** * 杩斿洖浜屽弶鎺掑簭鏍戜腑鐨勬渶澶у€? * @return mixed 濡傛灉瀛樺湪鍒欒繑鍥炴渶澶у€硷紝鍚﹀垯杩斿洖NULL */ public function findMax() { if ($this->isEmpty ()) return NULL; elseif ($this->getRight()->isEmpty()) return $this->getKey(); else return $this->getRight()->findMax(); } /** * 缁欎簩鍙夋帓搴忔爲鎻掑叆鎸囧畾鍊? * * @param mixed $obj 闇€瑕佹彃鍏ョ殑鍊? * 濡傛灉鎸囧畾鐨勫€煎湪鏍戜腑瀛樺湪锛屽垯杩斿洖閿欒 */ public function insert($obj) { if ($this->isEmpty()) { $this->attachKey($obj); } else { $diff = $this->compare($obj); if ($diff == 0) die('argu error'); if ($diff < 0) $this->getLeft()->insert($obj); else $this->getRight()->insert($obj); } $this->balance(); } /** * 浠庝簩鍙夋帓搴忔爲涓垹闄ゆ寚瀹氱殑鍊? * * @param mixed $obj 闇€瑕佸垹闄ょ殑鍊? */ public function delete($obj) { if ($this->isEmpty ()) die(); $diff = $this->compare($obj); if ($diff == 0) { if (!$this->getLeft()->isEmpty()) { $max = $this->getLeft()->findMax(); $this->key = $max; $this->getLeft()->delete($max); } elseif (!$this->getRight()->isEmpty()) { $min = $this->getRight()->findMin(); $this->key = $min; $this->getRight()->delete($min); } else $this->detachKey(); } else if ($diff < 0) $this->getLeft()->delete($obj); else $this->getRight()->delete($obj); $this->balance(); } public function compare($obj) { return $obj - $this->getKey(); } /** * Attaches the specified object as the key of this node. * The node must be initially empty. * * @param object IObject $obj The key to attach. * @exception IllegalOperationException If this node is not empty. */ public function attachKey($obj) { if (!$this->isEmpty()) return false; $this->key = $obj; $this->left = new BST(); $this->right = new BST(); } /** * Balances this node. * Does nothing in this class. */ protected function balance () {} /** * Main program. * * @param array $args Command-line arguments. * @return integer Zero on success; non-zero on failure. */ public static function main($args) { printf("BinarySearchTree main program.\n"); $root = new BST(); foreach ($args as $row) { $root->insert($row); } return $root; } } $root = BST::main(array(50, 3, 10, 5, 100, 56, 78)); echo $root->findMax(); $root->delete(100); echo $root->findMax(); |
浠ヤ笂浠g爜鐪嬩簡鍑犻亶锛屾湁浜涙湜灏樿帿鍙婄殑鎰熻
宸窛寰堝ぇ锛岃€屼笖杩樻槸2005骞村啓鐨?br />
鍐嶆鑶滄嫓锛?br />
EOF
鏈枃鍦板潃锛?a href="http://www.phppan.com/2010/04/binary-tree-and-binary-sort-tree-php/" title="浜屽弶鏍戝強浜屽弶鎺掑簭鏍戠殑PHP瀹炵幇" rel="bookmark">浜屽弶鏍戝強浜屽弶鎺掑簭鏍戠殑PHP瀹炵幇 鏂囩珷鍑哄锛?a href="http://www.phppan.com/" title="PHP銆€鎵╁睍銆€绋嬪簭銆€鐢熸椿鏉傝皥">鑳栧瓙鐨勭┖闂?/a>
杞浇璇蜂互閾炬帴褰㈠紡娉ㄦ槑鍘熷鍑哄鍜屼綔鑰咃紝璋㈢粷涓嶅皧閲嶇増鏉冭€呮妱琚紒
鏍囩锛?a href="http://www.phppan.com/tag/binary-sort-tree/" rel="tag">Binary Sort Tree, , ,