主頁(yè) > 知識(shí)庫(kù) > 數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹

數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹

熱門標(biāo)簽:招標(biāo)自動(dòng)語(yǔ)音外呼系統(tǒng) gps 地圖標(biāo)注軟件 黔江400電話如何辦理 OMG地圖標(biāo)注app 地圖標(biāo)注視頻廣告入駐 ai電話機(jī)器人加盟代理 電銷機(jī)器人便宜的有嗎 中原區(qū)電話機(jī)器人價(jià)格 400電話鄭州申請(qǐng)

前言

這篇文章是介紹 二叉樹 和 二分搜索樹,然后通過(guò) PHP 代碼定義一下 二分搜索樹 的節(jié)點(diǎn),使用遞歸思想操作向二分搜索樹添加元素,然后實(shí)現(xiàn)了遞歸判斷二分搜索樹上是否包含某個(gè)元素,最后分別實(shí)現(xiàn)了前序遍歷、中序遍歷、后序遍歷 二分搜索樹。

1.二叉樹

1.1 二叉樹圖示

1.2 二叉樹節(jié)點(diǎn)定義

//二叉樹具有唯一根節(jié)點(diǎn)
class Node{
 $e; //節(jié)點(diǎn)元素
 $left; //左兒子
 $right;//右兒子
}

Tips:二叉樹每個(gè)節(jié)點(diǎn)最多有兩個(gè)兒子,每個(gè)節(jié)點(diǎn)最多有一個(gè)父親。

1.3 二叉樹的特點(diǎn)

  • 二叉樹具有天然的遞歸結(jié)構(gòu),每個(gè)節(jié)點(diǎn)的左兒子或右兒子也是 二叉樹。
  • 二叉樹不一定是滿的,可能只有左兒子或又兒子。
  • 一個(gè)節(jié)點(diǎn)或 NULL 也可以看做一個(gè)二叉樹。

2.二分搜索樹

2.1 二分搜索樹特點(diǎn)

  • 二分搜索樹是二叉樹。
  • 每個(gè)節(jié)點(diǎn)的元素的值都要大于左兒子所有節(jié)點(diǎn)的值。
  • 每個(gè)節(jié)點(diǎn)的元素的值都要小于右兒子所有節(jié)點(diǎn)的值。
  • 每個(gè)子樹也是二分搜索樹。
  • 二分搜索樹查詢速度快。
  • 存儲(chǔ)的元素必須要有比較性。

2.2 二分搜索樹圖示

2.3 PHP 代碼定義節(jié)點(diǎn)

class Node
{
 public $e;
 public $left = null;
 public $right = null;
 /**
  * 構(gòu)造函數(shù) 初始化節(jié)點(diǎn)數(shù)據(jù)
  * Node constructor.
  * @param $e
  */
 public function __construct($e) {
  $this->e = $e;
 }
}

2.4 向二分搜索樹添加元素

下面展示的的使用遞歸思想向二分搜索樹添加元素,其中 add($e) 方法表示想二分搜索樹添加元素 $e,recursionAdd(Node $root, $e) 是一個(gè)遞歸函數(shù),表示使用遞歸向二分搜索樹添加元素:

 /**
  * 向二分搜索樹添加元素
  * @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) { //若節(jié)點(diǎn)為空則添加元素 并且返回當(dāng)前節(jié)點(diǎn)信息
   $this->size++;
   $root = new Node($e);
  } elseif ($e  $root->e) { //若元素小于當(dāng)前節(jié)點(diǎn)元素 則向左節(jié)點(diǎn)遞歸添加元素
   $root->left = $this->recursionAdd($root->left, $e);
  } elseif ($e > $root->e) { //若元素大于當(dāng)前節(jié)點(diǎn)元素 則向右節(jié)點(diǎn)遞歸添加元素
   $root->right = $this->recursionAdd($root->right, $e);
  } //若元素等于當(dāng)前節(jié)點(diǎn)元素 則什么都不做
 }

Tips:這里的二分搜索樹不包含重復(fù)元素,如果想要包含重復(fù)元素,可以定義每個(gè)左兒子所有元素小于等于父親節(jié)點(diǎn),或者每個(gè)節(jié)點(diǎn)右兒子所有節(jié)點(diǎn)元素大于等于父親節(jié)點(diǎn)。

2.5 查詢二分搜索樹是否包含某個(gè)元素

下面展示的的使用遞歸思想查詢二分搜索樹元素是否包含某個(gè)元素,其中 contains($e) 方法表示查詢二分搜索樹是否包含元素 $e,recursionContains(Node $root, $e) 是一個(gè)遞歸函數(shù),表示使用遞歸查詢二分搜索樹元素:

 /**
  * 判斷二分搜索樹是否包含某個(gè)元素
  * @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) { //若當(dāng)前節(jié)點(diǎn)為空 則表示不存在元素 $e
   return false;
  } elseif ($e == $root->e) { //若 $e 等于當(dāng)前節(jié)點(diǎn)元素,則表示樹包含元素 $e
   return true;
  } elseif ($e  $root->e) { //若 $e 小于當(dāng)前節(jié)點(diǎn)元素,則去左兒子樹遞歸查詢是否包含節(jié)點(diǎn)
   return $this->recursionContains($root->left, $e);
  } else { //若 $e 大于當(dāng)前節(jié)點(diǎn)元素,則去右兒子樹遞歸查詢是否包含節(jié)點(diǎn)
   return $this->recursionContains($root->right, $e);
  }
 }

Tips:遞歸的時(shí)候會(huì)比較元素和節(jié)點(diǎn)的值,遞歸的時(shí)候判斷元素大小相當(dāng)于 “指路”,最終指向到的位置就是判斷是否包含元素是否存在的依據(jù)。

2.6 二分搜索樹前序遍歷

前序遍歷操作就是把所有節(jié)點(diǎn)都訪問(wèn)一次,前序遍歷 是先訪問(wèn)節(jié)點(diǎn),再遞歸遍歷左兒子樹,然后再遞歸遍歷右兒子樹:

 /**
  * 前序遍歷
  */
 public function preTraversal() {
  $this->recursionPreTraversal($this->root, 0);
 }
 /**
  * 前序遍歷的遞歸
  */
 public function recursionPreTraversal($root, $sign_num) {
  echo $this->getSign($sign_num);//打印深度
  if ($root == null) {
   echo "nullbr>";
   return;
  }
  echo $root->e . "br>"; //打印當(dāng)前節(jié)點(diǎn)元素
  $this->recursionPreTraversal($root->left, $sign_num + 1);
  $this->recursionPreTraversal($root->right, $sign_num + 1);
 }

