内容简介:在了解二叉查找树之前,我们行了解一下树的概念。树由节点和层级关系组成,是一种非线性的数据结构。就像现实中树的叶子和枝干一样。树枝把树叶一片片连接起来,树叶就是节点,树枝就是路径。像这样而二叉树是一种特殊的树,它每个节点最多只会有两个节点。像上图,因为节点 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 实现数据结构】遍历二叉查找树
- 数据结构和算法面试题系列—二分查找算法详解
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。