数据结构之利用PHP实现二分搜索树

头像
后端开发 2024年05月26日 756 浏览
首页 动态 后端开发 正文
文章详情

前言

这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。

1.二叉树

1.1 二叉树图示

数据结构之利用PHP实现二分搜索树

1.2 二叉树节点定义

//二叉树具有唯一根节点
class Node{
$e; //节点元素
$left; //左儿子
$right;//右儿子
}

Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。

1.3 二叉树的特点

  • 二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。

  • 二叉树不一定是满的，可能只有左儿子或又儿子。

  • 一个节点或 NULL 也可以看做一个二叉树。

2.二分搜索树

2.1 二分搜索树特点

  • 二分搜索树是二叉树。

  • 每个节点的元素的值都要大于左儿子所有节点的值。

  • 每个节点的元素的值都要小于右儿子所有节点的值。

  • 每个子树也是二分搜索树。

  • 二分搜索树查询速度快。

  • 存储的元素必须要有比较性。

2.2 二分搜索树图示

数据结构之利用PHP实现二分搜索树

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

ips：递归的时候会比较元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的位置就是判断是否包含元素是否存在的依据。

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

代码仓库 ：https://gitee.com/love-for-po…

总结

到此这篇关于数据结构之利用PHP实现二分搜索树的文章就介绍到这了

收藏 0
点赞 0

版权：版权申明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 70068002@qq.com 举报，一经查实，本站将立刻删除。

转载请注明出处：https://www.stntk.com/2593.html

头像
上一篇： 关于Java8中map()和flatMap()的一些事
下一篇： python时间time模块处理大全
相关推荐
php数据库怎样去重复的数据
php数据库怎样去重复的数据
当涉及到数据库去重功能时，PHP可以与数据库交互并执行相应的操作。以下是一个示例的PHP代码，用于从数据库中删除重复的记录并保留唯一的数据：…
头像
后端开发 2024-05-26
1,022
如何在 Python 中使用 try…else 块
如何在 Python 中使用 try…else 块
在 Python 编程中，我们经常会遇到需要处理异常的情况。使用 try…except 块是一种常见的处理方法，它可以捕获和处理代码中可能出…
头像
后端开发 2024-05-26
1,319
php发送/显示 base64 编码图像
php发送/显示 base64 编码图像
我需要向客户端发送一个 base64 编码的字符串。因此，我打开并读取服务器上的图像文件，对其进行编码并将该数据与 image/jpeg 内…
头像
后端开发 2024-05-26
11,528
php 生成条形码(支持任意php框架)
php 生成条形码(支持任意php框架)
一：插件安装 在php中我们可以使用php-barcode-generator插件来生成条形码，php-barcode-generator插…
头像
后端开发 2024-05-26
986
如何在ThinkPHP6中使用队列技术
如何在ThinkPHP6中使用队列技术
ThinkPHP 6（TP6）是一个流行的PHP框架，它提供了一些有用的工具和组件，其中之一就是队列（Queue）服务。队列是一种用于异步处…
头像
后端开发 2024-05-26
1,575
cURL error 60: SSL certificate problem: unable to get local issuer certificate 解决方法
cURL error 60: SSL certificate problem: unable to get local issuer certificate 解决方法
fastadmin开发小程序登录功能报错： cURL error 60: SSL certificate problem: unable t…
头像
后端开发 2024-05-26
1,089
发表评论
暂无评论

还没有评论呢，快来抢沙发~

Lomu
头像

码农,程序员,码农网,码农社区,码农教程,码农日报,码农工具,码农文章,码农书籍,码农头条

文章
261
收藏
1
人气
305,863
粉丝
4
    文章展示
    随机标签

    创造一个强大的网站从未如此简单！

    即刻开启创造面向世界的产业链

    从优米云开始
    今日签到
    抽奖活动
    点击联系客服

    在线时间：8:00-16:00

    客服电话

    400-888-8888

    客服邮箱

    70068002@qq.com

    扫描二维码

    关注微信公众号

    首页 论坛 菜单 会员 我的