數(shù)據(jù)結構之利用PHP實現(xiàn)二分搜索樹
前言
這篇文章是介紹 二叉樹 和 二分搜索樹，然后通過 PHP 代碼定義一下 二分搜索樹 的節(jié)點，使用遞歸思想操作向二分搜索樹添加元素，然后實現(xiàn)了遞歸判斷二分搜索樹上是否包含某個元素，最后分別實現(xiàn)了前序遍歷、中序遍歷、后序遍歷 二分搜索樹。
1.二叉樹
1.1 二叉樹圖示
1.2 二叉樹節(jié)點定義
//二叉樹具有唯一根節(jié)點
class Node{
$e; //節(jié)點元素
$left; //左兒子
$right;//右兒子
}
Tips：二叉樹每個節(jié)點最多有兩個兒子，每個節(jié)點最多有一個父親。
1.3 二叉樹的特點
- 二叉樹具有天然的遞歸結構，每個節(jié)點的左兒子或右兒子也是 二叉樹。
- 二叉樹不一定是滿的，可能只有左兒子或又兒子。
- 一個節(jié)點或 NULL 也可以看做一個二叉樹。
2.二分搜索樹
2.1 二分搜索樹特點
- 二分搜索樹是二叉樹。
- 每個節(jié)點的元素的值都要大于左兒子所有節(jié)點的值。
- 每個節(jié)點的元素的值都要小于右兒子所有節(jié)點的值。
- 每個子樹也是二分搜索樹。
- 二分搜索樹查詢速度快。
- 存儲的元素必須要有比較性。
2.2 二分搜索樹圖示
2.3 PHP 代碼定義節(jié)點
class Node
{
public $e;
public $left = null;
public $right = null;
/**
* 構造函數(shù) 初始化節(jié)點數(shù)據(jù)
* Node constructor.
* @param $e
*/
public function __construct($e) {
$this->e = $e;
}
}
2.4 向二分搜索樹添加元素
下面展示的的使用遞歸思想向二分搜索樹添加元素，其中 add($e) 方法表示想二分搜索樹添加元素 $e，recursionAdd(Node $root, $e) 是一個遞歸函數(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é)點為空則添加元素 并且返回當前節(jié)點信息
$this->size++;
$root = new Node($e);
} elseif ($e < $root->e) { //若元素小于當前節(jié)點元素 則向左節(jié)點遞歸添加元素
$root->left = $this->recursionAdd($root->left, $e);
} elseif ($e > $root->e) { //若元素大于當前節(jié)點元素 則向右節(jié)點遞歸添加元素
$root->right = $this->recursionAdd($root->right, $e);
} //若元素等于當前節(jié)點元素 則什么都不做
}
Tips：這里的二分搜索樹不包含重復元素，如果想要包含重復元素，可以定義每個左兒子所有元素小于等于父親節(jié)點，或者每個節(jié)點右兒子所有節(jié)點元素大于等于父親節(jié)點。
2.5 查詢二分搜索樹是否包含某個元素
下面展示的的使用遞歸思想查詢二分搜索樹元素是否包含某個元素，其中 contains($e) 方法表示查詢二分搜索樹是否包含元素 $e，recursionContains(Node $root, $e) 是一個遞歸函數(shù)，表示使用遞歸查詢二分搜索樹元素：
/**
* 判斷二分搜索樹是否包含某個元素
* @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) { //若當前節(jié)點為空 則表示不存在元素 $e
return false;
} elseif ($e == $root->e) { //若 $e 等于當前節(jié)點元素，則表示樹包含元素 $e
return true;
} elseif ($e < $root->e) { //若 $e 小于當前節(jié)點元素，則去左兒子樹遞歸查詢是否包含節(jié)點
return $this->recursionContains($root->left, $e);
} else { //若 $e 大于當前節(jié)點元素，則去右兒子樹遞歸查詢是否包含節(jié)點
return $this->recursionContains($root->right, $e);
}
}
Tips：遞歸的時候會比較元素和節(jié)點的值，遞歸的時候判斷元素大小相當于 “指路”，最終指向到的位置就是判斷是否包含元素是否存在的依據(jù)。
2.6 二分搜索樹前序遍歷
前序遍歷操作就是把所有節(jié)點都訪問一次，前序遍歷 是先訪問節(jié)點，再遞歸遍歷左兒子樹，然后再遞歸遍歷右兒子樹：
/**
* 前序遍歷
*/
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>"; //打印當前節(jié)點元素
$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 二分搜索樹中序遍歷
遍歷操作就是把所有節(jié)點都訪問一次，后序遍歷 是先遞歸遍歷右兒子樹，再訪問節(jié)點，然后再遞歸遍歷右兒子樹，最后的順序輸出結果是有序的：
/**
* 中序遍歷
*/
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 二分搜索樹后序遍歷
遍歷操作就是把所有節(jié)點都訪問一次，后序遍歷 是先遞歸遍歷左兒子樹，然后再遞歸遍歷右兒子樹，再訪問節(jié)點：
/**
* 后序遍歷
*/
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...
總結
到此這篇關于數(shù)據(jù)結構之利用PHP實現(xiàn)二分搜索樹的文章就介紹到這了,更多相關PHP實現(xiàn)二分搜索樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
利用php+mcDropdown實現(xiàn)文件路徑可在下拉框選擇
以下是對php+mcDropdown實現(xiàn)文件路徑可在下拉框進行選擇的方法進行了詳細的分析介紹，需要的朋友可以過來參考下2013-08-08
基于PHP實現(xiàn)棧數(shù)據(jù)結構和括號匹配算法示例
這篇文章主要介紹了基于PHP實現(xiàn)棧數(shù)據(jù)結構和括號匹配算法,結合實例形式分析了php數(shù)組操作實現(xiàn)棧數(shù)據(jù)結構的進棧、出棧,以及基于棧的括號匹配應用技巧,需要的朋友可以參考下2017-08-08
這篇文章主要介紹了PHP訪問數(shù)據(jù)庫集群的方法,結合實例形式總結分析了三種常見的PHP訪問數(shù)據(jù)庫集群的技巧,需要的朋友可以參考下2016-03-03
這篇文章主要介紹了php接口技術,結合實例形式分析了php接口的基本概念、功能、定義、使用方法與相關注意事項,需要的朋友可以參考下2016-12-12
這篇文章主要介紹了PHP抽象類與接口的區(qū)別,結合實例形式分析了php抽象類與接口的概念、區(qū)別、使用方法及相關操作注意事項,需要的朋友可以參考下2019-05-05
PHPwind整合最土系統(tǒng)用戶同步登錄實現(xiàn)方法
我的任務就是讓PHPWind和最土登錄同步，領導也知道我的技術能力有限，不怎么高要求，所以讓我先實現(xiàn)，再考慮其他。趕鴨子上架，開工了。2010-12-12
這篇文章主要介紹了php無限級分類實現(xiàn)方法,結合2個簡單實例形式分析了php通過遞歸與普通算法實現(xiàn)無限級分類的相關操作技巧,需要的朋友可以參考下2016-10-10
PHP實現(xiàn)將漢字轉換為拼音及獲取詞語首字母的方法
這篇文章主要介紹了PHP實現(xiàn)將漢字轉換為拼音及獲取詞語首字母的方法,涉及php字符串、數(shù)組的遍歷及編碼轉換相關操作技巧,需要的朋友可以參考下2017-08-08
xhprof 是一款Facebook工程師開發(fā)和維護的一款PHP性能分析、調試工具，相較于xdebug要更輕量，更節(jié)省資源，強烈推薦大家使用。下面這篇文章主要給大家介紹了關于PHP性能分析工具xhprof的安裝與使用方法的相關資料，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了ecshop 2.72如何修改后臺訪問地址的方法,需要的朋友可以參考下2015-03-03