4.1 数据结构(PHP实现) -- 二叉树 > 二分搜索树的结点插入
码农天地 -1. 插入原则:第一个结点为根节点后续插入的结点值如果小于根节点,就成为根节点的左儿子后续插入的结点值如果大于根节点,就成为根节点的右儿子2. 示意图3. 二分搜索树的实现
<?php
/**
* content: 二叉树的二分搜索树的实现
* auth: yujiaming
* create: 2020-10-25 */
namespace TreeBundle;
use ArrayBundle\BaseArray;
use StackBundle\BaseStack;
class BaseBinaryTree
{
public function __construct()
{
$this->rootNode = null;
$this->size = 0;
}
/**
* 二叉树的根节点
* @var Node
*/
protected $rootNode;
/**
* 获取根节点
* @return Node
*/
public function getRootNode(): Node
{
return $this->rootNode;
}
/**
* 二叉树的个数
* @var int
*/
protected $size;
/**
* 获取二叉树的元素个数
* @return int
*/
public function getSize(): int
{
return $this->size;
}
/**
* 判断是否为空
* @return bool
*/
public function isEmpty(): bool
{
return $this->size == 0;
}
/**
* 插入结点
* @param mixed $value
* @return void
*/
public function add($value): void
{
// 如果不存在根节点就插入根节点
if (is_null($this->rootNode)) {
$this->rootNode = new Node($value);
$this->size;
return;
} else {
$this->addChild($value, $this->rootNode);
return;
}
}
/**
* 插入儿子结点
* @param mixed $value
* @param Node|null $parentNode
*/
private function addChild($value, ?Node $parentNode): void
{
if (bccomp($parentNode->getValue(), $value) > 0) {
// 左儿子
if (is_null($parentNode->getLeftChild())) {
$parentNode->setLeftChild(new Node($value));
$this->size++;
return;
} else {
$this->addChild($value, $parentNode->getLeftChild());
}
} elseif (bccomp($parentNode->getValue(), $value) < 0) {
// 右儿子
if (is_null($parentNode->getRightChild())) {
$parentNode->setRightChild(new Node($value));
$this->size++;
return;
} else {
$this->addChild($value, $parentNode->getRightChild());
}
} else {
return;
}
}
}
4. demo<?php
// composer自动加载
require_once __DIR__ . '/../../vendor/autoload.php';
// 获取一个二分搜索树
$tree = new TreeBundleBaseBinaryTree();
// 插入根节点
$tree->add(10);
$tree->add(5);
$tree->add(15);
$tree->add(1);
$tree->add(9);
特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。
php介绍
PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。