# 【PHP 实现数据结构】二叉查找树

#### 定义节点

/**
* 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 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