文章詳情頁

數據結構之利用PHP實現二分搜索樹

瀏覽：73日期：2022-09-08 18:34:29

前言

這篇文章是介紹二叉樹和二分搜索樹，然后通過 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 '; return; } echo $root->e . ' '; //打印當前節點元素 $this->recursionPreTraversal($root->left, $sign_num + 1); $this->recursionPreTraversal($root->right, $sign_num + 1); }

下面是打印結果:

<?phprequire ’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); }

下面是打印結果:

<?phprequire ’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---------------null45--------------------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 . ' '; }

下面是打印結果:

<?phprequire ’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-----5545 */

代碼倉庫：https://gitee.com/love-for-po...

總結

到此這篇關于數據結構之利用PHP實現二分搜索樹的文章就介紹到這了,更多相關PHP實現二分搜索樹內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！

PHP

上一條：基于PHP實現郵箱驗證激活過程詳解下一條：php redis setnx分布式鎖簡單原理解析

相關文章：

1. ASP動態網頁制作技術經驗分享2. jsp文件下載功能實現代碼3. asp.net core項目授權流程詳解4. 在JSP中使用formatNumber控制要顯示的小數位數方法5. CSS3實現動態翻牌效果仿百度貼吧3D翻牌一次動畫特效6. XMLHTTP資料7. ASP常用日期格式化函數 FormatDate()8. html中的form不提交（排除）某些input 原創9. CSS3中Transition屬性詳解以及示例分享10. ASP基礎入門第八篇（ASP內建對象Application和Session）

排行榜

					
					Python數據相關系數矩陣和熱力圖輕松實現教程
如何在PHP中讀寫文件
vue-drag-chart 拖動/縮放圖表組件的實例代碼
PHP正則表達式函數preg_replace用法實例分析
如何使用repr調試python程序
Django與AJAX實現網頁動態數據顯示的示例代碼
python 截取XML中bndbox的坐標中的圖像,另存為jpg的實例
Django項目如何獲得SSL證書與配置HTTPS
解決android studio引用遠程倉庫下載慢(JCenter下載慢)
關于Spring自定義XML schema 擴展的問題(Spring面試高頻題)
vue3頁面跳轉的兩種方式
				