二分搜索树介绍&PHP 定义节点

码农天地 - 2020-10-22 09:59:05

---

这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树(Binary Search Tree) 的节点。

1.二叉树1.1 二叉树图示

1.2 二叉树节点定义

//二叉树具有唯一根节点
class Node{
    $e; //节点元素
    $left; //左儿子
    $right;//右儿子
}

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

2.3 PHP 代码定义节点

<?php
class BinarySearchTree
{
    private $root;
    private $size;
    /**
     * 构造函数 初始化二分搜索树
     * BinarySearchTree constructor.
     */
    public function __construct() {
        $this->root = null;
        $this->size;
    }
    /**
     * 获取当前搜索树元素个数
     * @return mixed
     */
    public function getSize() {
        return $this->size;
    }
    /**
     * 判断当前二分搜索树是否为空
     * @return bool
     */
    public function isEmpty(): bool {
        return $this->size == 0;
    }
}
class Node
{
    public $e;
    public $left = null;
    public $right = null;
    /**
     * 构造函数 初始化节点数据
     * Node constructor.
     * @param $e
     */
    public function __construct($e) {
        $this->e = $e;
    }
}

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

php算法程序员

扩展阅读