数据结构之PHP二分搜索树

thinkabel 的个人博客 / 116 / 0 / 创建于 3年前 / 更新于 3年前

前面我们学习了数组，栈，链表，队列。他们都是属于线性结构，区别在于是顺序存储还是无序存储。在学习链表的时候，我们知道链表里存储的是两个元素，一个是当前元素值，一个是写一个节点的元素信息。今天我们学习的二分搜索树也是这种类型，不过是三个元素。

学习二分搜索树，首先我们来看下二分树。既然称为树，顾名思义，就是来源于我们生活中的树，一支分多支，无限延展下去的结构。在数据结构中，树结构和现实生活中的树是反着的。把树根放在顶部，叶子在下，类似于这样。

（树结构示意图）

一、二叉树

什么是二叉树，上面的结构就是一个二叉树，一个节点连着两个节点。二叉树具有唯一的根节点，每个节点都有两个子节点。换句话也就是说，二叉树每个节点最多有两个子节点，二叉树每个节点最多有一个父节点。

在树结构中，我们称顶级节点为根节点，下面的节点都为子节点，在子节点的左子树和右子树都为空的时候，称之为叶子节点。

（二叉树示意图）

我们看到, 二叉树不一定是全”满”的, 就算一个节点也是二叉树, 比如说现在只有根节点, 这个时候也是一个二叉树, 空树也是一个二叉树。二叉树具有天然的递归性, 为什么这样说呢, 我们看, 孩子又是一个新的二叉树, 这就体现了递归。

二、二分搜索树（Binary Search Tree）

二分搜索树也是一种二叉树, 只不过比二叉树要多一些规则:

二分搜索树每个节点的值:
大于当前节点左子树所有节点的值
小于当前节点右子树所有节点的值
每一个子树也是一个二分搜索树

（二分搜索树示意图）

1. 添加元素

我们根据这个基本规则进行添加元素。从根节点出发，如果添加的元素大于根节点元素值，就需要将此元素放在根节点的右子树上，直到待插入节点为null，就把这个元素插入该位置。看下流程图

（二分搜索树添加元素示意图）

我们认真思考一下，如果我们想插入两个66 或者 8 怎么办，这个时候，元素应该是放在左子树还是右子树呢？其实插入左子树还是右子树，这个要根据实际需求来决定放在哪里。如果我们想包含重复元素的话，我们就改下定义：**左子树小于等于节点或者右子树大于等于节点。**

2. 查询和更改元素

我们之前在学习数组, 链表时都有查找指定位置的情况。但是在树结构中，没有位置可言，我们可以查询树结构中是否包含待查元素。同添加元素一样，我们可以通过递归的方式，进行查找和更改。

3. 遍历元素

树的遍历元素和线性结构遍历是不同的，线性结构是从头到尾，对于树来说遍历分为以下几种情况：

前序遍历
中序遍历
后序遍历
层序遍历

在上面的遍历中，前序，中序，后序都是为深度算法，而层序遍历则是广度优先的算法。

3.1 前序遍历

前序遍历主要思想就是，先访问节点元素，然后在对左右子树进行前序遍历操作。我们看下图：

（前序遍历示意图）

流程顺序：

先访问节点元素 28，然后在对 28 的左子树进行遍历
然后访问节点元素 20，然后对 20 的左子树进行遍历
访问节点元素 13，然后对 13 的左子树进行遍历，发现 13 左右子树都为空。这时访问节点右子树 22，发现 22 左右字数都为空。所以遍历遍历结果为 20-13-22
此时返回节点元素 28，对 28的右子树进行遍历, 访问节点元素 36，然后对 36 的左子树进行遍历
访问节点元素 30，然后对 30 的左子树进行遍历，发现 30 左右子树都为空。这时访问节点右子树 42，发现 42 左右字数都为空。所以遍历遍历结果为 36-30-42

*程序的结果为: 28-20-13-22-36-30-42
*

3.2 中序遍历

中序遍历主要思想就是，把访问根节点元素的操作放在中间，先对左子树进行遍历, 然后访问其节点元素, 最后遍历右子树。我们看下图：

（中序遍历示意图）

流程顺序：

先访问左子树
左子树的根节点为 20, 这时在对 20 的左子树进行遍历, 访问 13 , 发现13为叶子节点, 在返回根节点 20 , 最后访问 20 的右子树 22. 结果为 13-20-22
在访问根节点元素 , 结果为28
在访问右子树
右子树的根节点为 36, 在对 36 的左子树进行遍历, 访问 30, 发现30为叶子节点, 在返回根节点 36 , 最后访问 36 的右子树 42. 结果为 30-36-42

程序的结果为: 13-20-22-28-30-36-42

3.3 后序遍历

有了前面两个遍历的基础, 后序遍历会比较简单了. 主要思想就是，把访问根节点元素的操作放在最后，先对左子树进行遍历, 然后遍历右子树。最后其节点元素

程序的结果为: 13-22-20-30-42-36-28

3.4 层序遍历

层序遍历和前面的不同, 层序遍历是广度优先的算法. 也就是一层层的进行访问. 某一层深度访问完后继续往下访问.

这里我们需要借助队列进行实现, 主要的思想就是, 让每一层级的节点入队, 这样出队的元素就是左右节点的元素.

（层序遍历示意图）

我们要先出根节点, 先将根节点入队. 然后需要遍历第二层, 先将左子树入队, 在入队右子树. 最后就是下图所示:

（层序遍历示意图）

4. 删除元素

删除元素时最难的一个操作, 我们先从简单的入手, 删除最大值和最小值。最大值我们知道，在二分搜索树的右子节点，就是最大值；最小值就是左子树的叶子节点。

（最大最小示意图）

4.1 删除最小节点

     删除就是删除左子树的最小点, 左子树分为两种情况：

若是叶子节点，直接删除该元素即可；
若无左子树节点，右子树节点顶替待删除节点。

（删除叶子节点 13 示意图）

（删除叶子节点20, 无左子树示意图）

4.2 删除最大节点

     删除就是删除右子树的最大点, 右子树分为两种情况：

若是叶子节点，直接删除该元素即可；
若无右子树节点，左子树节点顶替待删除节点。

这里就不画图了

4.3 删除任意节点

 删除任意节点, 相对来讲会麻烦一点,  这里需要一个方法

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.

math.oxford.emory.edu/site/cs171/hi...

意思就是说, 将要删除的节点与其后继节点交换. 这里 后继指的是当前节点右子树中最小的节点进行替换当前删除节点. 这种情况来处理左右子树都有数据的情况. 相反我们也可以使用 前序, 前序指的是当前节点左子树中最大的节点进行替换。这两种都可以满足。

此时，我们需要删除 36 这个节点，我们使用后继的方式看下。

（后继示意图）

根据定义，36的右子树中最小的节点进行替换，右子树只有一个节点，那也就是 42，所以使用 42 替换 36。

（后继示意图）

前序根据定一样是一样的。就不画图了。大家可以动手理解下。
三、程序实现

BinarySearchTree.php

<?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;
    }

}

LinkedQueue.php

<?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;
    }
}

LinkedList.php

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

    }

}

index.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();