php实现二叉查找树
树的节点
/**
* Class TNode
* 节点类
*/
class TNode
{
public $lnode = null;
public $rnode = null;
public $val = 0;
public function __construct($val, $lnode = null, $rnode = null)
{
$this->val = $val;
$this->lnode = $lnode;
$this->rnode = $rnode;
}
}
树的容器
/**
* Class BinarySearchTree
* 二叉查找树容器
*/
class BinarySearchTree
{
/**
* 用于存放根节点
* @var null|TNode
*/
protected $head = null;
/**
* 内部节点的指向引用
* @var null|TNode
*/
protected $pointer = null;
public function __construct(TNode &$node)
{
$this->head = &$node;
$this->pointer = $this->head;
}
/**
* 重置指针到根节点
*/
public function rewind()
{
$this->pointer = &$this->head;
}
/**
* 插入操作
* @param $val
*/
public function insert($val)
{
$this->rewind();
//遍历插入
while (true) {
if ($val > $this->pointer->val) {
//大于当前节点则向右查
if (!empty($this->pointer->rnode)) {
$this->pointer = &$this->pointer->rnode;
} else {
$this->pointer->rnode = new TNode($val);
break;
}
} else {
//小于当前节点则向左查
if (!empty($this->pointer->lnode)) {
$this->pointer = &$this->pointer->lnode;
} else {
$this->pointer->lnode = new TNode($val);
break;
}
}
}
}
/**
* 查找操作
* @param $val
* @return bool|null|TNode
*/
public function search($val)
{
//与插入类似
$this->rewind();
while (true) {
if ($val > $this->pointer->val) {
if (!empty($this->pointer->rnode)) {
$this->pointer = &$this->pointer->rnode;
} else {
return false;
}
} else if ($val < $this->pointer->val) {
if (!empty($this->pointer->lnode)) {
$this->pointer = &$this->pointer->lnode;
} else {
return false;
}
} else {
return $this->pointer;
}
}
}
/**
* 删除操作
* @param $val
* @return bool
*/
public function delete($val)
{
$this->rewind();
$flag = true;
$prev_pointer = null;
//遍历寻找需要被删除的数据
while (true) {
if ($val > $this->pointer->val) {
if (!empty($this->pointer->rnode)) {
$prev_pointer = $this->pointer;
$this->pointer = &$this->pointer->rnode;
} else {
$flag = false;
break;
}
} else if ($val < $this->pointer->val) {
if (!empty($this->pointer->lnode)) {
$prev_pointer = $this->pointer;
$this->pointer = &$this->pointer->lnode;
} else {
$flag = false;
break;
}
} else {
break;
}
}
if ($flag === false) {
return false;
}
if ($this->pointer->rnode == null || $this->pointer->lnode == null) {
//存在左边
if ($this->pointer == $prev_pointer->lnode) {
unset($prev_pointer->lnode);
$prev_pointer->lnode = $this->pointer->lnode;
} else {
unset($prev_pointer->rnode);
$prev_pointer->rnode = $this->pointer->lnode;
}
unset($this->pointer);
} else if ($this->pointer->rnode != null && $this->pointer->rnode == null) {
//存在右边分支
if ($this->pointer == $prev_pointer->lnode) {
unset($prev_pointer->lnode);
$prev_pointer->lnode = $this->pointer->rnode;
} else {
unset($prev_pointer->rnode);
$prev_pointer->rnode = $this->pointer->rnode;
}
unset($this->pointer);
} else if ($this->pointer->rnode == null && $this->pointer->lnode == null) {
//不存在两边分支
if ($this->pointer == $prev_pointer->lnode) {
unset($prev_pointer->lnode);
} else {
unset($prev_pointer->rnode);
}
unset($this->pointer);
} else {
//两边都存在分支
$temp = &$this->pointer;
//先转向左节点
$search = &$this->pointer->lnode;
//一直向右寻找
while (!empty($search->rnode)) {
$temp = &$search;
$search = &$search->rnode;
}
$this->pointer->val = $search->val;
//如果第一次寻找存在右节点
if ($temp != $this->pointer) {
//重置右节点
$temp->rnode = $search->lnode;
} else {
//重置左节点
$temp->lnode = $search->lnode;
}
}
}
}
实例演示
$tree = new BinarySearchTree(new TNode(1));
$tree->insert(2);
$tree->insert(5);
$tree->insert(7);
$tree->insert(3);
$tree->insert(6);
$tnode = $tree->search(5);
var_dump($tnode);
$tree->delete(5);
var_dump($tree);
码字很辛苦,转载请注明来自雨林寒舍的《php实现二叉查找树》
请问下这种代码块使用的什么插件?
highlight