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

目的

根据我在这段时间的观察,很多人不懂一些基本的数据结构,所以今天在这里,我不准备讲Laravel的相关知识,而是来一点儿数据结构知识的科普:二叉树。代码我已经上传到了码云php-tree,希望大家能够下载下来。下面的讲解都是根据代码来的,仔细阅读。代码可能不是那么容易理解,没关系,我在这篇博文的后面会给大家仔细的讲解。

二叉树的起源

关于到底是谁发明了二叉树,已经无从得知了,反正历史十分悠久,之所以二叉树会存在,是为了解决线性搜索耗费时间的问题,但是因为二叉树的极端情况(有可能演变为链表),所以二叉树在生产环境下基本没有使用,但是二叉树衍生除了许多其它的变种,比如 红黑树(Red-Black-Tree), 红黑树的应用无处不在(操作系统,标准库等等),但是要想理解这些变种,基本的二叉树原理,你是必须要知道的。

二叉树的定义

二叉树的定义很简单,如下:

  1. 每一个节点,有且最多只有2个子节点。
  2. 每一个节点的左子节点的值小于当前节点的值,当前节点的值小于右子节点的值。

定义很简单,没错,就是这么简单,希望大家记住。

二叉树的操作

今天我要讲的是二叉树的插入和删除操作,因为这是它的核心操作,请大家仔细理解。

代码结构

博文的开头,我已经给出了代码的地址,下载是必须的,代码结构如下所示:

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

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

每个文件的作用我已经给大家标出来了,这里我还要给大家简要的介绍一下没各类的基本属性。

二叉树的每一个节点都是Node类,这个类很简单,如下:

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

各个属性的含义,我都给大家标出来了,就不再说了,NodeComparator是一个接口,所有的结点比较器(如果比较两个结点的大小)都应该实现NodeComparator结构,NodeComparator接口定义如下:

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

最后是BinaryTree类了,这个类有点儿复杂,其它的操作在本篇博文的后面,我们在这里只看它的基础属性:

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

关于如何实现自己的结点比较器,我在test.php文件中有给大家演示,下面我贴出来:

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

上面简要的介绍了基本类的一些作用,下面开始深入二叉树的插入和删除操作。

二叉树的插入

在阅读下面的代码前,我希望,你已经理解了二叉树的定义,废话不多说。

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

因为插入操作不是那么复杂,所以这里直接贴出了所有的代码,
Node::create方法创建了一个Node类的对象,首先判断根节点root_node是否为空,如果为空的话,那么直接设置根节点就可以了,如果不为空的话,那么就需要从根节点遍历整棵树,这里提醒大家,记住二叉树的定义,这里所有的一切都是以这个为依据,BinaryTree的compare方法用于比较2个Node节点的大小,实现如下:

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

这个很简单,不多说,compare方法比较当前结点node和将要插入的结点new_node的大小值,如果node的值大于new_node的值,也就是说new_node会插入到node的左子树中,此时我们判断node是否存在左子节点,判断方法就是node->getLeftNode方法,如果存在的话,我们直接把左子节点赋值给node变量,这样下次迭代就是以左子节点为判断依据,也就是说下次迭代的时候,node就是当前迭代node的左子节点,如果不存在的话,那么也就是说new_node直接插入作为node节点的左子树。如果当前节点小于new_node的值的话,也就是说new_node会插入到当前迭代节点的右子树中,这里首先判断,当前节点的右子节点是否存在,如果不存在的话,new_node节点直接作为它的当前node节点的右子节点即可,如果存在的话,那么我们就需要继续迭代整棵二叉树,只不过下次迭代的node节点为当前node节点的右子节点,如此反复,直到找到满足条件的节点。

二叉树的删除

不管是二叉树,还是它的衍生树,删除操作都是极其麻烦的,因为情况实在是太多了,下面我们一一分析:

删除操作位于BinaryTree的delete方法中,如下:

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

