PHP如何实现二分搜索树
发布时间：2022-02-22 01:35:03 所属栏目：PHP教程 来源：互联网
导读：学习过数据结构的朋友对于二叉树应该都不陌生，而二分搜索树也叫做二叉查找树，那么如何使用PHP来实现二分搜索树呢？下面我们一起来看一看。 这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分
|
学习过数据结构的朋友对于二叉树应该都不陌生，而二分搜索树也叫做二叉查找树，那么如何使用PHP来实现二分搜索树呢？下面我们一起来看一看。 这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。 1.二叉树 1.1 二叉树图示 1.2 二叉树节点定义 //二叉树具有唯一根节点 class Node{ $e; //节点元素 $left; //左儿子 $right;//右儿子 } Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。 1.3 二叉树的特点 二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。 二叉树不一定是满的，可能只有左儿子或又儿子。 一个节点或 NULL 也可以看做一个二叉树。 2.二分搜索树 2.1 二分搜索树特点 二分搜索树是二叉树。 每个节点的元素的值都要大于左儿子所有节点的值。 每个节点的元素的值都要小于右儿子所有节点的值。 每个子树也是二分搜索树。 二分搜索树查询速度快。 存储的元素必须要有比较性。 2.2 二分搜索树图示 2.3 PHP 代码定义节点 class Node { public $e; public $left = null; public $right = null; /** * 构造函数 初始化节点数据 * Node constructor. * @param $e */ public function __construct($e) { $this->e = $e; } } 2.4 向二分搜索树添加元素 下面展示的的使用递归思想向二分搜索树添加元素，其中 add($e) 方法表示想二分搜索树添加元素 $e，recursionAdd(Node $root, $e) 是一个递归函数，表示使用递归向二分搜索树添加元素： /** * 向二分搜索树添加元素 * @param $e */ public function add($e) { $this->root = $this->recursionAdd($this->root, $e); } /** * 递归向二分搜索树添加元素 * @param Node $root * @param $e */ public function recursionAdd(Node $root, $e) { if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息 $this->size++; $root = new Node($e); } elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素 $root->left = $this->recursionAdd($root->left, $e); } elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素 $root->right = $this->recursionAdd($root->right, $e); } //若元素等于当前节点元素 则什么都不做 } Tips：这里的二分搜索树不包含重复元素，如果想要包含重复元素，可以定义每个左儿子所有元素小于等于父亲节点，或者每个节点右儿子所有节点元素大于等于父亲节点。 2.5 查询二分搜索树是否包含某个元素 下面展示的的使用递归思想查询二分搜索树元素是否包含某个元素，其中 contains($e) 方法表示查询二分搜索树是否包含元素 $e，recursionContains(Node $root, $e) 是一个递归函数，表示使用递归查询二分搜索树元素： /** * 判断二分搜索树是否包含某个元素 * @param $e * @return bool */ public function contains($e): bool { return $this->recursionContains($this->root, $e); } /** * 递归判断二分搜索树是否包含某元素 * @param $root * @param $e * @return bool */ private function recursionContains(Node $root, $e): bool { if ($root == null) { //若当前节点为空 则表示不存在元素 $e return false; } elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e return true; } elseif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点 return $this->recursionContains($root->left, $e); } else { //若 $e 大于当前节点元素，则去右儿子树递归查询是否包含节点 return $this->recursionContains($root->right, $e); } } Tips：递归的时候会比较元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的位置就是判断是否包含元素是否存在的依据。 2.6 二分搜索树前序遍历 前序遍历操作就是把所有节点都访问一次，前序遍历 是先访问节点，再递归遍历左儿子树，然后再递归遍历右儿子树： /** * 前序遍历 */ public function preTraversal() { $this->recursionPreTraversal($this->root, 0); } /** * 前序遍历的递归 */ public function recursionPreTraversal($root, $sign_num) { echo $this->getSign($sign_num);//打印深度 if ($root == null) { echo "null<br>"; return; } echo $root->e . "<br>"; //打印当前节点元素 $this->recursionPreTraversal($root->left, $sign_num + 1); $this->recursionPreTraversal($root->right, $sign_num + 1); } 下面是打印结果: <?php require 'BinarySearchTree.php'; $binarySearchTree = new BinarySearchTree(); $binarySearchTree->add(45); $binarySearchTree->add(30); $binarySearchTree->add(55); $binarySearchTree->add(25); $binarySearchTree->add(35); $binarySearchTree->add(50); $binarySearchTree->add(65); $binarySearchTree->add(15); $binarySearchTree->add(27); $binarySearchTree->add(31); $binarySearchTree->add(48); $binarySearchTree->add(60); $binarySearchTree->add(68); //下面是预期想要的结果 /** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */ $binarySearchTree->preTraversal(); /** 打印输出 45 -----30 ----------25 ---------------15 --------------------null --------------------null ---------------27 --------------------null --------------------null ----------35 ---------------31 --------------------null --------------------null ---------------null -----55 ----------50 ---------------48 --------------------null --------------------null ---------------null ----------65 ---------------60 --------------------null --------------------null ---------------68 --------------------null --------------------null */ Tips：可以看到打印输出结果和预期一致。 2.7 二分搜索树中序遍历 遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历右儿子树，再访问节点，然后再递归遍历右儿子树，最后的顺序输出结果是有序的： /** * 中序遍历 */ public function midTraversal() { $this->recursionMidTraversal($this->root, 0); } /** * 中序遍历的递归 */ public function recursionMidTraversal($root, $sign_num) { if ($root == null) { echo $this->getSign($sign_num);//打印深度 echo "null<br>"; return; } $this->recursionMidTraversal($root->left, $sign_num + 1); echo $this->getSign($sign_num);//打印深度 echo $root->e . "<br>"; $this->recursionMidTraversal($root->right, $sign_num + 1); } 下面是打印结果: <?php require 'BinarySearchTree.php'; $binarySearchTree = new BinarySearchTree(); $binarySearchTree->add(45); $binarySearchTree->add(30); $binarySearchTree->add(55); $binarySearchTree->add(25); $binarySearchTree->add(35); $binarySearchTree->add(50); $binarySearchTree->add(65); $binarySearchTree->add(15); $binarySearchTree->add(27); $binarySearchTree->add(31); $binarySearchTree->add(48); $binarySearchTree->add(60); $binarySearchTree->add(68); //下面是预期想要的结果 /** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */ $binarySearchTree->midTraversal(); /** 打印输出 --------------------null ---------------15 --------------------null ----------25 --------------------null ---------------27 --------------------null -----30 --------------------null ---------------31 --------------------null ----------35 ---------------null 45 --------------------null ---------------48 --------------------null ----------50 ---------------null -----55 --------------------null ---------------60 --------------------null ----------65 --------------------null ---------------68 --------------------null */ Tips：可以看到打印输出结果和预期一致，但是此时的遍历顺序变了，最后的顺序输出结果是有序的。 2.8 二分搜索树后序遍历 遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历左儿子树，然后再递归遍历右儿子树，再访问节点： /** * 后序遍历 */ public function rearTraversal() { $this->recursionRearTraversal($this->root, 0); } /** * 后序遍历的递归 */ public function recursionRearTraversal($root, $sign_num) { if ($root == null) { echo $this->getSign($sign_num);//打印深度 echo "null<br>"; return; } $this->recursionRearTraversal($root->left, $sign_num + 1); $this->recursionRearTraversal($root->right, $sign_num + 1); echo $this->getSign($sign_num);//打印深度 echo $root->e . "<br>"; } 下面是打印结果: <?php require 'BinarySearchTree.php'; $binarySearchTree = new BinarySearchTree(); $binarySearchTree->add(45); $binarySearchTree->add(30); $binarySearchTree->add(55); $binarySearchTree->add(25); $binarySearchTree->add(35); $binarySearchTree->add(50); $binarySearchTree->add(65); $binarySearchTree->add(15); $binarySearchTree->add(27); $binarySearchTree->add(31); $binarySearchTree->add(48); $binarySearchTree->add(60); $binarySearchTree->add(68); //下面是预期想要的结果 /** * 45 * / * 30 55 * / / * 25 35 50 65 * / / / / * 15 27 31 48 60 68 * */ $binarySearchTree->rearTraversal(); /** 打印输出 --------------------null --------------------null ---------------15 --------------------null --------------------null ---------------27 ----------25 --------------------null --------------------null ---------------31 ---------------null ----------35 -----30 --------------------null --------------------null ---------------48 ---------------null ----------50 --------------------null --------------------null ---------------60 --------------------null --------------------null ---------------68 ----------65 -----55 45 */ 总结 以上就是对PHP实现二分搜索树的介绍，本文有详细的实现过程及示例，大家可以参考一下，希望对大家学习有帮助。 （编辑：武汉站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
