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
0
投稿
猜你喜欢
- 本章的前面讨论如何使用SQL向一个表中插入数据。但是,如果你需要向一个表中添加许多条记录,使用SQL语句输入数据是很不方便的。幸运的是,My
- PDOStatement::getColumnMetaPDOStatement::getColumnMeta — 返回结果集中一列的元数据(
- 第一:编写限制搜索范围的查询语句。众所周知,在数据库查询的时候返回记录的多少直接关系到查询的效率。所以,在客户端通过一定的条件语句,限制搜索
- 内容摘要:严格地说,ASP 并不是一门编程语言,所以不存在类这一概念,我们这里说 ASP 类是指 A
- 一、单字节SQL注入MYSQL的SQL注入已经由来已久,以下是普遍采用的注入步骤:1、在GET参数上加一个/*或者#(mysql专有的注释)
- 你的SQL Server最近是否运行不正常?不,我指的不是我们肯定会遇到的通常的数据库和操作系统问题。我的意思是,你是否经历过服务器的反应迟
- 前言责任链模式(Chain of Responsibility Pattern)是什么?责任链模式是一种行为型模式,它允许多个对象将请求沿着
- 内容摘要合理使用渐变留白网格布局提高字体应用明确而有效的导航设计漂亮、有用的页脚介绍优秀设计和卓越设计之间的区别是比较小的。一般人可能无法解
- PDO::_constructPDO::_construct — 创建一个表示数据库连接的 PDO 实例(PHP 5 >= 5.1.0
- 数据库计算机 databasecomputer 实现数据库的存储、管理和控制的一种专用计算机系统。它能十分快速而有效地完成各种数据库操作,并
- 由于特定需求,最近实验室需要远程连接外地的sql server 2000服务器,最开始怎么连也连不上,出现了很多问题,但是在今天上午,借用实
- 我在传递数据的时候老是出错,请问如何处理?不管是什么数据库,一般来说,是它所包含引号的字符串带来的问题。假设我们使用名为“strDate”的
- 一个简单的例子:将如下代码另存为.wsc文件,并右键“注册”(卸载时右键“不注册”)。<Component> <regis
- 近年来,广告已成为很多网站的主要收入来源。不久前,在线广告往往遭到访客的拒绝,广告客户也不确定它的价值和效力。今天,大多数访客期望在商业网站
- 在本文中,我将说明如何用SQL Server的工具来优化数据库索引的使用,本文还涉及到有关索引的一般性知识。 关于索引的常识 影响到数据
- ps:大多与c等编程语言极为相似一、if分支if:给定一个条件,同时为该条件设置多种(一般两种)情况,然后通过条件判断来实现具体的执行段复合
- 注意:安装时要保证Oracle安装目录不能带有中文字符(如果第一次安装出现“加载数据库错误areasQueries”的错误,一般是因为Ora
- 这是来自于Steven D编写的WEB前端开发设计要点的内容。虽然许多设计师已非常熟练的使用了Web标准,让人遗憾的是有很多细节的排版处理仍
- 很多网友在经典论坛里说自己的网站为什么色彩上总是有问题,总是看起来没什么精神,没办法吸引人注意。小毅观察了一些网友们设计的网站发现他们在用色
- Microsoft® SQL Server™ 2000 由一系列产品组成,不仅能够满足最大的数据处理系统