亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

怎么在PHP中利用數據結構實現二分搜索樹

發布時間：2021-03-03 16:47:13 來源：億速云 閱讀：156 作者：TREX 欄目：開發技術

本篇內容主要講解“數據結構怎么利用PHP實現二分搜索樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“數據結構怎么利用PHP實現二分搜索樹”吧!

前言

這篇文章是介紹 二叉樹 和 二分搜索樹，然后通過 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);
  }
 }

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實現二分搜索樹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！

向AI問一下細節

免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。

AI
助
手
新疆| 叶城县| 呼伦贝尔市| 乌兰县| 襄城县| 胶州市| 汤阴县| 孝义市| 唐山市| 体育| 治多县| 徐闻县| 宝清县| 洛浦县| 新密市| 津南区| 高要市| 葵青区| 长岛县| 土默特左旗| 酉阳| 黄浦区| 会泽县| 平安县| 若羌县| 久治县| 高阳县| 台湾省| 若尔盖县| 安顺市| 剑阁县| 安岳县| 福安市| 沂水县| 喀喇沁旗| 长治市| 小金县| 获嘉县| 平山县| 炎陵县| 宽城|