当前位置：首页 > PHP教程 > php高级应用 > 列表

数据结构之利用PHP实现二分搜索树

发布:smiling　来源: PHP粉丝网 　添加日期：2022-03-29 08:31:00　浏览: 评论：0　

这篇文章主要给大家介绍了关于数据结构之利用PHP实现二分搜索树的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧。

前言

这篇文章是介绍 二叉树 和 二分搜索树，然后通过 PHP 代码定义一下 二分搜索树 的节点，使用递归思想操作向二分搜索树添加元素，然后实现了递归判断二分搜索树上是否包含某个元素，最后分别实现了前序遍历、中序遍历、后序遍历 二分搜索树。

1.二叉树

1.1 二叉树图示

数据结构之利用PHP实现二分搜索树

1.2 二叉树节点定义

  1. //二叉树具有唯一根节点 
  2. class Node{ 
  3.  $e; //节点元素 
  4.  $left; //左儿子 
  5.  $right;//右儿子 
  6. } 

Tips：二叉树每个节点最多有两个儿子，每个节点最多有一个父亲。

1.3 二叉树的特点

二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是 二叉树。

二叉树不一定是满的，可能只有左儿子或又儿子。

一个节点或 NULL 也可以看做一个二叉树。

2.二分搜索树

2.1 二分搜索树特点

二分搜索树是二叉树。

每个节点的元素的值都要大于左儿子所有节点的值。

每个节点的元素的值都要小于右儿子所有节点的值。

每个子树也是二分搜索树。

二分搜索树查询速度快。

存储的元素必须要有比较性。

2.2 二分搜索树图示

数据结构之利用PHP实现二分搜索树

2.3 PHP 代码定义节点

  1. class Node 
  2. { 
  3.  public $e; 
  4.  public $left = null; 
  5.  public $right = null; 
  6.  /** 
  7.   * 构造函数 初始化节点数据 
  8.   * Node constructor. 
  9.   * @param $e 
  10.   */ 
  11.  public function __construct($e) { 
  12.   $this->e = $e; 
  13.  } 
  14. } 

2.4 向二分搜索树添加元素

下面展示的的使用递归思想向二分搜索树添加元素，其中 add($e) 方法表示想二分搜索树添加元素 $e，recursionAdd(Node $root, $e) 是一个递归函数，表示使用递归向二分搜索树添加元素：

  1. /** 
  2.  * 向二分搜索树添加元素 
  3.  * @param $e 
  4.  */ 
  5. public function add($e) { 
  6.  $this->root = $this->recursionAdd($this->root, $e); 
  7. } 
  8. /** 
  9.  * 递归向二分搜索树添加元素 
  10.  * @param Node $root 
  11.  * @param $e 
  12.  */ 
  13. public function recursionAdd(Node $root, $e) { 
  14.  if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息 
  15.   $this->size++; 
  16.   $root = new Node($e); 
  17.  } elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素 
  18.   $root->left = $this->recursionAdd($root->left, $e); 
  19.  } elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素 
  20.   $root->right = $this->recursionAdd($root->right, $e); 
  21.  } //若元素等于当前节点元素 则什么都不做 
  22. } 

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

2.5 查询二分搜索树是否包含某个元素

下面展示的的使用递归思想查询二分搜索树元素是否包含某个元素，其中 contains($e) 方法表示查询二分搜索树是否包含元素 $e，recursionContains(Node $root, $e) 是一个递归函数，表示使用递归查询二分搜索树元素：

  1. /** 
  2.  * 判断二分搜索树是否包含某个元素 
  3.  * @param $e 
  4.  * @return bool 
  5.  */ 
  6. public function contains($e): bool { 
  7.  return $this->recursionContains($this->root, $e); 
  8. } 
  9. /** 
  10.  * 递归判断二分搜索树是否包含某元素 
  11.  * @param $root 
  12.  * @param $e 
  13.  * @return bool 
  14.  */ 
  15. private function recursionContains(Node $root, $e): bool { 
  16.  if ($root == null) { //若当前节点为空 则表示不存在元素 $e 
  17.   return false; 
  18.  } elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e 
  19.   return true; 
  20.  } elseif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点 
  21.   return $this->recursionContains($root->left, $e); 
  22.  } else { //若 $e 大于当前节点元素，则去右儿子树递归查询是否包含节点 
  23.   return $this->recursionContains($root->right, $e); 
  24.  } 
  25. } 

