老死机带你用 PHP 实现数据结构之二叉树

各位老哥如果刷Leetcode 的二叉树题目可以参考我以前总结了很多二叉树的题型 :kissing_heart::博客：Leetcode 二叉树题目集合 (看完这个面试不会做二叉树题,辣条给你！！...

提出一个疑问

第一次接触和学习二叉树，本着不懂就问的学习精神，在此提出一个疑问。

我今天将代码下载下来研究学习了一下，但是在我本地跑的测试结果与我理解二叉树后预期的结果有差异，我认为可能是测试代码中一小段代码的逻辑有点问题导致的，还望大佬解惑，具体情况如下：

// 以下为 test.php 中代码片段
$tree = new BinaryTree(new IntComparator());
$to_insert = [100, 20, 1, 34, 230, 78, 349, 289, 89, 45, 30, 8,25,24,26,23];
foreach ($to_insert as $item) {
    $tree->insert($item);
}
// $tree->delete(20);
$result = $tree->toArray($tree->root_node);
echo json_encode($result);

在原测试代码的基础上增加了将 $to_insert 变量增加了四个元素 25,24,26,23 。
对 $result = $tree->toArray($tree->root_node); 的说明：
为便于测试，将私有属性 private $root_node = null; 改为公有属性 public $root_node = null;
在 BinaryTree 类中添加了一个方法 toArray($node)

public function toArray($node)
    {
        if($node && ($node->getLeftNode()||$node->getRightNode())){
            return [
                $node->getValue() => [
                    $this->toArray($node->getLeftNode()),
                    $this->toArray($node->getRightNode())
                ]
            ];
        }elseif($node){
            return $node->getValue();
        }
        return null;
    }

运行输出结果：

然后将 // $tree->delete(20); 注释打开，删除 20
运行输出结果：

但是该结果与预期结果不符。

该子树无故消失，我预期的结果应该如下：

经过分析代码后发现：
delete 方法中，当左右子树都存在时, $right_first_node->setLeftNode(null); 左子树会被设为 null ，导致问题出现。

if ($t_node !== $right_first_node) {
    $t_node->setRightNode($right_first_node);
    $right_first_node->setParentNode($t_node);
    $right_first_node->setLeftNode(null);
} else {
    //do nothing
}

我这边根据分析后的结果对该情况下的代码进行了如下调整：

//two children  exist
//look for min node of right subtree
$t_node = $right_first_node = $node->getRightNode();
while (true) {
    if (!$t_node->getLeftNode()) {
        if ($t_node !== $right_first_node) {
            $t_parent_node = $t_node->getParentNode();
            $t_parent_node->setLeftNode(null);
        } else {
            //do nothing
        }
        $t_node->setLeftNode($node->getLeftNode());
        if ($parent_node) {
            if ($node === $parent_node->getLeftNode()) {
                $parent_node->setLeftNode($t_node);
            } else {
                $parent_node->setRightNode($t_node);
            }
            $t_node->setParentNode($parent_node);
        } else {
            $this->root_node = $t_node;
            $t_node->setParentNode(null);
        }

        if ($t_node->getRightNode()) {
            if ($t_node !== $right_first_node) {
                $t_node->getParentNode()->setLeftNode($t_node->getRightNode());
                $t_node->getRightNode()->setParentNode($t_node->getParentNode());
            } else {
                //do nothing
            }
        } else {
            //do nothing
        }

        if ($t_node !== $right_first_node) {
            $t_node->setRightNode($right_first_node);
            $right_first_node->setParentNode($t_node);
            //$right_first_node->setLeftNode(null);
        } else {
            //do nothing
        }
        return;
    } else {
        $t_node = $t_node->getLeftNode();
    }
}

再次运行后结果如下：

最终结果符合我的预期，请问这样是否正确？

大二教的数据结构，期末考试前还知道基本的数据结构，考试后就全忘了 :joy: :joy:

老司机 :bus:搞了二叉树都死机了

求讲解红黑树的增删改查😂

老死机 还玩二叉树

你给的定义是BST