内容简介:在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 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 实现数据结构】遍历二叉查找树
- 数据结构和算法面试题系列—二分查找算法详解
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Domain-Driven Design Distilled
Vaughn Vernon / Addison-Wesley Professional / 2016-6-2 / USD 36.99
Domain-Driven Design (DDD) software modeling delivers powerful results in practice, not just in theory, which is why developers worldwide are rapidly moving to adopt it. Now, for the first time, there......一起来看看 《Domain-Driven Design Distilled》 这本书的介绍吧!