数据结构之PHP二分搜索树
什么是二叉树，上面的结构就是一个二叉树，一个节点连着两个节点。二叉树具有唯一的根节点，每个节点都有两个子节点。换句话也就是说，二叉树每个节点最多有两个子节点，二叉树每个节点最多有一个父节点。
在树结构中，我们称顶级节点为根节点，下面的节点都为子节点，在子节点 的 左子树 和 右子树 都为空的时候，称之为叶子节点。
（二叉树 示意图）
二分搜索树每个节点的值:
大于当前节点左子树所有节点的值
小于当前节点右子树所有节点的值
每一个子树也是一个二分搜索树
（二分搜索树 示意图）
1. 添加元素
2. 查询和更改元素
3. 遍历元素
前序遍历
中序遍历
后序遍历
层序遍历
前序遍历主要思想就是，先访问节点元素，然后在对左右子树进行前序遍历操作。我们看下图：
先访问节点元素 28， 然后 在对 28 的 左子树进行遍历
然后访问节点元素 20， 然后对 20 的 左子树 进行遍历
访问节点元素 13， 然后对 13 的左子树进行遍历， 发现 13 左右子树都为空。这时访问节点右子树 22， 发现 22 左右字数都为空。所以遍历遍历结果为 20-13-22
此时返回节点元素 28， 对 28的 右子树 进行遍历, 访问节点元素 36，然后对 36 的 左子树进行遍历
访问 节点元素 30， 然后对 30 的左子树进行遍历， 发现 30 左右子树都为空。这时访问节点右子树 42， 发现 42 左右字数都为空。所以遍历遍历结果为 36-30-42
中序遍历主要思想就是，把访问根节点元素的操作放在中间，先对左子树进行遍历, 然后访问其节点元素, 最后遍历右子树。我们看下图：
先访问左子树
左子树的根节点为 20, 这时 在 对 20 的左子树进行遍历, 访问 13 , 发现13为叶子节点, 在返回根节点 20 , 最后访问 20 的右子树 22. 结果为 13-20-22
在访问根节点元素 , 结果为28
在访问右子树
右子树的根节点 为 36, 在对 36 的左子树进行遍历, 访问 30, 发现30为叶子节点, 在返回根节点 36 , 最后访问 36 的右子树 42. 结果为 30-36-42
有了前面两个遍历的基础, 后序遍历会比较简单了. 主要思想就是，把访问根节点元素的操作放在最后，先对左子树进行遍历, 然后遍历右子树。 最后其节点元素
层序遍历和前面的不同, 层序遍历是广度优先的算法. 也就是一层层的进行访问. 某一层深度访问完 后 继续往下访问.
这里我们需要借助队列进行实现, 主要的思想就是, 让每一层级的节点入队, 这样出队的元素 就是 左右节点的元素.
（ 层 序遍历 示意图）
4. 删除元素
（最大 最小 示意图）
删除就是删除左子树的最小点, 左子树分为两种情况：
若是叶子节点，直接删除该元素即可；
若无左子树节点，右子树节点顶替待删除节点。
（删除叶子节点 13 示意图）
（删除叶子节点20, 无左子树 示意图）
删除就是删除右子树的最大点, 右子树分为两种情况：
若是叶子节点，直接删除该元素即可；
若无右子树节点，左子树节点顶替待删除节点。
删除任意节点, 相对来讲会麻烦一点, 这里需要一个方法
One efficient way to do this, as discovered by Thomas Hibbard in 1962, is to swap the node to be deleted with its successor. The successor to a key is the next largest key in the tree and is conveniently found as the minimum key in the right subtree of the node to be deleted.
http://math.oxford.emory.edu/site/cs171/hibbardDeletion/
根据定义，36的右子树中最小的节点进行替换，右子树只有一个节点， 那也就是 42， 所以使用 42 替换 36。
前序根据定一样是一样的。就不画图了。大家可以动手理解下。
<?php
/**
* Created by : PhpStorm
* User: think abel
* Date: 2021/1/13 0013
* Time: 22:22
*/
include 'ArrayQueue/LinkedQueue.php';
class BinarySearchTree
{
private $root;
private $size;
public function __construct()
{
$this->root = null;
$this->size = 0;
}
/**
* Notes: 获取 二分搜索树 长度
* User: think abel
* Date: 2021/1/13 0013
* Time: 22:29
*
* @return int
*/
public function getSize()
{
return $this->size;
}
/**
* Notes: 二分搜索树是否为空
* User: think abel
* Date: 2021/1/13 0013
* Time: 22:29
*
* @return bool
*/
public function isEmpty()
{
return $this->size == 0;
}
/**
* Notes: 添加元素
* User: think abel
* Date: 2021/1/13 0013
* Time: 23:22
*
* @param $val
*/
public function add($val)
{
$this->root = $this->recursion($this->root, $val);
}
/**
* Notes: 递归插入
* User: think abel
* Date: 2021/1/13 0013
* Time: 22:45
*
* @param BinarySearchTreeNode $node
* @param $val
*
* @return BinarySearchTreeNode
*/
private function recursion($node, $val)
{
// 暂时不包含重复值
if ($node == null) {
$this->size ++;
return new BinarySearchTreeNode($val);
}
if ($val < $node->val) {
$node->left = $this->recursion($node->left, $val);
}
elseif ($val > $node->val) {
$node->right = $this->recursion($node->right, $val);
}
return $node;
}
/**
* Notes: 查找元素是否存在
* User: think abel
* Date: 2021/1/13 0013
* Time: 23:24
*
* @param $val
*
* @return bool
*/
public function contains($val)
{
return $this->containsRecursion($this->root, $val);
}
/**
* Notes: 递归查找元素是否存在
* User: think abel
* Date: 2021/1/13 0013
* Time: 23:27
*
* @param BinarySearchTreeNode $node
* @param $val
*
* @return bool
*/
private function containsRecursion($node, $val)
{
if ($node == null) {
return false;
}
if ($node->val == $val) {
return true;
}
elseif ($val < $node->val) {
return $this->containsRecursion($node->left, $val);
}
elseif ($val > $node->val) {
return $this->containsRecursion($node->right, $val);
}
}
/**
* Notes: 前序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 10:08
*
*/
public function preOrder()
{
$this->preOrderRecursion($this->root);
}
/**
* Notes: 前序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 10:08
*
* @param $node
*/
private function preOrderRecursion($node)
{
if ($node != null) {
echo $node->val . " ";
$this->preOrderRecursion($node->left);
$this->preOrderRecursion($node->right);
}
}
/**
* Notes: 非递归实现 前序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 11:46
*/
public function preOrderNonRecursion()
{
$stack = array();
array_push($stack, $this->root);
while (count($stack)) {
$cur = array_pop($stack);
echo $cur->val;
if ($cur->right) {
array_push($stack, $cur->right);
}
if ($cur->left) {
array_push($stack, $cur->left);
}
}
}
/**
* Notes: 中序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 11:13
*/
public function inOrder()
{
$this->inOrderRecursion($this->root);
}
/**
* Notes: 中序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 10:08
*
* @param $node
*/
private function inOrderRecursion($node)
{
if ($node != null) {
$this->inOrderRecursion($node->left);
echo $node->val . " ";
$this->inOrderRecursion($node->right);
}
}
/**
* Notes: 后序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 11:13
*/
public function postOrder()
{
$this->postOrderRecursion($this->root);
}
/**
* Notes: 后序遍历
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 10:08
*
* @param $node
*/
private function postOrderRecursion($node)
{
if ($node != null) {
$this->inOrderRecursion($node->left);
$this->inOrderRecursion($node->right);
echo $node->val . " ";
}
}
/**
* Notes:
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 18:08
*/
public function levelOrder()
{
$queue = new LinkedQueue();
$queue->enqueue($this->root);
while ($queue->getSize()) {
$removeNode = $queue->dequeue();
echo $removeNode->val;
if ($removeNode->left) {
$queue->enqueue($removeNode->left);
}
if ($removeNode->right) {
$queue->enqueue($removeNode->right);
}
}
}
/**
* Notes: 输出字符
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 11:14
*
* @return string
*/
public function toString()
{
$str = '';
return $str = $this->generateTreeString($this->root, 0, $str);
}
/**
* Notes: 生成以node为根节点,深度为depth描述二叉树的字符串
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 10:17
*
* @param $node
* @param $depth
* @param $str
*
* @return string
*/
private function generateTreeString($node, $depth, $str)
{
if ($node == null) {
$str .= $this->generateDepthString($depth) . "null" . PHP_EOL;
return $str;
}
$str .= $this->generateDepthString($depth) . $node->val . PHP_EOL;
$str = $this->generateTreeString($node->left, $depth + 1, $str);
$str = $this->generateTreeString($node->right, $depth + 1, $str);
return $str;
}
private function generateDepthString($depth)
{
$str = '';
for ($i = 0; $i < $depth; $i ++) {
$str .= '--';
}
return $str;
}
/**
* Notes: 获取最小值
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 19:18
*
* @return mixed|string
*/
public function getMinimum()
{
if (!$this->getSize()) {
return "The BinarySearchTree Is Empty";
}
return $this->getMinimumRecursion($this->root)->val;
}
/**
* Notes: 递归处理查找
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 19:17
*
* @param BinarySearchTreeNode $node
*
* @return mixed
*/
private function getMinimumRecursion(BinarySearchTreeNode $node)
{
if ($node->left == null) {
return $node;
}
return $this->getMinimumRecursion($node->left);
}
/**
* Notes: 获取最大值
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 19:18
*
* @return mixed|string
*/
public function getMaximum()
{
if (!$this->getSize()) {
return "The BinarySearchTree Is Empty";
}
return $this->getMaximumRecursion($this->root)->val;
}
/**
* Notes: 递归处理查找
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 19:17
*
* @param BinarySearchTreeNode $node
*
* @return mixed
*/
private function getMaximumRecursion(BinarySearchTreeNode $node)
{
if ($node->right == null) {
return $node;
}
return $this->getMaximumRecursion($node->right);
}
/**
* Notes: 移除最小节点
* User: think abel
* Date: 2021/1/14 0014
* Time: 21:27
*
* @return mixed|string
*/
public function removeMin()
{
$ret = $this->getMinimum();
$this->root = $this->removeMinRecursion($this->root);
return $ret;
}
/**
* Notes: 移除最小节点
* User: think abel
* Date: 2021/1/14 0014
* Time: 21:33
*
* @param BinarySearchTreeNode $node
*
* @return BinarySearchTreeNode|null
*/
private function removeMinRecursion(BinarySearchTreeNode $node)
{
// 如果当前节点的有节点为空, 说明没有左子树, 将右子树顶替给左子树
if ($node->left == null) {
$rightNode = $node->right;
$node->right = null;
$this->size --;
return $rightNode;
}
// 继续递归查找最大值, 直到 左子树 为空 停止
$node->left = $this->removeMinRecursion($node->left);
return $node;
}
/**
* Notes: 递归移除最大节点
* User: think abel
* Date: 2021/1/14 0014
* Time: 21:27
*
* @return mixed|string
*/
public function removeMax()
{
$ret = $this->getMaximum();
$this->root = $this->removeMaxRecursion($this->root);
return $ret;
}
/**
* Notes: 递归移除最大节点
* User: think abel
* Date: 2021/1/14 0014
* Time: 21:33
*
* @param BinarySearchTreeNode $node
*
* @return BinarySearchTreeNode|null
*/
private function removeMaxRecursion(BinarySearchTreeNode $node)
{
// 如果当前节点的有节点为空, 说明没有右子树, 将左子树顶替给右子树
if ($node->right == null) {
$leftNode = $node->left;
$node->left = null;
$this->size --;
return $leftNode;
}
// 继续递归查找最大值, 直到 右子树 为空 停止
$node->right = $this->removeMaxRecursion($node->right);
return $node;
}
public function removeArbitraryNode($val)
{
$this->removeArbitraryNodeRecursion($this->root, $val);
}
/**
* Notes: 删除以 node 为根节点的二分搜索树中 值为 val 的节点
* User: think abel
* Date: 2021/1/14 0014
* Time: 22:04
*
* @param BinarySearchTreeNode $node
* @param $val
*
* @return BinarySearchTreeNode 返回删除节点后新的二分搜索树的跟
*/
private function removeArbitraryNodeRecursion($node, $val)
{
if ($node == null) {
return null;
}
if ($val < $node->val) {
$node->left = $this->removeArbitraryNodeRecursion($node->left, $val);
}
elseif ($val > $node->val) {
$node->right = $this->removeArbitraryNodeRecursion($node->right, $val);
}
elseif ($val == $node->val) {
// 待删除节点左子树为空的情况
if ($node->left == null) {
$rightNode = $node->right;
$node->right = null;
$this->size --;
return $rightNode;
}
// 待删除节点右子树为空的情况
if ($node->right == null) {
$leftNode = $node->left;
$node->left = null;
$this->size --;
return $leftNode;
}
/**
* 待删除节点左右子树都不为空的情况
* 找到比待删节点大的最小节点, 就是待删除节点的右子树上最小的节点 (后继)
* 用这个节点顶替待删除的节点位置
*
* @var BinarySearchTreeNode $successor
*/
$successor = $this->getMinimumRecursion($node->right);
$successor->right = $this->removeMinRecursion($node->right);
$successor->left = $node->left;
$node->left = $node->right = null;
return $successor;
/**
* 待删除节点左右子树都不为空的情况
* 找到比待删节点小的最大节点, 就是待删除节点的左子树上最大的节点 (前驱)
* 用这个节点顶替待删除的节点位置
*
* @var BinarySearchTreeNode $predecessor
*/
// $predecessor = $this->getMaximumRecursion($node->left);
// $predecessor->left = $this->removeMaxRecursion($node->left);
// $predecessor->right = $node->right;
//
// $node->left = $node->right = null;
// return $predecessor;
}
return $node;
}
}
/**
* node 节点
* Class Node
*/
class BinarySearchTreeNode
{
public $val;
public $left;
public $right;
public function __construct($val)
{
$this->val = $val;
$this->left = null;
$this->right = null;
}
}
<?php
include 'LinkedList/LinkedList.php';
class LinkedQueue
{
// 链表头部
private $head;
// 链表尾部
private $tail;
// 链表大小
private $size;
/**
* 初始化
* LinkedQueue constructor.
*/
public function __construct()
{
$this->head = null;
$this->tail = null;
$this->size = 0;
}
/**
* Notes: 获取链表大小
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 18:30
*
* @return int
*/
public function getSize()
{
return $this->size;
}
/**
* Notes: 入队
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 18:40
*
* @param $val
*/
public function enqueue($val)
{
if ($this->head == null) {
$this->tail = $this->head = new linkedNode($val, null);
}
else {
$node = new linkedNode($val, null);
$this->tail->next = $node;
$this->tail = $node;
}
$this->size ++;
}
/**
* Notes: 出队
* Author: PhpStorm
* Date: 2021/1/14 0014
* Time: 18:41
*
*/
public function dequeue()
{
if ($this->size == null) {
return "The Queue Is Empty";
}
$node = $this->head;
$this->head = $node->next;
$this->size --;
if ($node->next == null) {
$this->tail = null;
}
return $node->val;
}
}
class linkedNode
{
public $val;
public $next;
public function __construct($val, $next)
{
$this->val = $val;
$this->next = $next;
}
}
<?php
/**
* Created by : PhpStorm
* User: think abel
* Date: 2021/1/11 0011
* Time: 22:12
*/
class LinkedList
{
// 链表虚拟头结点
private $dummyHead;
// 链表的元素数
private $size;
/**
* LinkedList constructor.
*/
public function __construct()
{
$this->dummyHead = new Node(null, null);
$this->size = 0;
}
/**
* Notes: 获取链表中的元素个数
* User: think abel
* Date: 2021/1/11 0011
* Time: 22:28
*
* @return int
*/
public function getSize(): int
{
return $this->size;
}
/**
* Notes: 链表是否为空
* User: think abel
* Date: 2021/1/11 0011
* Time: 22:28
*
* @return bool
*/
public function isEmpty(): bool
{
return $this->size == 0;
}
/**
* Notes: 在链表的第 index 处 添加新的元素 e
* User: think abel
* Date: 2021/1/11 0011
* Time: 22:45
*
* @param $index
* @param $e
*
* @return string
*/
public function add($index, $e)
{
try {
if ($index < 0 || $index > $this->size) {
throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
}
/**
* @var Node $prev 为虚拟头结点, 所以遍历 输入的 index 次 就是前一个节点
*/
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i ++) {
$prev = $prev->next;
}
/**
* 通过 当前传递的 数据 和 上一个节点所指向的下一个节点信息 来创建 当前 节点
* 并把 上一个节点 所指向的下一个节点信息 变为当前创建的节点
*/
$prev->next = new Node($e, $prev->next);
$this->size ++;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 在链表头添加新的元素 e
* User: think abel
* Date: 2021/1/11 0011
* Time: 22:34
*
* @param $e
*/
public function addFirst($e)
{
$this->add(0, $e);
}
/**
* Notes: 向链表末尾添加元素 e
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:23
*/
public function addLast($e)
{
$this->add($this->size, $e);
}
/**
* Notes: 获取第 index 位置的 元素
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:36
*
* @param int $index
*
* @return string
*/
public function get(int $index)
{
try {
if ($index < 0 || $index > $this->size) {
throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
}
/**
* @var Node $cur 当前节点的下一个节点, 因为前面有一个虚拟节点
*/
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i ++) {
$cur = $cur->next;
}
return $cur->e;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 获取第一个元素
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:40
*
* @return string
*/
public function getFirst()
{
return $this->get(0);
}
/**
* Notes: 获取最后一个元素
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:40
*
* @return string
*/
public function getLast()
{
return $this->get($this->size - 1);
}
/**
* Notes: 更新一个元素
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:44
*
* @param int $index
* @param $e
*
* @return string
*/
public function set(int $index, $e)
{
try {
if ($index < 0 || $index > $this->size) {
throw new Exception("修改失败, index require >= 0 and <= " . $this->size);
}
/**
* @var Node $cur 当前节点的下一个节点, 因为前面有一个虚拟节点
*/
$cur = $this->dummyHead->next;
for ($i = 0; $i < $index; $i ++) {
$cur = $cur->next;
}
$cur->e = $e;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 查找元素是否存在
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:49
*
* @param $e
*
* @return bool
*/
public function contains($e): bool
{
/**
* @var Node $cur
*/
$cur = $this->dummyHead->next;
/**
* 不知道遍历多少次, 使用 while 循环
* 如果 当前的元素 == $e 说明 存在, 返回true
* 否则 将 当前的下一个元素 赋值给 当前元素 继续遍历
* 如果 都没有, 说明不存在, 返回 false
*/
while ($cur != null) {
if ($cur->e == $e) {
return true;
}
$cur = $cur->next;
}
return false;
}
/**
* Notes: 删除 index 位置的元素
* User: think abel
* Date: 2021/1/12 0012
* Time: 0:15
*
* @param int $index
*
* @return string|null
*/
public function remove(int $index)
{
try {
if ($index < 0 || $index > $this->size) {
throw new Exception("删除失败, index require >= 0 and <= " . $this->size);
}
/**
* @var Node $prev 当前节点的下一个节点, 因为前面有一个虚拟节点
*/
$prev = $this->dummyHead;
for ($i = 0; $i < $index; $i ++) {
$prev = $prev->next;
}
/**
* @var Node $removeNode
*/
$removeNode = $prev->next;
$prev->next = $removeNode->next;
$removeElement = $removeNode->e;
$removeNode = null;
$this->size --;
return $removeElement . PHP_EOL;
}
catch (Exception $e) {
return $e->getMessage();
}
}
/**
* Notes: 删除第一个元素
* User: think abel
* Date: 2021/1/12 0012
* Time: 0:16
*
* @return string|null
*/
public function removeFirst()
{
return $this->remove(0);
}
/**
* Notes: 删除最后一个元素
* User: think abel
* Date: 2021/1/12 0012
* Time: 0:16
*
* @return string|null
*/
public function removeLast()
{
return $this->remove($this->size - 1);
}
/**
* Notes: 打印输出
* User: think abel
* Date: 2021/1/11 0011
* Time: 23:52
*
* @return string
*/
public function toString(): string
{
/**
* @var Node $cur
*/
$cur = $this->dummyHead->next;
$str = '';
for ($cur; $cur != null; $cur = $cur->next) {
$str .= $cur->e . '-->';
}
$str .= 'NULL';
return $str . PHP_EOL;
}
}
/**
* 创建节点类
* Class Node
*/
class Node
{
// 节点元素
public $e;
// 指向下一个节点信息
public $next;
/**
* Node constructor.
*
* @param null $e
* @param null $next
*/
public function __construct($e = null, $next = null)
{
$this->e = $e;
$this->next = $next;
}
}
<?php
include 'BinarySearchTree/BinarySearchTree.php';
$binary = new BinarySearchTree();
$binary->add(28);
$binary->add(20);
$binary->add(15);
$binary->add(22);
$binary->add(36);
$binary->add(30);
$binary->add(42);
print_r($binary);
echo PHP_EOL;
var_dump($binary->contains(5));
print_r($binary->toString());
echo $binary->preOrder();
echo $binary->inOrder();
echo $binary->postOrder();
echo $binary->preOrderNonRecursion();
echo $binary->getMinimum();
echo $binary->getMaximum();
echo $binary->removeMin();
echo PHP_EOL;
echo $binary->inOrder();
echo PHP_EOL;
echo $binary->removeMax();
echo PHP_EOL;
echo $binary->inOrder();
echo PHP_EOL;
echo $binary->removeArbitraryNode(20);
echo PHP_EOL;
echo $binary->inOrder();