Tips：递归的时候会比较元素和节点的值，递归的时候判断元素大小相当于 “指路”，最终指向到的位置就是判断是否包含元素是否存在的依据。

2.6 二分搜索树前序遍历

前序遍历操作就是把所有节点都访问一次，前序遍历 是先访问节点，再递归遍历左儿子树，然后再递归遍历右儿子树：

  1. /** 
  2.  * 前序遍历 
  3.  */ 
  4. public function preTraversal() { 
  5.  $this->recursionPreTraversal($this->root, 0); 
  6. } 
  7. /** 
  8.  * 前序遍历的递归 
  9.  */ 
  10. public function recursionPreTraversal($root, $sign_num) { 
  11.  echo $this->getSign($sign_num);//打印深度 
  12.  if ($root == null) { 
  13.   echo "null<br>"; 
  14.   return; 
  15.  } 
  16.  echo $root->e . "<br>"; //打印当前节点元素 
  17.  $this->recursionPreTraversal($root->left, $sign_num + 1); 
  18.  $this->recursionPreTraversal($root->right, $sign_num + 1); 
  19. } 

下面是打印结果:

  1. <?php 
  2. require 'BinarySearchTree.php'; 
  3. $binarySearchTree = new BinarySearchTree(); 
  4. $binarySearchTree->add(45); 
  5. $binarySearchTree->add(30); 
  6. $binarySearchTree->add(55); 
  7. $binarySearchTree->add(25); 
  8. $binarySearchTree->add(35); 
  9. $binarySearchTree->add(50); 
  10. $binarySearchTree->add(65); 
  11. $binarySearchTree->add(15); 
  12. $binarySearchTree->add(27); 
  13. $binarySearchTree->add(31); 
  14. $binarySearchTree->add(48); 
  15. $binarySearchTree->add(60); 
  16. $binarySearchTree->add(68); 
  17. //下面是预期想要的结果 
  18. /** 
  19.  *                     45 
  20.  *           /                   
  21.  *          30                   55 
  22.  *        /                    /    
  23.  *      25       35         50       65 
  24.  *     /       /          /       /   
  25.  *   15   27  31         48       60     68 
  26.  * 
  27.  */ 
  28. $binarySearchTree->preTraversal(); 
  29. /** 

打印输出

  1. 45 
  2. -----30 
  3. ----------25 
  4. ---------------15 
  5. --------------------null 
  6. --------------------null 
  7. ---------------27 
  8. --------------------null 
  9. --------------------null 
  10. ----------35 
  11. ---------------31 
  12. --------------------null 
  13. --------------------null 
  14. ---------------null 
  15. -----55 
  16. ----------50 
  17. ---------------48 
  18. --------------------null 
  19. --------------------null 
  20. ---------------null 
  21. ----------65 
  22. ---------------60 
  23. --------------------null 
  24. --------------------null 
  25. ---------------68 
  26. --------------------null 
  27. --------------------null 
  28.  */ 

Tips：可以看到打印输出结果和预期一致。

2.7 二分搜索树中序遍历

遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历右儿子树，再访问节点，然后再递归遍历右儿子树，最后的顺序输出结果是有序的：

  1. /** 
  2.  * 中序遍历 
  3.  */ 
  4. public function midTraversal() { 
  5.  $this->recursionMidTraversal($this->root, 0); 
  6. } 
  7. /** 
  8.  * 中序遍历的递归 
  9.  */ 
  10. public function recursionMidTraversal($root, $sign_num) { 
  11.  if ($root == null) { 
  12.   echo $this->getSign($sign_num);//打印深度 
  13.   echo "null<br>"; 
  14.   return; 
  15.  } 
  16.  $this->recursionMidTraversal($root->left, $sign_num + 1); 
  17.  echo $this->getSign($sign_num);//打印深度 
  18.  echo $root->e . "<br>"; 
  19.  $this->recursionMidTraversal($root->right, $sign_num + 1); 
  20. } 

