PHP Class&Object -- PHP 自排序二叉树的深入解析
时间:2024-06-05 09:48:33
在节点之间再应用一些排序逻辑,二叉树就能提供出色的组织方式。对于每个节点,都让满足所有特定条件的元素都位于左节点及其子节点。在插入新元素时,我们需要从树的第一个节 点(根节点)开始,判断它属于哪一侧的节点,然后沿着这一侧找到恰当的位置,类似地,在读取数据时,只需要使用按序遍历方法来遍历二叉树。
<?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>';
?>
标签:PHP,自排序,二叉树
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Go语言并发技术详解
2024-02-14 16:49:22
一文详解Python中logging模块的用法
2022-03-27 23:09:38
Python+selenium破解拼图验证码的脚本
2023-11-22 05:24:05
![](https://img.aspxhome.com/file/2023/1/80661_0s.jpg)
Go语言Goroutinue和管道效率详解
2024-02-02 18:19:09
![](https://img.aspxhome.com/file/2023/5/113075_0s.jpg)
Mootools常用方法扩展(二)
2009-01-11 18:22:00
解决缩小图标变样问题
2007-10-08 19:13:00
![](https://img.aspxhome.com/file/UploadPic/200710/8/2007108191659246s.png)
分享一个超好用的php header下载函数
2023-09-03 21:31:43
基于bootstrop常用类总结(推荐)
2024-04-17 09:52:42
![](https://img.aspxhome.com/file/2023/2/136472_0s.png)
使用django和vue进行数据交互的方法步骤
2021-12-20 03:29:07
数据库工具sysbench安装教程和性能测试例子
2024-01-28 06:00:42
PHP实现表单处理方法详解
2023-05-25 07:39:18
keras获得model中某一层的某一个Tensor的输出维度教程
2023-12-15 11:28:54
python图像和办公文档处理总结
2021-03-08 19:24:02
![](https://img.aspxhome.com/file/2023/5/72875_0s.png)
python 基于TCP协议的套接字编程详解
2023-09-11 21:09:30
Python3.5集合及其常见运算实例详解
2023-04-25 04:04:33
浅谈Python几种常见的归一化方法
2021-01-22 16:36:45
![](https://img.aspxhome.com/file/2023/4/66824_0s.gif)
SQL Server误区30日谈 第12天 TempDB的文件数和需要和CPU数目保持一致
2024-01-21 19:07:29
MySQL安装starting the server失败的2种解决办法(推荐!)
2024-01-28 11:16:09
![](https://img.aspxhome.com/file/2023/5/115545_0s.png)
python打开windows应用程序的实例
2021-08-22 09:49:40
Python 爬虫图片简单实现
2023-08-30 15:43:10