您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)PHP如何實(shí)現(xiàn)自排序二叉樹,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
在節(jié)點(diǎn)之間再應(yīng)用一些排序邏輯,二叉樹就能提供出色的組織方式。對(duì)于每個(gè)節(jié)點(diǎn),都讓滿足所有特定條件的元素都位于左節(jié)點(diǎn)及其子節(jié)點(diǎn)。在插入新元素時(shí),我們需要從樹的第一個(gè)節(jié) 點(diǎn)(根節(jié)點(diǎn))開始,判斷它屬于哪一側(cè)的節(jié)點(diǎn),然后沿著這一側(cè)找到恰當(dāng)?shù)奈恢?,類似地,在讀取數(shù)據(jù)時(shí),只需要使用按序遍歷方法來遍歷二叉樹。
復(fù)制代碼 代碼如下:
<?php
ob_start();
// Here we need to include the binary tree class
Class Binary_Tree_Node() {
// You can find the details at
}
ob_end_clean();
// Define a class to implement self sorting binary tree
class Sorting_Tree {
// Define the variable to hold our tree:
public $tree;
// We need a method that will allow for inserts that automatically place
// themselves in the proper order in the tree
public function insert($val) {
// Handle the first case:
if (!(isset($this->tree))) {
$this->tree = new Binary_Tree_Node($val);
} else {
// In all other cases:
// Start a pointer that looks at the current tree top:
$pointer = $this->tree;
// Iteratively search the tree for the right place:
for(;;) {
// If this value is less than, or equal to the current data:
if ($val <= $pointer->data) {
// We are looking to the left ... If the child exists:
if ($pointer->left) {
// Traverse deeper:
$pointer = $pointer->left;
} else {
// Found the new spot: insert the new element here:
$pointer->left = new Binary_Tree_Node($val);
break;
}
} else {
// We are looking to the right ... If the child exists:
if ($pointer->right) {
// Traverse deeper:
$pointer = $pointer->right;
} else {
// Found the new spot: insert the new element here:
$pointer->right = new Binary_Tree_Node($val);
break;
}
}
}
}
}
// Now create a method to return the sorted values of this tree.
// All it entails is using the in-order traversal, which will now
// give us the proper sorted order.
public function returnSorted() {
return $this->tree->traverseInorder();
}
}
// Declare a new sorting tree:
$sort_as_you_go = new Sorting_Tree();
// Let's randomly create 20 numbers, inserting them as we go:
for ($i = 0; $i < 20; $i++) {
$sort_as_you_go->insert(rand(1,100));
}
// Now echo the tree out, using in-order traversal, and it will be sorted:
// Example: 1, 2, 11, 18, 22, 26, 32, 32, 34, 43, 46, 47, 47, 53, 60, 71,
// 75, 84, 86, 90
echo '<p>', implode(', ', $sort_as_you_go->returnSorted()), '</p>';
?>
關(guān)于“PHP如何實(shí)現(xiàn)自排序二叉樹”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。