4.4 数据结构（PHP实现） -- 二分搜索树的结点删除

码农天地 - 2020-11-03 00:01:24

1. 删除逻辑删除的结点不存在左儿子：

删除的结点不存在右儿子：

删除的结点存在左儿子和右儿子：删除的结点的左边所有值都会比该结点小，所以只要在其中拿出最大的一个值替换成该节点即可

2. 代码

<?php
/**
 * content: 二叉树的二分搜索树的实现
 * auth: yujiaming
 * create: 2020-10-25
 */
namespace TreeBundle;

use ArrayBundle\BaseArray;
use QueueBundle\BaseQueue;
use StackBundle\BaseStack;

class BaseBinaryTree
{

    /**
     * 删除某个结点
     * @param $value
     */
    public function deleteNode($value)
    {
        $node = $this->rootNode;
        $parentNode = null;

        while (!is_null($node)) {
            if (bccomp($node->getValue(), $value) > 0) {
                $parentNode = $node;
                $node = $node->getLeftChild();
            } elseif (bccomp($node->getValue(), $value) < 0) {
                $parentNode = $node;
                $node = $node->getRightChild();
            } else {
                // 如果不存在右儿子，则左儿子直接挂到父节点下面即可
                if (is_null($node->getRightChild())) {
                    // 将新节点接到父节点下，这里要判断是父节点的左儿子还是右儿子
                    if (!is_null($parentNode->getLeftChild()) && bccomp($parentNode->getLeftChild()->getValue(), $node->getValue()) == 0) {
                        $parentNode->setLeftChild($node->getLeftChild());
                    } elseif (!is_null($parentNode->getRightChild()) && bccomp($parentNode->getRightChild()->getValue(), $node->getValue()) == 0) {
                        $parentNode->setRightChild($node->getLeftChild());
                    }
                    return;
                }

                // 如果不存在左儿子，则右儿子直接挂到父节点下面即可
                if (is_null($node->getLeftChild())) {
                    // 将新节点接到父节点下，这里要判断是父节点的左儿子还是右儿子
                    if (!is_null($parentNode->getLeftChild()) && bccomp($parentNode->getLeftChild()->getValue(), $node->getValue()) == 0) {
                        $parentNode->setLeftChild($node->getRightChild());
                    } elseif (!is_null($parentNode->getRightChild()) && bccomp($parentNode->getRightChild()->getValue(), $node->getValue()) == 0) {
                        $parentNode->setRightChild($node->getRightChild());
                    }
                    return;
                }

                // 如果左儿子和右儿子都存在，则获取右儿子里最小的结点来替代该结点

                // 定义当前结点左儿子的最大结点的父节点
                $leftMaxNodeParent = $node;
                // 定义当前结点左儿子的最大结点
                $leftMaxNode = $leftMaxNodeParent->getLeftChild();
                // 遍历
                while (!is_null($leftMaxNode) && !is_null($leftMaxNode->getRightChild())) {
                    $leftMaxNodeParent = $leftMaxNode;
                    $leftMaxNode = $leftMaxNode->getRightChild();
                }
                // 将当前结点左儿子的最大结点的父节点的右儿子设置为null
                $leftMaxNodeParent->setRightChild(null);
                // 将当前结点左儿子的最大结点的左儿子和右儿子设置为该结点的左儿子和右儿子
                $leftMaxNode->setLeftChild($node->getLeftChild());
                $leftMaxNode->setRightChild($node->getRightChild());

                // 将新节点接到父节点下，这里要判断是父节点的左儿子还是右儿子
                if (!is_null($parentNode->getLeftChild()) && bccomp($parentNode->getLeftChild()->getValue(), $node->getValue()) == 0) {
                    $parentNode->setLeftChild($leftMaxNode);
                } elseif (!is_null($parentNode->getRightChild()) && bccomp($parentNode->getRightChild()->getValue(), $node->getValue()) == 0) {
                    $parentNode->setRightChild($leftMaxNode);
                }
                return;
            }
        }
    }
    
    // ...其他代码

}

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。