下面是打印结果:

  1. <?php 
  2. require 'BinarySearchTree.php'; 
  3. $binarySearchTree = new BinarySearchTree(); 
  4. $binarySearchTree->add(45); 
  5. $binarySearchTree->add(30); 
  6. $binarySearchTree->add(55); 
  7. $binarySearchTree->add(25); 
  8. $binarySearchTree->add(35); 
  9. $binarySearchTree->add(50); 
  10. $binarySearchTree->add(65); 
  11. $binarySearchTree->add(15); 
  12. $binarySearchTree->add(27); 
  13. $binarySearchTree->add(31); 
  14. $binarySearchTree->add(48); 
  15. $binarySearchTree->add(60); 
  16. $binarySearchTree->add(68); 
  17. //下面是预期想要的结果 
  18. /** 
  19.  *                     45 
  20.  *           /                   
  21.  *          30                   55 
  22.  *        /                    /    
  23.  *      25       35         50       65 
  24.  *     /       /          /       /   
  25.  *   15   27  31         48       60     68 
  26.  * 
  27.  */ 
  28. $binarySearchTree->midTraversal(); 
  29. /** 

打印输出

  1. --------------------null 
  2. ---------------15 
  3. --------------------null 
  4. ----------25 
  5. --------------------null 
  6. ---------------27 
  7. --------------------null 
  8. -----30 
  9. --------------------null 
  10. ---------------31 
  11. --------------------null 
  12. ----------35 
  13. ---------------null 
  14. 45 
  15. --------------------null 
  16. ---------------48 
  17. --------------------null 
  18. ----------50 
  19. ---------------null 
  20. -----55 
  21. --------------------null 
  22. ---------------60 
  23. --------------------null 
  24. ----------65 
  25. --------------------null 
  26. ---------------68 
  27. --------------------null 
  28.  */ 

Tips：可以看到打印输出结果和预期一致，但是此时的遍历顺序变了，最后的顺序输出结果是有序的。

2.8 二分搜索树后序遍历

遍历操作就是把所有节点都访问一次，后序遍历 是先递归遍历左儿子树，然后再递归遍历右儿子树，再访问节点：

  1. /** 
  2.  * 后序遍历 
  3.  */ 
  4. public function rearTraversal() { 
  5.  $this->recursionRearTraversal($this->root, 0); 
  6. } 
  7. /** 
  8.  * 后序遍历的递归 
  9.  */ 
  10. public function recursionRearTraversal($root, $sign_num) { 
  11.  if ($root == null) { 
  12.   echo $this->getSign($sign_num);//打印深度 
  13.   echo "null<br>"; 
  14.   return; 
  15.  } 
  16.  $this->recursionRearTraversal($root->left, $sign_num + 1); 
  17.  $this->recursionRearTraversal($root->right, $sign_num + 1); 
  18.  echo $this->getSign($sign_num);//打印深度 
  19.  echo $root->e . "<br>"; 
  20. } 

下面是打印结果:

  1. <?php 
  2. require 'BinarySearchTree.php'; 
  3. $binarySearchTree = new BinarySearchTree(); 
  4. $binarySearchTree->add(45); 
  5. $binarySearchTree->add(30); 
  6. $binarySearchTree->add(55); 
  7. $binarySearchTree->add(25); 
  8. $binarySearchTree->add(35); 
  9. $binarySearchTree->add(50); 
  10. $binarySearchTree->add(65); 
  11. $binarySearchTree->add(15); 
  12. $binarySearchTree->add(27); 
  13. $binarySearchTree->add(31); 
  14. $binarySearchTree->add(48); 
  15. $binarySearchTree->add(60); 
  16. $binarySearchTree->add(68); 
  17. //下面是预期想要的结果 
  18. /** 
  19.  *                     45 
  20.  *           /                   
  21.  *          30                   55 
  22.  *        /                    /    
  23.  *      25       35         50       65 
  24.  *     /       /          /       /   
  25.  *   15   27  31         48       60     68 
  26.  * 
  27.  */ 
  28. $binarySearchTree->rearTraversal(); 
  29. /** 

打印输出

  1. --------------------null 
  2. --------------------null 
  3. ---------------15 
  4. --------------------null 
  5. --------------------null 
  6. ---------------27 
  7. ----------25 
  8. --------------------null 
  9. --------------------null 
  10. ---------------31 
  11. ---------------null 
  12. ----------35 
  13. -----30 
  14. --------------------null 
  15. --------------------null 
  16. ---------------48 
  17. ---------------null 
  18. ----------50 
  19. --------------------null 
  20. --------------------null 
  21. ---------------60 
  22. --------------------null 
  23. --------------------null 
  24. ---------------68 
  25. ----------65 
  26. -----55 
  27. 45 
  28.  */ 

代码仓库 ：https://gitee.com/love-for-po...

Tags: PHP二分搜索树

分享到：

推荐文章

热门文章

最新评论文章