<?php

class Node
{
    public $data;

    /**
     * @var Node
     */
    public $left;

    /**
     * @var Node
     */
    public $right;
}

// 最终返回的是根节点
function insert($val,  ? Node $node = null) : Node
{
    if (!$node) {
        $node = new Node;
        $node->data = $val;
        $node->left = $node->right = null;
    }
    if ($val < $node->data) {
        $node->left = insert($val, $node->left);
    }
    if ($val > $node->data) {
        $node->right = insert($val, $node->right);
    }

    return $node;
}

function find($val,  ? Node $node = null) :  ? Node
{
    if (!$node) {
        return null;
    }
    if ($val == $node->data) {
        return $node;
    }
    if ($val > $node->data) {
        return find($val, $node->right);
    }
    if ($val < $node->data) {
        return find($val, $node->left);
    }
}

function findMin( ? Node $node = null) :  ? Node
{
    if (!$node->left) {
        return $node;
    }
    if ($node->left) {
        return findMin($node->left);
    }
}

function findMax( ? Node $node = null) :  ? Node
{
    if (!$node->right) {
        return $node;
    }
    if ($node->right) {
        return findMax($node->right);
    }
}

function delete($val,  ? Node $node)
{
    $findNode = find($val, $node);
    if (!$findNode) {
        echo '未找到';
        return;
    } else if (!$findNode->left && !$findNode->right) {
        // 叶子节点可以直接删除
        $findNode->data = null;
        unset($findNode); // php中unset只是释放了局部变量
    } else if (!$findNode->left && $findNode->right) {
        // 只有一个右子树,则直接替换当前节点
        $tmp = $findNode->right;
        $findNode->data = $tmp->data;
        $findNode->left = $tmp->left;
        $findNode->right = $tmp->right;
    } else if ($findNode->left && !$findNode->right) {
        // 只有一个左子树,则直接替换当前节点
        $tmp = $findNode->left;
        $findNode->data = $tmp->data;
        $findNode->left = $tmp->left;
        $findNode->right = $tmp->right;
    } else {
        // 两个子树,可使用左子树最大值或者右子树最小值替换,并删除这个最值元素,而且这个最值一定是叶子节点
        $right = findMin($findNode->right);
        $findNode->data = $right->data;
        delete($right->data, $findNode->right);
    }
}

$root = insert(1);
insert(2, $root);
insert(4, $root);
insert(10, $root);
insert(3, $root);
insert(7, $root);
insert(-100, $root);
insert(-9, $root);
print_r(json_decode(json_encode($root), true));

// $res = find(10, $root);
// var_dump($res);

// $res = findMin($root);
// var_dump($res);

// $res = findMax($root);
delete(-100, $root);
print_r(json_decode(json_encode($root), true));

最后更新于 2021-07-15 08:14:57 并被添加「」标签，已有 667 位童鞋阅读过。