1. 首页
  2. PHP
  3. 数据结构-PHP 实现二分搜索树

数据结构-PHP 实现二分搜索树

码农天地 -
数据结构-PHP 实现二分搜索树

这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。

1.二叉树1.1 二叉树图示

1.2 二叉树节点定义
//二叉树具有唯一根节点
class Node{
    $e; //节点元素
    $left; //左儿子
    $right;//右儿子
}
Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。1.3 二叉树的特点二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。二叉树不一定是满的，可能只有左儿子或又儿子。一个节点或 NULL 也可以看做一个二叉树。2.二分搜索树2.1 二分搜索树特点二分搜索树是二叉树。每个节点的元素的值都要大于左儿子所有节点的值。每个节点的元素的值都要小于右儿子所有节点的值。每个子树也是二分搜索树。二分搜索树查询速度快。存储的元素必须要有比较性。2.2 二分搜索树图示

2.3 PHP 代码定义节点
class Node
{
    public $e;
    public $left = null;
    public $right = null;
    /**
     * 构造函数 初始化节点数据
     * Node constructor.
     * @param $e
     */
    public function __construct($e) {
        $this->e = $e;
    }
}
2.4 向二分搜索树添加元素

下面展示的的使用递归思想向二分搜索树添加元素，其中 add($e) 方法表示想二分搜索树添加元素 $e，recursionAdd(Node $root, $e) 是一个递归函数，表示使用递归向二分搜索树添加元素：

 /**
     * 向二分搜索树添加元素
     * @param $e
     */
    public function add($e) {
        $this->root = $this->recursionAdd($this->root, $e);
    }
    /**
     * 递归向二分搜索树添加元素
     * @param Node $root
     * @param $e
     */
    public function recursionAdd(Node $root, $e) {
        if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息
            $this->size++;
            $root = new Node($e);
        } elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素
            $root->left = $this->recursionAdd($root->left, $e);
        } elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素
            $root->right = $this->recursionAdd($root->right, $e);
        } //若元素等于当前节点元素 则什么都不做
    }
Tips：这里的二分搜索树不包含重复元素，如果想要包含重复元素，可以定义每个左儿子所有元素小于等于父亲节点，或者每个节点右儿子所有节点元素大于等于父亲节点。2.5 查询二分搜索树是否包含某个元素

下面展示的的使用递归思想查询二分搜索树元素是否包含某个元素，其中 contains($e) 方法表示查询二分搜索树是否包含元素 $e，recursionContains(Node $root, $e) 是一个递归函数，表示使用递归查询二分搜索树元素：

 /**
     * 判断二分搜索树是否包含某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool {
        return $this->recursionContains($this->root, $e);
    }
    /**
     * 递归判断二分搜索树是否包含某元素
     * @param $root
     * @param $e
     * @return bool
     */
    private function recursionContains(Node $root, $e): bool {
        if ($root == null) { //若当前节点为空 则表示不存在元素 $e
            return false;
        } elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e
            return true;
        } elseif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点
            return $this->recursionContains($root->left, $e);
        } else {  //若 $e 大于当前节点元素，则去右儿子树递归查询是否包含节点
            return $this->recursionContains($root->right, $e);
        }
    }
Tips：递归的时候会比较元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的位置就是判断是否包含元素是否存在的依据。2.6 二分搜索树前序遍历

前序遍历操作就是把所有节点都访问一次，前序遍历 是先访问节点，再递归遍历左儿子树，然后再递归遍历右儿子树：

 /**
     * 前序遍历
     */
    public function preTraversal() {
        $this->recursionPreTraversal($this->root, 0);
    }
    /**
     * 前序遍历的递归
     */
    public function recursionPreTraversal($root, $sign_num) {
        echo $this->getSign($sign_num);//打印深度
        if ($root == null) {
            echo "null<br>";
            return;
        }
        echo $root->e . "<br>"; //打印当前节点元素
        $this->recursionPreTraversal($root->left, $sign_num + 1);
        $this->recursionPreTraversal($root->right, $sign_num + 1);
    }

下面是打印结果:

<?php
require 'BinarySearchTree.php';
$binarySearchTree = new BinarySearchTree();
$binarySearchTree->add(45);
$binarySearchTree->add(30);
$binarySearchTree->add(55);
$binarySearchTree->add(25);
$binarySearchTree->add(35);
$binarySearchTree->add(50);
$binarySearchTree->add(65);
$binarySearchTree->add(15);
$binarySearchTree->add(27);
$binarySearchTree->add(31);
$binarySearchTree->add(48);
$binarySearchTree->add(60);
$binarySearchTree->add(68);
//下面是预期想要的结果
/**
 *                     45
 *           /                   
 *          30                   55
 *        /                    /    
 *      25       35         50       65
 *     /       /          /       /   
 *   15   27  31         48       60     68
 *
 */
$binarySearchTree->preTraversal();
/**
打印输出
45
-----30
----------25
---------------15
--------------------null
--------------------null
---------------27
--------------------null
--------------------null
----------35
---------------31
--------------------null
--------------------null
---------------null
-----55
----------50
---------------48
--------------------null
--------------------null
---------------null
----------65
---------------60
--------------------null
--------------------null
---------------68
--------------------null
--------------------null
 */
