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

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;
            }
        }
    }
    
    // ...其余代码

}

喜欢 (0)赏

[搞代码]

分享 (0)