一個二叉樹及二叉排序樹的php版本

<?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();