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

更新时间:2023-04-08 23:27:19 阅读：评论：0

前言

这篇文章是介绍二叉树和二分搜索树，然后通过 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);  } elif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素   $root->left = $this->recursionadd($root->left, $e);  } elif ($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 fal;  } elif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e   return true;  } elif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点   return $this->recursioncontains($root->left, $e);  } el { //若 $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;  }  ech中餐服务培训o $root->e . "<br>"; //打印当前节点元素  $this->recursionpretraversal($root->left, $sign_num + 1);  $this->recursionpretraversal($root->right, $sign_num + 1); }

下面是打印结果:

<?php
require ‘binaryarchtree.php’;
$binaryarchtree = new binaryarchtree();
$binaryarchtree->add(45);
$binaryarchtree->add(30);
$binaryarchtree->add(55);
$binaryarchtree->add(25);
$binaryarchtree->add(35);
$binaryarchtree->add(50);
$binaryarchtree->add(65);
$binaryarchtree->add(15);
$binaryarchtree->add(27);
$binaryarchtree->add(31);
$binaryarchtree->add(48);
$binaryarchtree->ad逆境与成才d(60);
$binaryarchtree->add(68);
//下面是预期想要的结果
/**
* 45
* /
* 30 55
* / /
* 25 35 50 65
* / / / /
* 15 27 31 48 60 68
*
*/
$binaryarchtree->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) {   e我的学习生活作文cho $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 ‘binaryarchtree.php’;
$binaryarchtree = new binaryarchtree();
$binaryarchtree->add(45);
$binaryarchtree->add(30);
$binaryarchtree->add(55);
$binaryarchtree->add(25);
$binaryarchtree->add(35);
$binaryarchtree->add(50);
$binaryarchtree->add(65);
$binaryarchtree->add(15);
$binaryarchtree->add(27);
$binaryarchtree->add(31);
$binaryarchtree->add(48);
$binaryarchtree->add(60);
$binaryarchtree->add(68);
//下面是预期想要的结果
/**
* 45
* /
* 30 55
* / /
* 25 35 50 65
* / / / /
* 15 27 31 48 60 68
*
*/
$binaryarchtree->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
*/

2020年国庆节图片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 ‘binaryarchtree.php’;
$binaryarchtree = new binaryarchtree();
$binaryarchtree->add(45);
$binaryarchtree->add(30);
$binaryarchtree->add(55);
$binaryarchtree->add(25);
$binaryarchtree->add(35);
$binaryarchtree->add(50);
$binaryarchtree->add(65);
$binaryarchtree->add(15);
$binaryarchtree->add(27);
$binaryarchtree->add(31);
$binaryarchtree->add(48);
$binaryarchtree->add(60);
$binaryarchtree->add(68);
//下面是预期想要的结果
/**
* 45
* /
* 30 55
* / /
* 25 35 50 65
* / / / /
* 15 27 31 48 60 68
*
*/
$binaryarchtree->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
*/