Tips：可以看到打印输出结果和预期一致。2.7 二分搜索树中序遍历

遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历右儿子树，再访问节点，然后再递归遍历右儿子树，最后的顺序输出结果是有序的：

 /**
     * 中序遍历
     */
    public function midTraversal() {
        $this->recursionMidTraversal($this->root, 0);
    }
    /**
     * 中序遍历的递归
     */
    public function recursionMidTraversal($root, $sign_num) {
        if ($root == null) {
            echo $this->getSign($sign_num);//打印深度
            echo "null<br>";
            return;
        }
        $this->recursionMidTraversal($root->left, $sign_num + 1);
        echo $this->getSign($sign_num);//打印深度
        echo $root->e . "<br>";
        $this->recursionMidTraversal($root->right, $sign_num + 1);
    }

下面是打印结果:

<?php
require 'BinarySearchTree.php';
$binarySearchTree = new BinarySearchTree();
$binarySearchTree->add(45);
$binarySearchTree->add(30);
$binarySearchTree->add(55);
$binarySearchTree->add(25);
$binarySearchTree->add(35);
$binarySearchTree->add(50);
$binarySearchTree->add(65);
$binarySearchTree->add(15);
$binarySearchTree->add(27);
$binarySearchTree->add(31);
$binarySearchTree->add(48);
$binarySearchTree->add(60);
$binarySearchTree->add(68);
//下面是预期想要的结果
/**
 *                     45
 *           /                   
 *          30                   55
 *        /                    /    
 *      25       35         50       65
 *     /       /          /       /   
 *   15   27  31         48       60     68
 *
 */
$binarySearchTree->midTraversal();
/**
打印输出
--------------------null
---------------15
--------------------null
----------25
--------------------null
---------------27
--------------------null
-----30
--------------------null
---------------31
--------------------null
----------35
---------------null
45
--------------------null
---------------48
--------------------null
----------50
---------------null
-----55
--------------------null
---------------60
--------------------null
----------65
--------------------null
---------------68
--------------------null
 */
Tips：可以看到打印输出结果和预期一致，但是此时的遍历顺序变了，最后的顺序输出结果是有序的。2.8 二分搜索树后序遍历

遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历左儿子树，然后再递归遍历右儿子树，再访问节点：

 /**
     * 后序遍历
     */
    public function rearTraversal() {
        $this->recursionRearTraversal($this->root, 0);
    }
    /**
     * 后序遍历的递归
     */
    public function recursionRearTraversal($root, $sign_num) {
        if ($root == null) {
            echo $this->getSign($sign_num);//打印深度
            echo "null<br>";
            return;
        }
        $this->recursionRearTraversal($root->left, $sign_num + 1);
        $this->recursionRearTraversal($root->right, $sign_num + 1);
        echo $this->getSign($sign_num);//打印深度
        echo $root->e . "<br>";
    }

下面是打印结果:

<?php
require 'BinarySearchTree.php';
$binarySearchTree = new BinarySearchTree();
$binarySearchTree->add(45);
$binarySearchTree->add(30);
$binarySearchTree->add(55);
$binarySearchTree->add(25);
$binarySearchTree->add(35);
$binarySearchTree->add(50);
$binarySearchTree->add(65);
$binarySearchTree->add(15);
$binarySearchTree->add(27);
$binarySearchTree->add(31);
$binarySearchTree->add(48);
$binarySearchTree->add(60);
$binarySearchTree->add(68);
//下面是预期想要的结果
/**
 *                     45
 *           /                   
 *          30                   55
 *        /                    /    
 *      25       35         50       65
 *     /       /          /       /   
 *   15   27  31         48       60     68
 *
 */
$binarySearchTree->rearTraversal();
/**
打印输出
--------------------null
--------------------null
---------------15
--------------------null
--------------------null
---------------27
----------25
--------------------null
--------------------null
---------------31
---------------null
----------35
-----30
--------------------null
--------------------null
---------------48
---------------null
----------50
--------------------null
--------------------null
---------------60
--------------------null
--------------------null
---------------68
----------65
-----55
45
 */

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

​

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
更多关于php的阅读
上一篇： 电商系统设计之运费模板（下）
下一篇： php怎么删除最后一个字符

Tags 标签

php算法程序员

扩展阅读

隐藏apache版本信息
2018-09-30 10:56:15 []
CentOS 6.5安装php5.6
2018-09-30 11:36:53 []
PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []
CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []
PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []
PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []
Linux php: command not found
2020-02-05 01:30:13 []
php 缓冲区 buffer 原理
2020-06-28 19:09:43 []
PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []

加个好友，技术交流

1628738909466805.jpg

码农天地

首页 HTML/CSS WEB服务器 PHP Linux 数据库 异常报错 插件工具 美文欣赏 站长直荐
友情链接：码农天地爱厂家深圳钻石回收麦思会议

Copyright © 2019-2024| 沪ICP备19030844号-2 | SiteMap