PHP 二叉搜索树的查找、插入和删除

继续上一篇的内容，这次是在二叉树的基础上添加二叉搜索树的查找、插入和删除方法。

<?php

/**
 * 节点类
 */
class TreeNode
{

    private ?self $left = null;

    private ?self $right = null;

    private int $value;

    private ?self $parent;

    public function __construct(int $value, self $parent = null)
    {
        $this->value = $value;
        $this->parent = $parent;
    }

    /**
     * @return int
     */
    public function getValue(): int
    {
        return $this->value;
    }

    /**
     * @return self|null
     */
    public function getLeft(): ?self
    {
        return $this->left;
    }

    /**
     * @return self|null
     */
    public function getRight(): ?self
    {
        return $this->right;
    }

    /**
     * @param self|null $left
     */
    public function setLeft(?self $left): void
    {
        $this->left = $left;
    }

    /**
     * @param self|null $right
     */
    public function setRight(?self $right): void
    {
        $this->right = $right;
    }

    /**
     * @return self|null
     */
    public function getParent(): ?self
    {
        return $this->parent;
    }

    /**
     * @param self $parent
     */
    public function setParent(self $parent): void
    {
        $this->parent = $parent;
    }

    /**
     * @param int $value
     */
    public function setValue(int $value): void
    {
        $this->value = $value;
    }
}

/**
 * 树
 */
class Tree
{

    protected ?TreeNode $root;

    public function __construct(array $dataSet1, array $dataSet2, string $method)
    {
        switch ($method) {
            case 'pre': // 根据前序和中序遍历的结果构建
                $this->root = $this->makeFromPreOrderAndInOrder($dataSet1, $dataSet2);
                break;
            case 'post':// 根据后序和中序遍历的结果构建
                $this->root = $this->makeFromPostOrderAndInOrder($dataSet1, $dataSet2);
                break;
            default:
                throw new InvalidArgumentException;
        }
    }

    /**
     * 从前序遍历和中序遍历的结果构建原来的树
     * 解法：先序中的首元素a 必为该二叉树的根结点，在中序序列里a之前的元素一定是a的左子树部分，a之后的元素一定为a的右子树部分。
     *
     * @param int[] $pre
     * @param int[] $in
     * @param TreeNode|null $parent
     * @return TreeNode
     */
    public function makeFromPreOrderAndInOrder(array $pre, array $in, TreeNode $parent = null): TreeNode
    {
        $currentRoot = $pre[0]; // 前序遍历的首元素肯定是根节点
        $currentRootPos = array_search($currentRoot, $in, true);
        $left = array_slice($in, 0, $currentRootPos);
        $right = array_slice($in, $currentRootPos + 1);
        $preLeft = array_slice($pre, 1, $currentRootPos);
        $preRight = array_slice($pre, $currentRootPos + 1);
        $currentRoot = new TreeNode($currentRoot, $parent);

        if ($left) {
            $currentRoot->setLeft($this->makeFromPreOrderAndInOrder($preLeft, $left, $currentRoot));
        }

        if ($right) {
            $currentRoot->setRight($this->makeFromPreOrderAndInOrder($preRight, $right, $currentRoot));
        }

        return $currentRoot;
    }

    /**
     * 从后序遍历和中序遍历的结果重新构建树
     * 思路同上，只是反了过来
     *
     * @param array $post
     * @param array $in
     * @param TreeNode|null $parent
     * @return TreeNode
     */
    public function makeFromPostOrderAndInOrder(array $post, array $in, TreeNode $parent = null): TreeNode
    {
        $currentRoot = $post[count($post) - 1]; // 后序遍历的最后一个元素是根节点
        $currentRootPos = array_search($currentRoot, $in, true);
        $left = array_slice($in, 0, $currentRootPos);
        $right = array_slice($in, $currentRootPos + 1);
        $postLeft = array_slice($post, 0, $currentRootPos);
        $postRight = array_slice($post, $currentRootPos, -1);

        $currentRoot = new TreeNode($currentRoot, $parent);

        if ($left) {
            $currentRoot->setLeft($this->makeFromPostOrderAndInOrder($postLeft, $left, $currentRoot));
        }

        if ($right) {
            $currentRoot->setRight($this->makeFromPostOrderAndInOrder($postRight, $right, $currentRoot));
        }

        return $currentRoot;
    }

