二叉查找树

class Node
{
    public $value;
    public $left;
    public $right;

    public function __construct(int $value, Node $left = null, Node $right = null)
    {
        $this->value = $value;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * Class BinaryTree
 * 默认树中不存在重复元素
 */
class BinaryTree
{

    public $root;

    private $isDelete;

    public function __construct(Node $root)
    {
        $this->root = $root;
    }

    public function insert(int $value)
    {
        $node = new Node($value);

        $compareNode = $this->root;

        while (true) {
            if ($this->compare($node, $compareNode) >= 0) {
                if ($compareNode->right === null) {
                    $compareNode->right = $node;
                    return true;
                }
                $compareNode = $compareNode->right;
            } else {
                if ($compareNode->left === null) {
                    $compareNode->left = $node;
                    return true;
                }
                $compareNode = $compareNode->left;
            }
        }

        return true;

    }

    public function delete(int $value)
    {
        $this->isDelete = false;
        $this->_delete($value, $this->root);
        return $this->isDelete;
    }

    protected function _delete($value, &$compareNode)
    {
        if ($compareNode === null) {
            return null;
        }

        if ($this->compare($value, $compareNode) == 0) {
            if ($compareNode->left !== null && $compareNode->right !== null) {
                $maxLeft = $this->max($compareNode->left);
                $right = $compareNode->right;
                $left = $compareNode->left;
                $this->_delete($maxLeft->value, $left);
                $compareNode = $maxLeft;
                $compareNode->left = $left;
                $compareNode->right = $right;
            } else {
                // 没有子节点或只有一个字节点
                $compareNode = $compareNode->left !== null ? $compareNode->left : $compareNode->right;
            }

            $this->isDelete = true;

        } elseif ($this->compare($value, $compareNode) > 0) {
            $this->_delete($value, $compareNode->right);
        } else {
            $this->_delete($value, $compareNode->left);
        }

        return null;
    }

    public function min(Node $root = null)
    {
        if ($root === null) {
            $root = $this->root;
        }

        while (true) {
            if ($root->left === null) {
                return $root;
            }
            $root = $root->left;
        }

        return null;
    }

    public function max(Node $root = null)
    {
        if ($root === null) {
            $root = $this->root;
        }

        while (true) {
            if ($root->right === null) {
                return $root;
            }
            $root = $root->right;
        }

        return null;
    }

    public function search(int $value)
    {
        $compareNode = $this->root;

        while (true) {

            if ($this->compare($value, $compareNode) == 0) {
                return $compareNode;
            } elseif ($this->compare($value, $compareNode) > 0) {
                if ($compareNode->right === null) {
                    return null;
                }
                $compareNode = $compareNode->right;
            } else {
                if ($compareNode->left === null) {
                    return null;
                }
                $compareNode = $compareNode->left;
            }
        }

        return null;
    }

    protected function compare($node, $compareNode)
    {
        if ($node instanceof Node) {
            $node = $node->value;
        }

        if ($compareNode instanceof Node) {
            $compareNode = $compareNode->value;
        }

        if ($node > $compareNode) {
            return 1;
        } elseif ($node == $compareNode) {
            return 0;
        } else {
            return -1;
        }
    }

    public function show()
    {
        print_r($this->root);
    }
}