下面是打印結(jié)果:

?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);
//下面是預(yù)期想要的結(jié)果
/**
 *                     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:可以看到打印輸出結(jié)果和預(yù)期一致。

2.7 二分搜索樹中序遍歷

遍歷操作就是把所有節(jié)點(diǎn)都訪問(wèn)一次,后序遍歷 是先遞歸遍歷右兒子樹,再訪問(wèn)節(jié)點(diǎn),然后再遞歸遍歷右兒子樹,最后的順序輸出結(jié)果是有序的:

 /**
  * 中序遍歷
  */
 public function midTraversal() {
  $this->recursionMidTraversal($this->root, 0);
 }
 /**
  * 中序遍歷的遞歸
  */
 public function recursionMidTraversal($root, $sign_num) {
  if ($root == null) {
   echo $this->getSign($sign_num);//打印深度
   echo "nullbr>";
   return;
  }
  $this->recursionMidTraversal($root->left, $sign_num + 1);
  echo $this->getSign($sign_num);//打印深度
  echo $root->e . "br>";
  $this->recursionMidTraversal($root->right, $sign_num + 1);
 }

下面是打印結(jié)果:

?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);
//下面是預(yù)期想要的結(jié)果
/**
 *                     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:可以看到打印輸出結(jié)果和預(yù)期一致,但是此時(shí)的遍歷順序變了,最后的順序輸出結(jié)果是有序的。

2.8 二分搜索樹后序遍歷

遍歷操作就是把所有節(jié)點(diǎn)都訪問(wèn)一次,后序遍歷 是先遞歸遍歷左兒子樹,然后再遞歸遍歷右兒子樹,再訪問(wèn)節(jié)點(diǎn):

 /**
  * 后序遍歷
  */
 public function rearTraversal() {
  $this->recursionRearTraversal($this->root, 0);
 }
 /**
  * 后序遍歷的遞歸
  */
 public function recursionRearTraversal($root, $sign_num) {
  if ($root == null) {
   echo $this->getSign($sign_num);//打印深度
   echo "nullbr>";
   return;
  }
  $this->recursionRearTraversal($root->left, $sign_num + 1);
  $this->recursionRearTraversal($root->right, $sign_num + 1);
  echo $this->getSign($sign_num);//打印深度
  echo $root->e . "br>";
 }

下面是打印結(jié)果:

?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);
//下面是預(yù)期想要的結(jié)果
/**
 *                     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
 */

代碼倉(cāng)庫(kù) :https://gitee.com/love-for-po...

總結(jié)

到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹的文章就介紹到這了,更多相關(guān)PHP實(shí)現(xiàn)二分搜索樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

您可能感興趣的文章:
  • 使用PHP實(shí)現(xiàn)二分查找算法代碼分享
  • PHP 冒泡排序 二分查找 順序查找 二維數(shù)組排序算法函數(shù)的詳解
  • php二分法在IP地址查詢中的應(yīng)用
  • php二分查找二種實(shí)現(xiàn)示例
  • 深入理解PHP幾個(gè)算法:PHP冒泡、PHP二分法、PHP求素?cái)?shù)、PHP乘法表
  • PHP字符串逆序排列實(shí)現(xiàn)方法小結(jié)【strrev函數(shù),二分法,循環(huán)法,遞歸法】
  • php順序查找和二分查找示例
  • php 數(shù)組二分法查找函數(shù)代碼
  • php數(shù)據(jù)結(jié)構(gòu)與算法(PHP描述) 查找與二分法查找
  • php中二分法查找算法實(shí)例分析

標(biāo)簽:阿里 北京 濟(jì)源 池州 日照 孝感 哈密 那曲

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹》,本文關(guān)鍵詞  數(shù)據(jù)結(jié)構(gòu),之,利用,PHP,實(shí)現(xiàn),;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹》相關(guān)的同類信息!
  • 本頁(yè)收集關(guān)于數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章