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);