php二叉树算法
二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)(不存在度大于2的結(jié)點(diǎn))，二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒。二叉樹(shù)的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。 一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹(shù)；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)。 <?php
/**? * 二叉樹(shù)的定義? */
class BinaryTree {
protected $key = NULL;????? //? 當(dāng)前節(jié)點(diǎn)的值
protected $left = NULL;???? //? 左子樹(shù)
protected $right = NULL;??? //? 右子樹(shù)
/**????? * 以指定的值構(gòu)造二叉樹(shù)，并指定左右子樹(shù)????? *
* @param mixed $key 節(jié)點(diǎn)的值.
* @param mixed $left 左子樹(shù)節(jié)點(diǎn).
* @param mixed $right 右子樹(shù)節(jié)點(diǎn).
*/
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;}}/*** 析構(gòu)方法.*/public function __destruct() {$this->key = NULL;$this->left = NULL;$this->right = NULL;}/*** 清空二叉樹(shù).**/public function purge () {$this->key = NULL;$this->left = NULL;$this->right = NULL;}/*** 測(cè)試當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn).** @return boolean 如果節(jié)點(diǎn)非空并且有兩個(gè)空的子樹(shù)時(shí)為真，否則為假.*/public function isLeaf() {return !$this->isEmpty() &&$this->left->isEmpty() &&$this->right->isEmpty();}/*** 測(cè)試節(jié)點(diǎn)是否為空** @return boolean 如果節(jié)點(diǎn)為空返回真，否則為假.*/public function isEmpty() {return $this->key === NULL;}/*** Key getter.** @return mixed 節(jié)點(diǎn)的值.*/public function getKey() {if ($this->isEmpty()) {return false;}return $this->key;}/*** 給節(jié)點(diǎn)指定Key值,節(jié)點(diǎn)必須為空** @param mixed $object 添加的Key值.*/public function attachKey($obj) {if (!$this->isEmpty())return false;$this->key = $obj;$this->left = new BinaryTree();$this->right = new BinaryTree();}/*** 刪除key值，使得節(jié)點(diǎn)為空.*/public function detachKey() {if (!$this->isLeaf())return false;$result = $this->key;$this->key = NULL;$this->left = NULL;$this->right = NULL;return $result;}/*** 返回左子樹(shù)** @return object BinaryTree 當(dāng)前節(jié)點(diǎn)的左子樹(shù).*/public function getLeft() {if ($this->isEmpty())return false;return $this->left;}/*** 給當(dāng)前結(jié)點(diǎn)添加左子樹(shù)** @param object BinaryTree $t 給當(dāng)前節(jié)點(diǎn)添加的子樹(shù).*/public function attachLeft(BinaryTree $t) {if ($this->isEmpty() || !$this->left->isEmpty())return false;$this->left = $t;}/*** 刪除左子樹(shù)** @return object BinaryTree? 返回刪除的左子樹(shù).*/public function detachLeft() {if ($this->isEmpty())return false;$result = $this->left;$this->left = new BinaryTree();return $result;}/*** 返回當(dāng)前節(jié)點(diǎn)的右子樹(shù)** @return object BinaryTree 當(dāng)前節(jié)點(diǎn)的右子樹(shù).*/public function getRight() {if ($this->isEmpty())return false;return $this->right;}/*** 給當(dāng)前節(jié)點(diǎn)添加右子樹(shù)** @param object BinaryTree $t 需要添加的右子樹(shù).*/public function attachRight(BinaryTree $t) {if ($this->isEmpty() || !$this->right->isEmpty())return false;$this->right = $t;}/*** 刪除右子樹(shù)，并返回此右子樹(shù)* @return object BinaryTree 刪除的右子樹(shù).*/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();}
}/*** 二叉排序樹(shù)的PHP實(shí)現(xiàn)*/class BST extends BinaryTree {/*** 構(gòu)造空的二叉排序樹(shù)*/public function __construct() {parent::__construct(NULL, NULL, NULL);}/*** 析構(gòu)*/public function __destruct() {parent::__destruct();}/*** 測(cè)試二叉排序樹(shù)中是否包含參數(shù)所指定的值** @param mixed $obj 查找的值.* @return boolean True 如果存在于二叉排序樹(shù)中則返回真，否則為假期*/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);elsereturn $this->getRight()->contains($obj);}/*** 查找二叉排序樹(shù)中參數(shù)所指定的值的位置** @param mixed $obj 查找的值.* @return boolean True 如果存在則返回包含此值的對(duì)象，否則為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);elsereturn $this->getRight()->find($obj);}/*** 返回二叉排序樹(shù)中的最小值* @return mixed 如果存在則返回最小值，否則返回NULL*/public function findMin() {if ($this->isEmpty ())return NULL;elseif ($this->getLeft()->isEmpty())return $this->getKey();elsereturn $this->getLeft()->findMin();}/*** 返回二叉排序樹(shù)中的最大值* @return mixed 如果存在則返回最大值，否則返回NULL*/public function findMax() {if ($this->isEmpty ())return NULL;elseif ($this->getRight()->isEmpty())return $this->getKey();elsereturn $this->getRight()->findMax();}/*** 給二叉排序樹(shù)插入指定值** @param mixed $obj 需要插入的值.* 如果指定的值在樹(shù)中存在，則返回錯(cuò)誤*/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();}/*** 從二叉排序樹(shù)中刪除指定的值** @param mixed $obj 需要?jiǎng)h除的值.*/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();
轉(zhuǎn)載于:https://www.cnblogs.com/icyy/p/4672724.html
總結(jié)
- 上一篇： grunt安装
- 下一篇： webservice jsonp格式调用