PHP排序二叉树基本功能实现方法示例

2024-07-28 20:53:29

本文实例讲述了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相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就
PHP实现从上往下打印二叉树的方法

本文实例讲述了PHP实现从上往下打印二叉树的方法.分享给大家供大家参考,具体如下: 问题从上往下打印出二叉树的每个节点,同层节点从左至右打印. 解决思路每层树从左到右打印,所以需要将节点的左右子树存起来,因为先进先出,所以用队列. 实现代码 /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树中序遍历:左子树->根节点->右子树后序遍历:左子树->右子树->根节点广度优先遍历:又叫层次遍历,从上往下对每一层依
PHP实现判断二叉树是否对称的方法

本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func
php实现二叉树中和为某一值的路径方法

二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 思路: 1.二叉树的前序遍历,中左右顺序 2.把目标值target传进去,target-=val 3.target为0并且left和right都为null,达到叶结点 4.函数外部两个数组,list数组存一条路径,listAll数组存所有路径 FindPath(roo
PHP完全二叉树定义与实现方法示例

本文实例讲述了PHP完全二叉树定义与实现方法.分享给大家供大家参考,具体如下: 若设二叉树的深度为h,除第 h 层外,其它各层 (1-h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树. PHP代码实现(暂时实现添加节点.层次遍历节点,删除节点后续更新) <?php class Node{ public $value; public $leftNode; public $rightNode; } /* 找到空节点 */ function findEmpyt
PHP实现按之字形顺序打印二叉树的方法

本文实例讲述了PHP实现按之字形顺序打印二叉树的方法.分享给大家供大家参考,具体如下: 问题请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 解决思路使用两个栈实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的
PHP获取二叉树镜像的方法

本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$
PHP排序二叉树基本功能实现方法示例

本文实例讲述了PHP排序二叉树基本功能实现方法.分享给大家供大家参考,具体如下: 这里演示了排序二叉树节点的插入,中序遍历,极值的查找和特定值的查找的功能. 基本没有提供什么概念和定义.建议先简单了解一下本文提供的几个概念在来看本文. 实际上,只是简单的提供了代码,注释也很少,各位辛苦了. 二叉树:在计算机科学中,二叉树是每个节点最多有两个子树的树结构. 排序二叉树: 左孩子节点的值小于父节点的值,右孩子节点的值大于父节点的值. 几个概念: 根节点叶子节点左子树右子树中序遍历前序遍历
thinkPHP5框架实现分页查询功能的方法示例

本文实例讲述了thinkPHP5框架实现分页查询功能的方法.分享给大家供大家参考,具体如下: controller文件内Admin.php <?php namespace app\admin\controller; use think\Controller; use app\admin\model\Admin as AdminModel; //使用分页类取别名解决类名冲突 class Admin extends Controller{ public function lst(){ /* 分页开
使用PyQt的QLabel组件实现选定目标框功能的方法示例

问题背景基于PyQt5开发了一个可以用于目标跟踪的软件,在开发过程中遇到一个问题,就是如何在PyQt5的组件QLable中自主选定目标框,这个在opencv里面有专门的函数完成这个工作:cv2.selectROI(),我的目的就是在QLabel的基础上,实现类似函数cv2.selectROI()的功能,这样在运行程序的过程中,就能在视频框里面直接选取感兴趣区域.直接贴出实现的最终效果: 上图中的红色框框就是在QLabel的基础上实现的功能. 实现思路具体要实现的功能是,在视频显示区域
Java调用微信支付功能的方法示例代码

Java 使用微信支付前言百度搜了一下微信支付,都描述的不太好,于是乎打算自己写一个案例,希望以后拿来直接改造使用. 因为涉及二维码的前端显示,所以有前端的内容一. 准备工作所需微信公众号信息配置 APPID:绑定支付的APPID(必须配置) MCHID:商户号(必须配置) KEY:商户支付密钥,参考开户邮件设置(必须配置) APPSECRET:公众帐号secert(仅JSAPI支付的时候需要配置) 我这个案例用的是尚硅谷一位老师提供的,这里不方便提供出来,需要大家自己找,或者公司提供二
thinkphp框架无限级栏目的排序功能实现方法示例

本文实例讲述了thinkphp框架无限级栏目的排序功能实现方法.分享给大家供大家参考,具体如下: 题目中我们并没有说明是tp5的无限级排序还是tp3的无限级排序就是为了让小新手们明白,这些功能的实现跟你使用的框架是没有关系的,不管你是tp5还是tp3还是laravel还是yii框架都没有关系,我们强调的是思路,是解决问题的方法,演示的时候因为我在用tp3所以无所谓了. 无限级栏目的排序非常简单,这次以博文的方式分享给大家解决的思路. 上图: 上图是我们实现的无限级分类,我们要注意两个字段,id和
JS二叉树的简单实现方法示例

本文实例讲述了JS二叉树的简单实现方法.分享给大家供大家参考,具体如下: 今天学习了一下二叉树的实现,在此记录一下简单的二叉树实现,并且实现升序和降序排序输出 function Node(data , left,right){ this.data = data; this.left = left; this.right = right; this.show = show; function show(){ return this.data; } }; function Bst(){ this
Bootstrap table 服务器端分页功能实现方法示例

本文实例讲述了Bootstrap table 服务器端分页功能实现方法.分享给大家供大家参考,具体如下: bootstrap版本为 3.X bootstrap-table.min.css bootstrap-table-zh-CN.min.js bootstrap-table.min.js 前端bootstrap+jQuery,服务端使用spring MVC实现restful风格服务前端代码块 <table id="test-table" class="col-xs
JS通过调用微信API实现微信支付功能的方法示例

本文实例讲述了JS通过调用微信API实现微信支付功能的方法.分享给大家供大家参考,具体如下: 最近在做微信公众号开发,在微信支付上遇到一些问题,困惑了3天,今天终于搞定.期间要感谢一些大神的帮助,趁热下面分享一下我的经验. 在实现微信支付之前,需要到微信开发平台认证,这些认证和配置信息我就不多说了,这里主要从代码层面实现支付. function onBridgeReady(){ WeixinJSBridge.invoke( 'getBrandWCPayRequest', { "appId&quo
thinkPHP多表查询及分页功能实现方法示例

本文实例讲述了thinkPHP多表查询及分页功能实现方法.分享给大家供大家参考,具体如下: 项目业务逻辑为:教师上传试卷,设置答题卡,发布答题卡给相关的班级或群组,只有试卷关联的答题卡发布后,该试卷才能在系统试卷中搜索到,同时其他的老师也可以收藏.在前端的收藏模块中,有个业务是给个input框以提供搜索功能给用户,但是在事先设计的搜索表中,只有一处试卷ID是和试卷表关联的,如果用户搜索试卷题目那岂不要两表查询了,一开始我想到的方法是在收藏表中多加个字段,也就是把试卷题目的字段添加到收藏表中,业务
Java操作redis实现增删查改功能的方法示例

本文实例讲述了Java操作redis实现增删查改功能的方法.分享给大家供大家参考,具体如下: 首先,我们需要在windows下配置一个redis环境,具体配置教程请看:http://www.jb51.net/article/96230.htm 然后需要导入:jedis-2.7.3.jar这个包,看如下代码: package redis.main; import redis.clients.jedis.Jedis; import redis.clients.jedis.JedisPool; imp

PHP排序二叉树基本功能实现方法示例

相关推荐

随机推荐