关于php:数据结构PHP-实现二分搜索树

42次阅读

共计 6513 个字符，预计需要花费 17 分钟才能阅读完成。

这篇文章是介绍 二叉树  和  二分搜寻树 ，而后通过 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…

扫码关注爱因诗贤

​

正文完
php
发表至： php
2020-10-23
 0
关于php:反射
关于php:基于NginxPHP实现的带权限验证的静态文件服务器如某些情景需要校验参数后才能返回资源或者缩略图生成等
关于php:Mac-M1Pro-安装-PHP-开发环境
关于php:test1