在分析代码之前,我先给大家分析删除的所有情况:

A. 二叉树为空,那么删除操作,就直接执行完毕了

B. 被删除的节点没有子节点,也就是下图所展示的情况

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

如果一个节点没有子节点,那么这个节点要么是根节点,要么是叶子节点,分别如上图所示的情况1和情况2,这种情况很简单。

C.被删除的节点有且只有一个子节点,此时的所有情况如下所示

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

  1. 情况3:被删除的节点是根节点,并且它的左子节点是存在的。
  2. 情况4:被删除节点是根节点,并且它的右子节点是存在。
  3. 情况5:被删除结点不是根节点,并且它的左子节点是存在的,同时被删除节点是它父节点的右子节点。
  4. 情况6:被删除结点不是根节点,并且它的左子节点是存在的,同时被删除节点是它父节点的左子节点。
  5. 情况7:被删除结点不是根节点,并且它的右子节点是存在的,同时被删除节点是它父节点的左子节点。
  6. 情况8:被删除结点不是根节点,并且它的右子节点是存在的,同时被删除节点是它父节点的右子节点。

D:被删除结点有2个子节点,此时,情况有点儿复杂,如下:

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

  1. 情况9:被删除节点是根节点,并且被删除节点的右子节点没有左子节点。
  2. 情况10:被删除节点不是根节点,并且被删除节点是父节点的右子节点。
  3. 情况11:被删除节点不是根节点,并且被删除节点是父节点的左子节点。
  4. 情况12:被删除节点不是根节点,并且被删除节点是父节点的右子节点,并且被删除节点的右子节点有左子节点。
  5. 情况13:被删除节点不是根节点,并且被删除节点是父节点的左子节点,并且被删除节点的右子节点有左子节点。
  6. 情况14:被删除节点是根节点,并且被删除节点的右子节点有左子节点。

上面我们分析了二叉树删除的所有情况,接下来我会根据分析情况对代码进行解析。

代码分析

我们现在分析的重点是Binarytree的delete方法,要执行删除操作,必须先找到需要删除的结点。

寻找删除的结点

寻找删除结点的过程和插入结点的过程是一样的,只不过compare的结果为0才算是找到了目标删除结点,简化代码为:

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

这部分代码和插入是一样的,从根节点遍历整棵树,直到找到compare为0的结点,相信大家如果理解了之前所说的插入,那么这里也应该理解了。

删除目标节点

删除的代码,我们分几个模块分析,首先被删除结点没有子节点

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

下面是被删除节点只有一个子节点
老死机带你用PHP实现数据结构之二叉树

接下来是被删除结点存在2个子节点:

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

代码的流程和上面的分析一一对应,如果你看懂了我上面的分析,代码肯定没有问题,好了,测试文件如下所示:

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

总结

请原谅,因为在贴出代码之前,我已经列举出了二叉树删除的所有情况,所以后面没有再仔细的分析代码,你只要看懂我上面的实例图片,看懂代码,完全不是问题,如果你遇到困难,请加qq群:

本作品采用《CC 协议》,转载必须注明作者和本文链接
如果有不懂的地方,可以加我的qq:1174332406,或者是微信:itshardjs
本帖由系统于 10个月前 自动加精
Dennis_Ritchie
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 7

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

10个月前 评论

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

10个月前 评论

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

10个月前 评论

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

10个月前 评论
VeryCool

老死机 还玩二叉树

10个月前 评论
Dennis_Ritchie (楼主) 10个月前

提出一个疑问

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

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

// 以下为 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;
    }

运行输出结果:
file

然后将 // $tree->delete(20); 注释打开,删除 20
运行输出结果:
file
但是该结果与预期结果不符。
file
该子树无故消失,我预期的结果应该如下:
file
经过分析代码后发现:
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();
    }
}

再次运行后结果如下:
file
最终结果符合我的预期,请问这样是否正确?

10个月前 评论

你给的定义是BST

10个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!