PHP如何实现二分搜索树?一文带你看懂

时间2024-03-26 08:54:03发布访客分类PHP浏览839

导读：这篇文章主要介绍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
";
    
   return;

  }
    
  echo $root->
    e . "
";
     //打印当前节点元素
  $this->
    recursionPreTraversal($root->
    left, $sign_num + 1);
    
  $this->
    recursionPreTraversal($root->
    right, $sign_num + 1);

 }

下面是打印结果:

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
";
    
   return;

  }
    
  $this->
    recursionMidTraversal($root->
    left, $sign_num + 1);
    
  echo $this->
    getSign($sign_num);
    //打印深度
  echo $root->
    e . "
";
    
  $this->
    recursionMidTraversal($root->
    right, $sign_num + 1);

 }

下面是打印结果:

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
";
    
   return;

  }
    
  $this->
    recursionRearTraversal($root->
    left, $sign_num + 1);
    
  $this->
    recursionRearTraversal($root->
    right, $sign_num + 1);
    
  echo $this->
    getSign($sign_num);
    //打印深度
  echo $root->
    e . "
";

 }

下面是打印结果:

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如何实现二分搜索树的介绍，代码仅供参考，需要的朋友可以了解看看，希望对大家学习PHP有帮助，想要了解更多可以继续浏览网络其他相关的文章。

文本转载自脚本之家

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！

php

若转载请注明出处： PHP如何实现二分搜索树?一文带你看懂
本文地址： https://pptw.com/jishu/653392.html

jQuery EasyUI是什么插件，如何使用 Go并发读写sync.map怎么实现，优势是什么