内容简介:在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 D 有三个子节点,它就不能称为二叉树。
什么是二叉树
在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样
而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 D 有三个子节点,它就不能称为二叉树。
什么是二叉查找树
二叉查找树又称为二叉 排序 数,是一种更特殊的树,首先它是二叉树,最多只会有两个节点,分别称为左节点和右节点,其次它的所有节点中,较小的值保存在左节点,较大的值保存在右节点。像这样
为了保证值大小的逻辑,在往二叉数里写数据时,就不能像队列或栈一样,直接放在队尾或栈顶了,需要有一定的逻辑处理。
代码实现
我们先实现数据结构和上述的数据逻辑
定义节点
/** * 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 实现数据结构】二叉查找树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
- 数据结构之二分查找
- 数据结构与算法:二分查找
- 数据结构与算法:二分查找
- 【PHP 实现数据结构】遍历二叉查找树
- 数据结构和算法面试题系列—二分查找算法详解
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
阿里巴巴正传:我们与马云的“一步之遥”
方兴东、刘伟 / 江苏凤凰文艺出版社 / 2015-1 / 45.00
十几年来,方兴东与马云每年一次,老友聚首,开怀畅谈,阿里上市前,作者再次与马云深度对话,阿里上市前的布局,深入探讨了一系列人们关心的话题。 本书忠实记录了阿里壮大、马云封圣的历史。作者通过细致梳理和盘点,对阿里巴巴的15年成长史进行了忠实回顾。从海博翻译社到淘宝网,从淘宝商城到天猫,从支付宝到阿里云计算,从拉来软银的第一笔投资到纽交所上市,作者对其中涉及到的人物、细节都有生动展现;对于马云、......一起来看看 《阿里巴巴正传:我们与马云的“一步之遥”》 这本书的介绍吧!
在线进制转换器
各进制数互转换器
HSV CMYK 转换工具
HSV CMYK互换工具