介绍
本篇内容主要讲解“数据结构怎么利用PHP实现二分搜索树”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习”数据结构怎么利用PHP实现二分搜索树”吧!
<>强前言
这篇文章是介绍二叉树和二分搜索树,然后通过PHP代码定义一下二分搜索树的节点,使用递归思想操作向二分搜索树添加元素,然后实现了递归判断二分搜索树上是否包含某个元素,最后分别实现了前序遍历,中序遍历,后序遍历二分搜索树。
<强> 1。二叉树
<强> 1.1二叉树图示
<强> 1.2二叉树节点定义
//二叉树具有唯一根节点
{class 节点
,$ e;//节点元素
,离开美元;//左儿子
,对美元;//右儿子
} 提示:二叉树每个节点最多有两个儿子,每个节点最多有一个父亲。
<强> 1.3二叉树的特点
<李> 二叉树具有天然的递归结构,每个节点的左儿子或右儿子也是二叉树。
<李> 二叉树不一定是满的,可能只有左儿子或又儿子。
<李> 一个节点或零也可以看做一个二叉树。
<强> 2。二分搜索树
<强> 2.1二分搜索树特点
<李> 二分搜索树是二叉树。
<李> 每个节点的元素的值都要大于左儿子所有节点的值。
<李> 每个节点的元素的值都要小于右儿子所有节点的值。
<李> 每个子树也是二分搜索树。
<李> 二分搜索树查询速度快。
<李> 存储的元素必须要有比较性。
<强> 2.2二分搜索树图示
<强> PHP 2.3代码定义节点
class 节点
{
,public $ e;
,public left 美元;=,空;
,public right 美元;=,空;/* *
*,才能构造函数,初始化节点数据
*,才能Node 构造函数。
*,才能@param $ e
,*/,public function __construct ($ e), {
这个美元才能→e =, $ e;
,}
} <强> 2.4向二分搜索树添加元素
下面展示的的使用递归思想向二分搜索树添加元素,其中添加(e)美元方法表示想二分搜索树添加元美元素e, recursionAdd(节点根,美元$ e)是一个递归函数,表示使用递归向二分搜索树添加元素:
,/* *
*,才能向二分搜索树添加元素
*,才能@param $ e
,*/,public function 添加($ e), {
这→美元才能root =, $ this→recursionAdd ($ this→根,,$ e);
,}/* *
*,才能递归向二分搜索树添加元素
*,才能@param Node 根美元
*,才能@param $ e
,*/,public function recursionAdd (Node 根,美元,美元e), {
if 才能;(root 美元;==,null),{,//若节点为空则添加元素,并且返回当前节点信息
,,这→美元大小+ +;
,,root 美元;=,new 节点($ e);
,,},elseif (e 美元;& lt;,根→美元e),{,//若元素小于当前节点元素,则向左节点递归添加元素
美元,才能根→left =, $ this→recursionAdd(根→美元左,,$ e);
,,},elseif (e 美元;祝辞,根→美元e),{,//若元素大于当前节点元素,则向右节点递归添加元素
美元,才能根→right =, $ this→recursionAdd(根→美元吧,,$ e);
,,},//若元素等于当前节点元素,则什么都不做
以前,} 提示:这里的二分搜索树不包含重复元素,如果想要包含重复元素,可以定义每个左儿子所有元素小于等于父亲节点,或者每个节点右儿子所有节点元素大于等于父亲节点。
<强> 2.5查询二分搜索树是否包含某个元素
下面展示的的使用递归思想查询二分搜索树元素是否包含某个元素,其中包含(e)美元方法表示查询二分搜索树是否包含元美元素e, recursionContains(节点根,美元$ e)是一个递归函数,表示使用递归查询二分搜索树元素:
,/* *
*,才能判断二分搜索树是否包含某个元素
*,才能@param $ e
*,才能@return 保龄球
,*/,public function 包含($ e):, bool {
return 才能;这→美元recursionContains ($ this→根,,$ e);
,}/* *
*,才能递归判断二分搜索树是否包含某元素
*,才能@param 根美元
*,才能@param $ e
*,才能@return 保龄球
,*/,private function recursionContains (Node 根,美元,美元e):, bool {
if 才能;(root 美元;==,null),{,//若当前节点为空,则表示不存在元素,$ e
,,return 假;
,,},elseif (e 美元;==,根→美元e),{,//若e 美元;等于当前节点元素,则表示树包含元素,$ e
,,return 真实;
,,},elseif (e 美元;& lt;,根→美元e),{,//若e 美元;小于当前节点元素,则去左儿子树递归查询是否包含节点
,才能return 美元这→recursionContains(根→美元左,,$ e);
,,},else {,//若e 美元;大于当前节点元素,则去右儿子树递归查询是否包含节点
,,return 美元这→recursionContains(根→美元吧,,$ e);
,,}
以前,}