    /**
     * 前序遍历
     *
     * @param TreeNode|null $treeNode
     * @return array
     */
    public function preOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        $ret[] = $treeNode->getValue(); // 节点马上输出

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->preOrderTraversal($treeNode->getLeft()));
        }
        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->preOrderTraversal($treeNode->getRight()));
        }

        return $ret;
    }

    /**
     * 中序遍历
     *
     * @param TreeNode $treeNode
     * @return array
     */
    public function inOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->inOrderTraversal($treeNode->getLeft()));
        }

        $ret[] = $treeNode->getValue(); //只有当遍历完左节点后才输出

        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->inOrderTraversal($treeNode->getRight()));
        }

        return $ret;
    }

    /**
     * 后序遍历
     *
     * @param TreeNode|null $treeNode
     * @return array
     */
    public function postOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->postOrderTraversal($treeNode->getLeft()));
        }

        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->postOrderTraversal($treeNode->getRight()));
        }

        $ret[] = $treeNode->getValue(); // 遍历完左右节点后才输出

        return $ret;
    }
}

class BinSearchTree extends Tree
{

    /**
     * 插入
     *
     * @param int $value
     * @param TreeNode|null $treeNode
     */
    public function insert(int $value, TreeNode $treeNode = null)
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }
        if ($treeNode->getValue() > $value) {
            if ($treeNode->getLeft()) {
                $this->insert($value, $treeNode->getLeft());
            } else {
                $treeNode->setLeft(new TreeNode($value,$treeNode));
            }
        } else {
            if ($treeNode->getRight()) {
                $this->insert($value, $treeNode->getRight());
            } else {
                $treeNode->setRight(new TreeNode($value,$treeNode));
            }
        }
    }

    /**
     * 搜索
     *
     * @param int $value
     * @param TreeNode|null $treeNode
     * @return TreeNode|null
     */
    public function search(int $value, TreeNode $treeNode = null): ?TreeNode
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }
        $nodeValue = $treeNode->getValue();
        if ($nodeValue === $value) {
            return $treeNode;
        }
        if ($nodeValue > $value && !is_null($treeNode->getLeft())) { // 在左子树继续找
            return $this->search($value, $treeNode->getLeft());
        }

        if ($nodeValue < $value && !is_null($treeNode->getRight())) { // 在右子树继续找
            return $this->search($value, $treeNode->getRight());
        }

        return null; // 没有找到
    }

    public function delete(int $value, TreeNode $treeNode=null): bool
    {
        $find=$this->search($value);

        if(is_null($find)){
            return false;
        }

        $findValue=$find->getValue();
        $parent=$find->getParent();
        $parentValue=is_null($parent)?null:$parent->getValue();

        // 该节点没有子节点，直接删除，即在父节点将该节点设为 null
        if(is_null($find->getLeft()) && is_null($find->getRight())){
            if(is_null($parent)){// 只有一个根节点
                $this->root=null;
            }else{
                if($parentValue>$findValue){ // 父节点值大于子节点，即子节点在父节点左子树上
                    $parent->setLeft(null);
                }else{
                    $parent->setRight(null);
                }
            }

        }

        // 只有左节点，把父节点指向左节点
        if(!is_null($find->getLeft()) && is_null($find->getRight())){
            if(is_null($parent)){ // 要删除的节点是根节点，直接把树的根节点指向左子树
                $this->root=$find->getLeft();
            }else{
                if($parentValue>$findValue){
                    $parent->setLeft($find->getLeft());
                }else{
                    $parent->setRight($find->getLeft());
                }
            }
        }

        //  只有右节点，同上处理
        if(is_null($find->getLeft()) && !is_null($find->getRight())){
            if(is_null($parent)){
                $this->root=$find->getRight();
            }else{
                if($parentValue>$findValue){
                    $parent->setLeft($find->getRight());
                }else{
                    $parent->setRight($find->getRight());
                }
            }

        }

        // 有左右节点，找到右子树最左节点，即最小元素（中序遍历第一个元素），进行替换删除
        // 这样做是因为对整棵树影响最小？
        if(!is_null($find->getLeft()) && !is_null($find->getRight())){
            $inOrderResult=$this->inOrderTraversal($find->getRight());
            $min=$this->search($inOrderResult[0],$find->getRight());
            $minValue=$min->getValue();
            $this->delete($minValue); // 删除右子树最小元素
            $find->setValue($minValue); // 要删除的元素替换为右子树最小元素
        }

        return true;
    }
}


$pre = [8, 3, 1, 6, 4, 7, 10, 14, 13];
$in = [1, 3, 4, 6, 7, 8, 10, 13, 14];

$tree = new BinSearchTree($pre, $in, 'pre');

$tree->insert(2);

$n2=$tree->search(2);
echo $n2->getParent()->getValue(),PHP_EOL;

$tree->delete(8);

var_export($tree->preOrderTraversal());