【PHP 实现数据结构】二叉查找树

栏目: IT技术 · 发布时间: 4年前

内容简介:在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 D 有三个子节点,它就不能称为二叉树。

什么是二叉树

在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样

【PHP 实现数据结构】二叉查找树

而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 D 有三个子节点,它就不能称为二叉树。

什么是二叉查找树

二叉查找树又称为二叉 排序 数,是一种更特殊的树,首先它是二叉树,最多只会有两个节点,分别称为左节点和右节点,其次它的所有节点中,较小的值保存在左节点,较大的值保存在右节点。像这样

【PHP 实现数据结构】二叉查找树

为了保证值大小的逻辑,在往二叉数里写数据时,就不能像队列或栈一样,直接放在队尾或栈顶了,需要有一定的逻辑处理。

【PHP 实现数据结构】二叉查找树

代码实现

我们先实现数据结构和上述的数据逻辑

定义节点

/**
 * Class Node
 * @property-read $left
 * @property-read $right
 */
class Node
{
    public $data;
    private $left = null;
    private $right = null;

    public function __construct($data)
    {
        $this->data = $data;
    }

    /**
     * @param Node $left
     */
    public function setLeft(Node $left)
    {
        $this->left = $left;
    }

    /**
     * @param Node $right
     */
    public function setRight(Node $right)
    {
        $this->right = $right;
    }

    public function __get($name)
    {
        if (in_array($name, ['left', 'right'])) {
            return $this->{$name};
        }
        return null;
    }
}

二叉查找树

class BinarySortTree
{
    /**
     * @var Node
     */
    public $root;

    public function insert($data) {
        $node = new Node($data);
        if(null == $this->root) {
            $this->root = $node;
            return;
        }

        $current = $this->root;
        do {
            $parent = $current;
            if ($node->data < $current->data) {
                $current = $parent->left;
                if(null == $current) {
                    $parent->setLeft($node);
                }
            } else {
                $current = $current->right;
                if(null == $current) {
                    $parent->setRight($node);
                }
            }
        } while ($current);
    }
}

示例

$bst = new BinarySortTree();
$bst->insert(23);
$bst->insert(45);
$bst->insert(16);
$bst->insert(37);
$bst->insert(3);
$bst->insert(99);
$bst->insert(22);

这样我们就获得了与上述示例图的一致的一个二叉树实例了,执行代码,数据插入流程是这样的

set root 23
current: 23, set right: 45
current: 23, set left: 16
current: 45, set left: 37
current: 16, set left: 3
current: 45, set right: 99
current: 16, set right: 22

以上所述就是小编给大家介绍的《【PHP 实现数据结构】二叉查找树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Go语言实战

Go语言实战

威廉·肯尼迪 (William Kennedy)、布赖恩·克特森 (Brian Ketelsen)、埃里克·圣马丁 (Erik St.Martin) / 李兆海 / 人民邮电出版社 / 2017-3-1 / CNY 59.00

Go语言结合了底层系统语言的能力以及现代语言的高级特性,旨在降低构建简单、可靠、高效软件的门槛。本书向读者提供一个专注、全面且符合语言习惯的视角。Go语言实战同时关注语言的规范和实现,涉及的内容包括语法、类型系统、并发、管道、测试,以及其他一些主题。一起来看看 《Go语言实战》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具