PHP如何达成二分搜索树

发布时间：2022-04-18 14:11:56 所属栏目：语言来源：互联网

导读：学习过数据结构的朋友对于二叉树应该都不陌生，而二分搜索树也叫做二叉查找树，那么如何使用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) 是一个递归函数，表示使用递归向二分搜索树添加元素：

       Tips：这里的二分搜索树不包含重复元素，如果想要包含重复元素，可以定义每个左儿子所有元素小于等于父亲节点，或者每个节点右儿子所有节点元素大于等于父亲节点。

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

Tomcat下载和安置	装饰器模式装饰设计模
无用单元采集垃圾回收	Java访问对象的属性和