<?php
class Tree{
public $top=null;
public $leftChild=null;
public $rightChild=null;
public function Tree($top){
$this -> top = $top;
}
/**
* 添加一个子节点
**/
public function addChild($child){
if ($this -> top > $child){
//如果添加的节点比当前节点小 放到左边
if (empty($this->leftChild )){
//如果左边节点为空 直接给左边节点
$this->leftChild =new Tree($child);
}else {
//递归 左边节点添加子节点
$this->leftChild ->addChild ($child);
}
}else if ($this->top <$child){
//如果添加的节点比当前节点大 放到右边
if (empty($this->rightChild )){
//如果右边节点为空 直接给右边节点
$this->rightChild =new Tree($child);
}else {
//递归 右边节点添加子节点
$this->rightChild ->addChild ($child);
}
return true;
}else {
return false;
}
}
/**
* 获取一个子节点
**/
public function getChild ($child){
if ($this->top >$child){
return $this->leftChild ->getChild ($child);
}else if ($this->top <$child){
return $this->rightChild ->getChild ($child);
}else {
return $this;
}
}
/**
* 获取指定节点下的最大节点
**/
public function getMaxChild ($node){
if (empty($node->rightChild )){
return $node;
}else {
return $this->getMaxChild ($node->rightChild );
}
}
/**
* 获取指定节点下的最小节点
**/
public function getMinChild ($node){
if (empty($node->leftChild )){
return $node;
}else {
return $this->getMinChild ($node->leftChild );
}
}
/**
* 删除指定的节点
**/
public function removeChild ($child){
if ($this->top >$child){
if (empty($this->leftChild )){
return false;
}else {
if ($this->leftChild ->top ==$child){
if (isset($this->leftChild ->leftChild ) && isset($this->leftChild ->rightChild )){
$maxNode=$this->getMaxChild ($this->leftChild ->leftChild );
$this->removeChild ($maxNode->top );
$this->leftChild ->top =$maxNode->top ;
}else if (empty($this->leftChild ->leftChild )){
$this->leftChild =$this->getChild ($child)->rightChild ;
return true;
}else if (empty($this->leftChild ->rightChild )){
$this->leftChild =$this->getChild ($child)->leftChild ;
return true;
}else {
$this->leftChild =null;
return true;
}
}else {
return $this->leftChild ->removeChild ($child);
}
}
}else if ($this->top <$child){
if (empty($this->rightChild )){
return false;
}else {
if ($this->rightChild ->top ==$child){
if (isset($this->rightChild ->leftChild ) && isset($this->rightChild ->rightChild )){
$maxNode=$this->getMaxChild ($this->rightChild ->leftChild );
$this->removeChild ($maxNode->top );
$this->rightChild ->top =$maxNode->top ;
}else if (empty($this->rightChild ->leftChild )){
$this->rightChild =$this->getChild ($child)->rightChild ;
return true;
}else if (empty($this->rightChild ->rightChild )){
$this->rightChild =$this->getChild ($child)->leftChild ;
return true;
}else {
$this->rightChild =null;
return true;
}
}else {
return $this->rightChild ->removeChild ($child);
}
}
}else {
//根节点就是要删除的
if (isset($this ->leftChild ) && isset($this ->rightChild )){
$maxNode=$this->getMaxChild ($this -> leftChild );
$this-> removeChild ($maxNode -> top);
$this -> top = $maxNode->top ;
}else if (empty($this ->leftChild )){
$this->leftChild =$this->getChild ($this)->rightChild ;
return true;
}else if (empty($this ->rightChild )){
$this->leftChild =$this->getChild ($this)->leftChild ;
return true;
}else {
$this->leftChild =null;
return true;
}
}
}
}
$tree=new Tree(15);
$tree->addChild (9);
$tree->addChild (23);
$tree->addChild (3);
$tree->addChild (12);
$tree->addChild (17);
$tree->addChild (28);
$tree->addChild (8);
$tree->addChild (1);
$tree->addChild (4);
$tree->addChild (11);
$tree->removeChild (4);
$tree->removeChild (9);
$tree->removeChild (15);
print_r($tree);
Tree Object
(
[top] => 12
[leftChild] => Tree Object
(
[top] => 8
[leftChild] => Tree Object
(
[top] => 3
[leftChild] => Tree Object
(
[top] => 1
[leftChild] =>
[rightChild] =>
)
[rightChild] =>
)
[rightChild] => Tree Object
(
[top] => 11
[leftChild] =>
[rightChild] =>
)
)
[rightChild] => Tree Object
(
[top] => 23
[leftChild] => Tree Object
(
[top] => 17
[leftChild] =>
[rightChild] =>
)
[rightChild] => Tree Object
(
[top] => 28
[leftChild] =>
[rightChild] =>
)
)
)