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

 更新时间:2020-11-19 10:26:28   作者:佚名   我要评论(0)

前言
这篇文章是介绍 二叉树 和 二分搜索树,然后通过 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
 */

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

总结

到此这篇关于数据结构之利用PHP实现二分搜索树的文章就介绍到这了,更多相关PHP实现二分搜索树内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!

您可能感兴趣的文章:
  • 使用PHP实现二分查找算法代码分享
  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解
  • php二分法在IP地址查询中的应用
  • php二分查找二种实现示例
  • 深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表
  • PHP字符串逆序排列实现方法小结【strrev函数,二分法,循环法,递归法】
  • php顺序查找和二分查找示例
  • php 数组二分法查找函数代码
  • php数据结构与算法(PHP描述) 查找与二分法查找
  • php中二分法查找算法实例分析

相关文章

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

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

    前言 这篇文章是介绍 二叉树 和 二分搜索树,然后通过 PHP 代码定义一下 二分搜索树 的节点,使用递归思想操作向二分搜索树添加元素,然后实现了递归判断二分搜索树
    2020-11-19
  • THINKPHP5分页数据对象处理过程解析

    THINKPHP5分页数据对象处理过程解析

    在用到THINKPHP5的分页的时候,我们可以发现获取的数据是对象,如果我们要对数据进行循环增加数据就实现不了 今天用此方法解决,以做记录方便以后忘了查看 // 查询
    2020-11-19
  • Laravel 自动转换长整型雪花 ID 为字符串的实现

    Laravel 自动转换长整型雪花 ID 为字符串的实现

    在设计 API 时,出于安全性等因素考虑,有时需要放弃使用自增 ID,使 ID 非连续且不可猜测。通常可以使用 Hash id,UUID,雪花 ID 等来实现。 在最近的一个项目中,我
    2020-11-19
  • 基于PHP实现邮箱验证激活过程详解

    基于PHP实现邮箱验证激活过程详解

    我们在很多网站注册会员时,注册完成后,系统会自动向用户的邮箱发送一封邮件,这封邮件的内容就是一个URL链接,用户需要点击打开这个链接才能激活之前在该网站注册
    2020-11-19
  • ThinkPHP 5 AJAX跨域请求头设置实现过程解析

    ThinkPHP 5 AJAX跨域请求头设置实现过程解析

    最近用thinkphp做项目,在测试环境时,存在接口的测试问题。在tp官网也没能找到相关的解决方法。自已看了一下源码,有如下的解决方案。 在项目目录下面,创建common
    2020-11-19
  • PHP常量DIRECTORY_SEPARATOR原理及用法解析

    PHP常量DIRECTORY_SEPARATOR原理及用法解析

    DIRECTORY_SEPARATOR在php是什么意思呢,在什么时候使用DIRECTORY_SEPARATOR最合理呢&#63;下面来给各位介绍一下php DIRECTORY_SEPARATOR常量。 我们知道DIRECTORY_S
    2020-11-19
  • 解决PHPstudy Apache无法启动的问题【亲测有效】

    解决PHPstudy Apache无法启动的问题【亲测有效】

    phpStudy启动失败,网上总结了基本就是下面的三种方法: 原因一是防火墙拦截,关闭防火墙。 二是80端口已经被别的程序占用,如IIS,迅雷等; 三是没有安装VC9运行库
    2020-11-19
  • PHP dirname(__FILE__)原理及用法解析

    PHP dirname(__FILE__)原理及用法解析

    dirname(dirname(_FILE_)); 假设__FILE__为 /home/web/config/config.php 上面的方法输出为 /home/web dirname(dirname(\__FILE__));//得到的是文件上一层目录名
    2020-11-19
  • 基于PHP实现用户在线状态检测

    基于PHP实现用户在线状态检测

    这个是基于ThinkPHP框架的,其他的可以自己根据需求改 1.先新建一个tags.php文件,放在配置目录Conf下。 <&#63;php /* * 添加行为 * */ return array( 'ac
    2020-11-19
  • phpstudy2020搭建站点的实现示例

    phpstudy2020搭建站点的实现示例

    1.下载phpstudy(到官网下载),并安装后,启动phpstudy 2. 进入C:\Windows\System32\drivers\etc路径下的hosts文件,进行如下配置 127.0.0.1 xxxxadmin.com 127.0
    2020-11-19

最新评论