PHP排序二叉树基本功能实现方法示例
作者:Oops_Qu 发布时间:2023-07-10 04:45:53
标签:PHP,排序二叉树
本文实例讲述了PHP排序二叉树基本功能实现方法。分享给大家供大家参考,具体如下:
这里演示了排序二叉树节点的插入,中序遍历,极值的查找和特定值的查找的功能.
基本没有提供什么概念和定义.建议先简单了解一下本文提供的几个概念在来看本文.
实际上,只是简单的提供了代码,注释也很少,各位辛苦了.
二叉树:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。
排序二叉树: 左孩子节点的值小于父节点的值,右孩子节点的值大于父节点的值.
几个概念:
根节点
叶子节点
左子树
右子树
中序遍历
前序遍历
后序遍历
二叉树查找
中序遍历:
先遍历左子树,在遍历本节点,在遍历右节点.遍历之后的结果就是排序好之后的结果
// created by 曲朋维
// 排序二叉树
// 完成以下任务.
// 1. 将节点插入到对应位置
// 2. 使用中序遍历遍历这个二叉树
// 3. 找到这个二叉树的极值
// 4. 搜索一个特定的值
class Node{
public $key,$left,$right;
public function __construct($key)
{
$this->key = $key;
}
}
class BinaryTree{
public $root;
public $sortArr = [];
// 插入节点
public function insertNode($node,$newNode){
if ($node->key < $newNode->key){
// 如果父节点小于子节点,插到右边
if (empty($node->right)){
$node->right = $newNode;
}else{
$this->insertNode($node->right,$newNode);
}
}elseif ($node->key > $newNode->key){
// 如果父节点大于子节点,插到左边
if (empty($node->left)){
$node->left = $newNode;
}else{
$this->insertNode($node->left,$newNode);
}
}
}
public function insert($key){
$newNode = new Node($key);
if (empty($this->root)){
$this->root = $newNode;
}else{
$this->insertNode($this->root,$newNode);
}
}
// 中序遍历
public function midSort(){
$this->midSortNode($this->root);
}
public function midSortNode($node){
if (!empty($node)){
$this->midSortNode($node->left);
array_push($this->sortArr,$node->key);
$this->midSortNode($node->right);
}
}
// 寻找极值
public function findMin(){
//不断的找它的左子树,直到这个左子树的节点为叶子节点.
if (!empty($this->root)){
$this->findMinNode($this->root);
}
}
public function findMinNode(Node $node){
if (!empty($node->left)){
$this->findMinNode($node->left);
}else{
echo '这个二叉树的最小值为:'.$node->key;
}
}
public function findMax(){
if (!empty($this->root)){
$this->findMaxNode($this->root);
}
}
public function findMaxNode(Node $node){
if (!empty($node->right)){
$this->findMaxNode($node->right);
}else{
echo '这个二叉树的最大值为:'.$node->key;
}
}
// 查找特定的值
public function find($val = ''){
if (!empty($val)){
$this->findNode($this->root,$val);
}
}
public function findNode(Node $node,$val){
if ($node->key == $val){
echo '找到'.$val.'了';
}else if ($node->key > $val){
// 如果 父节点的值 大于要查找的值,那么查找它的左子树
if (!empty($node->left)){
$this->findNode($node->left,$val);
}else{
echo '没有这个东西!';
}
}else if ($node->key < $val){
if (!empty($node->right)){
$this->findNode($node->right,$val);
}else{
echo '没有这个东西!';
}
}
}
}
$tree = new BinaryTree();
// 节点插入
$nodes = array(8,3,10,1,6,14,4,7,13);
foreach ($nodes as $value){
$tree->insert($value);
}
// 中序遍历
//$tree->midSort();
//print_r($tree->sortArr);
// 寻找极值
//$tree->findMin();
//$tree->findMax();
// 查找特定的值
$tree->find(7);
echo "<br/>";
$tree->find(11);
运行结果:
找到7了
没有这个东西!
希望本文所述对大家PHP程序设计有所帮助。
来源:https://blog.csdn.net/oops_qu/article/details/78280906


猜你喜欢
- 为了实现将RAW格式照片一键改变整体风格,且有多种风格选择,我们可以使用神经风格迁移技术。神经风格迁移是一种基于深度学习的方法,可以将一张图
- 现在的域名提供已经取消免费的url转发功能,而且我们一般主要用的是带www的域名,以前不带www的域名一般是做url转发跳转到带www的域名
- 1.删除 1)删除记录 Delete from 表名 where id ='xx' 2)
- <script language="vbscript" runat="s
- 一、获取文件路径实现1.1 获取当前文件路径import oscurrent_file_path = __file__print(f&quo
- 当我们在Vue.js项目中引用图片时,关于图片路径有以下几种情形:使用一我们在data里面定义好图片路径imgUrl:'../ass
- ASP(英文全称Active Server Pages)是一个编程环境,在其中,可以混合使用HTML、脚本语言以及组件来创建服务器端功能强大
- 题目:CSV格式清洗与转换描述附件是一个CSV格式文件,提取数据进行如下格式转换:
- 目录实验环境准备API 寻找 && 提取代码实现项目链接我身边的很多小伙伴们在朋友圈里面晒着出去游玩的照片,简直了,人多的不
- 原数据lambda函数处理我之前写了各种if substr函数,各种报错正确到热泪盈眶的函数data['Followers/Fans
- 使用python实现双向循环链表,供大家参考,具体内容如下双向循环链表: 将所有的数据存放到节点中,每一个节点相连接,首尾链接,每一个节点中
- 1.首先在Xshell上通过conda创建新的虚拟环境2.此时在 /home/y210101004/.conda/envs下多了刚
- 首先简单介绍一下通配符,用来匹配值的一部分的特殊字符。搜索模式(search pattern) 由字面值、通配符或两者组合构成的
- 目录需求背景思路分析UI展示开始使用一 编写支付组件模板二 支付组件的JS相关代码和说明附:组件JS完整的源码需求背景市场报告列表展示的报告
- Go 在testing包中内置测试命令go test,提供了最小化但完整的测试体验。标准工具链还包括基准测试和基于代码覆盖的语句,类似于NC
- 实验目的:用户输入网卡名称,通过函数返回对应的IPv4和IPv6地址。实验代码:步骤一: 由于window系统下网卡名称并不是真正的名字,而
- 1、场景描述通常来说,前端要拿到excel数据,都是先上传存储数据库,然后再请求后端接口,获取数据。但有100个产品经理,就会有101个不同
- 这个javascript农历日历,万年历代码网上看到的,很不错,功能齐全,值得收藏!功能介绍:动态显示当前世界各国各时区时间,显示当前农历,
- python 字符串切割 maxsplitmy_str.split(str1, maxsplit)str1 可以不写,默认是空白字符(&qu
- 请问论坛的树状记录表是怎么展开的?如何做?论坛的这种展开技术一般采用两种方法实现,一种是采用递归的方法,优点是逻辑简单,编程简单,缺点是速度