前言
这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。
1.二叉树
1.1 二叉树图示
1.2 二叉树节点定义
Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。
1.3 二叉树的特点
二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。
二叉树不一定是满的，可能只有左儿子或又儿子。
一个节点或 NULL 也可以看做一个二叉树。
2.二分搜索树
2.1 二分搜索树特点
二分搜索树是二叉树。
每个节点的元素的值都要大于左儿子所有节点的值。
每个节点的元素的值都要小于右儿子所有节点的值。
每个子树也是二分搜索树。
二分搜索树查询速度快。
存储的元素必须要有比较性。
2.2 二分搜索树图示
2.3 PHP 代码定义节点
2.4 向二分搜索树添加元素
下面展示的的使用递归思想向二分搜索树添加元素，其中 add($e) 方法表示想二分搜索树添加元素 $e，recursionAdd(Node $root, $e) 是一个递归函数，表示使用递归向二分搜索树添加元素：
Tips：这里的二分搜索树不包含重复元素，如果想要包含重复元素，可以定义每个左儿子所有元素小于等于父亲节点，或者每个节点右儿子所有节点元素大于等于父亲节点。
2.5 查询二分搜索树是否包含某个元素
下面展示的的使用递归思想查询二分搜索树元素是否包含某个元素，其中 contains($e) 方法表示查询二分搜索树是否包含元素 $e，recursionContains(Node $root, $e) 是一个递归函数，表示使用递归查询二分搜索树元素：
ips：递归的时候会比较元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的位置就是判断是否包含元素是否存在的依据。
2.6 二分搜索树前序遍历
前序遍历操作就是把所有节点都访问一次，前序遍历 是先访问节点，再递归遍历左儿子树，然后再递归遍历右儿子树：
下面是打印结果:
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 二分搜索树中序遍历
遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历右儿子树，再访问节点，然后再递归遍历右儿子树，最后的顺序输出结果是有序的：
下面是打印结果:
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 二分搜索树后序遍历
遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历左儿子树，然后再递归遍历右儿子树，再访问节点：
下面是打印结果:
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实现二分搜索树的文章就介绍到这了
