這篇“php實現(xiàn)二叉樹的方法是什么”文章的知識點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“php實現(xiàn)二叉樹的方法是什么”文章吧。
創(chuàng)新互聯(lián)堅持“要么做到,要么別承諾”的工作理念,服務(wù)領(lǐng)域包括:網(wǎng)站制作、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù),滿足客戶于互聯(lián)網(wǎng)時代的長樂網(wǎng)站設(shè)計、移動媒體設(shè)計的需求,幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴!
什么是二叉樹
二叉樹是由若干個節(jié)點(diǎn)組成的,每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)。它有三個屬性:
節(jié)點(diǎn)值
左子樹指針
右子樹指針
二叉樹分為以下幾類:
滿二叉樹:除了葉節(jié)點(diǎn),其他節(jié)點(diǎn)都有兩個子節(jié)點(diǎn)
完全二叉樹:如果二叉樹的深度為d,除了第d層,其他層都是滿的,而且在第d層上,所有的葉子節(jié)點(diǎn)都在左邊連續(xù)的位置
二叉搜索樹:左子樹所有節(jié)點(diǎn)小于根節(jié)點(diǎn)值,右子樹所有節(jié)點(diǎn)值大于根節(jié)點(diǎn)值
實現(xiàn)二叉樹
我們可以用類來定義二叉樹結(jié)構(gòu)。每個節(jié)點(diǎn)都是一個對象,包含以下屬性:
value:節(jié)點(diǎn)值
left:左子樹指針
right:右子樹指針
創(chuàng)建一個類來表示節(jié)點(diǎn)。
class Node {
public $value;
public $left;
public $right;
function __construct($value){
$this -> value = $value;
$this -> left = null;
$this -> right = null;
}
}
接下來,我們需要創(chuàng)建一個類來表示二叉樹。
class BinarySearchTree {
public $root;
function __construct() {
$this -> root = null;
}
}
接下來,我們將定義以下二叉樹的方法:
insert(value):將值插入二叉樹
search(value):查找二叉樹中的值
delete(value):從二叉樹中刪除值
插入節(jié)點(diǎn)
插入節(jié)點(diǎn)方法將插入新節(jié)點(diǎn)到正確的位置。如果樹為空,新節(jié)點(diǎn)是根節(jié)點(diǎn)。否則,我們開始從根節(jié)點(diǎn)比較當(dāng)前節(jié)點(diǎn)的值。
如果新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值,則我們將新節(jié)點(diǎn)插入左子樹。
如果新節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值,則我們將新節(jié)點(diǎn)插入右子樹。
如果新節(jié)點(diǎn)的值等于當(dāng)前節(jié)點(diǎn)的值,則節(jié)點(diǎn)已經(jīng)存在,不需要插入。
這是插入方法的代碼:
function insert($value) {
$newNode = new Node($value);
if ($this -> root == null) {
$this -> root = $newNode;
} else {
$current = $this -> root;
while (true) {
if ($value < $current -> value) {
if ($current -> left == null) {
$current -> left = $newNode;
return;
} else {
$current = $current -> left;
}
} else if ($value > $current -> value) {
if ($current -> right == null) {
$current -> right = $newNode;
return;
} else {
$current = $current -> right;
}
} else {
return;
}
}
}
}
查找節(jié)點(diǎn)
查找節(jié)點(diǎn)方法是一個簡單的遞歸方法。從根節(jié)點(diǎn)開始比較節(jié)點(diǎn)的值。如果值相等,返回當(dāng)前節(jié)點(diǎn)。否則,如果節(jié)點(diǎn)的值小于要查找的值,則繼續(xù)查找左子樹。如果值大于要查找的值,則繼續(xù)查找右子樹。
這是查找方法的代碼:
function search($value) {
$current = $this -> root;
while ($current != null) {
if ($value == $current -> value) {
return $current;
} else if ($value < $current -> value) {
$current = $current -> left;
} else {
$current = $current -> right;
}
}
return null;
}
刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)方法是整個實現(xiàn)中最復(fù)雜的方法之一。如何刪除節(jié)點(diǎn)取決于節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)??梢杂幸韵聨追N情況:
節(jié)點(diǎn)是葉子節(jié)點(diǎn),沒有子節(jié)點(diǎn)。直接刪除節(jié)點(diǎn)。
節(jié)點(diǎn)只有一個子節(jié)點(diǎn)。將子節(jié)點(diǎn)替換為該節(jié)點(diǎn)。
節(jié)點(diǎn)有兩個子節(jié)點(diǎn)。找到節(jié)點(diǎn)右子樹中的最小值,將最小值替換為該節(jié)點(diǎn),并從右子樹中刪除最小值。
這是刪除方法的代碼:
function delete($value) {
$current = $this -> root;
$parent = null;
while ($current != null) {
if ($value == $current -> value) {
if ($current -> left == null && $current -> right == null) {
if ($parent == null) {
$this -> root = null;
} else {
if ($parent -> left == $current) {
$parent -> left = null;
} else {
$parent -> right = null;
}
}
} else if ($current -> left == null) {
if ($parent == null) {
$this -> root = $current -> right;
} else {
if ($parent -> left == $current) {
$parent -> left = $current -> right;
} else {
$parent -> right = $current -> right;
}
}
} else if ($current -> right == null) {
if ($parent == null) {
$this -> root = $current -> left;
} else {
if ($parent -> left == $current) {
$parent -> left = $current -> left;
} else {
$parent -> right = $current -> left;
}
}
} else {
$replacementNode = $current -> right;
while ($replacementNode -> left != null) {
$replacementNode = $replacementNode -> left;
}
$removeValue = $replacementNode -> value;
$this -> delete($replacementNode -> value);
$current -> value = $removeValue;
}
return;
} else if ($value < $current -> value) {
$parent = $current;
$current = $current -> left;
} else {
$parent = $current;
$current = $current -> right;
}
}
}
以上就是關(guān)于“php實現(xiàn)二叉樹的方法是什么”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對大家有幫助,若想了解更多相關(guān)的知識內(nèi)容,請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
網(wǎng)站欄目:php實現(xiàn)二叉樹的方法是什么
新聞來源:http://muchs.cn/article8/ihdcip.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供響應(yīng)式網(wǎng)站、定制開發(fā)、外貿(mào)建站、網(wǎng)站制作、軟件開發(fā)、微信公眾號
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)