phpツリーアルゴリズム
11515 ワード
二叉樹の各結点はせいぜい二本の木(存在度が2より大きい結点)しかなく、二叉樹の子樹には左右の区別があり、順序が逆転してはならない.二叉木のi層目はせいぜい2^{i-1}個の接点がある.深さkの二叉木には2^k-1個の接点がある.いずれかの二叉木Tについて、その終端ノード数がn_である場合0,度2のノード数n_2ならn_0=n_2+1.
1本の深さはkであり、2^k-1個のノードを満二叉樹と呼ぶ.深さkは、n個のノードを有するツリーであり、各ノードが深さkのフルツリーのうち、シーケンス番号1〜nのノードに対応している場合にのみ、完全ツリーと呼ばれる.
1本の深さはkであり、2^k-1個のノードを満二叉樹と呼ぶ.深さkは、n個のノードを有するツリーであり、各ノードが深さkのフルツリーのうち、シーケンス番号1〜nのノードに対応している場合にのみ、完全ツリーと呼ばれる.
<?php
/** * */
class BinaryTree {
protected $key = NULL; //
protected $left = NULL; //
protected $right = NULL; //
/** * ， *
* @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;
}
/**
* Key ,
*
* @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 ， .
*/
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.
");
$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();