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

PHP完全二叉树定义与实现方法示例

发布:smiling 来源: PHP粉丝网  添加日期:2021-08-11 14:04:25 浏览: 评论:0 

这篇文章主要介绍了PHP完全二叉树定义与实现方法,简单描述了完全二叉树的概念并结合实例形式给出了完全二叉树的定义、节点查找、添加、设置、打印等相关操作技巧,需要的朋友可以参考下

本文实例讲述了PHP完全二叉树定义与实现方法。分享给大家供大家参考,具体如下:

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

PHP代码实现(暂时实现添加节点、层次遍历节点,删除节点后续更新)

  1. <?php 
  2. class Node{ 
  3.   public $value
  4.   public $leftNode
  5.   public $rightNode
  6. /* 找到空节点 */ 
  7. function findEmpytNode($node$parent = null){ 
  8.   if(emptyempty($node->value)){ 
  9.     return $node
  10.   }else
  11.     if(emptyempty($node->leftNode->value)){ 
  12.       return $node->leftNode; 
  13.     }else if(emptyempty($node->rightNode->value)){ 
  14.       return $node->rightNode; 
  15.     }else
  16.       if(emptyempty($parent) || $node->value == $parent->rightNode->value){ 
  17.         return findEmpytNode($node->leftNode, $node); 
  18.       }else
  19.         return findEmpytNode($parent->rightNode, $node); 
  20.       } 
  21.     } 
  22.   } 
  23. /* 添加节点 */ 
  24. function addNode($node$value){ 
  25.   $emptyNode = findEmpytNode($node); 
  26.   setNode($emptyNode$value); 
  27. /* 设置节点 */ 
  28. function setNode($node$value){ 
  29.   $node->value = $value
  30.   $node->leftNode = new Node(); 
  31.   $node->rightNode = new Node(); 
  32. /* 打印 */ 
  33. function printTree($node$parent = null){ 
  34.   if(emptyempty($node->value)) return ; 
  35.   echo $node->leftNode->value; 
  36.   echo $node->rightNode->value; 
  37.   if(emptyempty($parent) || $node->value == $parent->rightNode->value){ 
  38.     printTree($node->leftNode, $node); 
  39.   }else
  40.     printTree($parent->rightNode, $node); 
  41.   } 
  42. $head = new Node(); 
  43. setNode($head, 1); 
  44. addNode($head, 2); 
  45. addNode($head, 3); 
  46. addNode($head, 4); 
  47. addNode($head, 5); 
  48. addNode($head, 6); 
  49. printTree($head);

Tags: PHP二叉树

分享到: