完全二叉树是什么?
若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边,这就是完全二叉树。
image.png
完全二叉树 php实现
<?php
/**
* @Author: fql
* @Email: fangqiulin4923@gmail.com
* @Date: 2020-07-19 22:41
*/
namespace fql\structure;
/**
* 完全二叉树
*
*/
class node{
private $element;
public $left;
public $right;
//构造函数
public function __construct($element)
{
$this->element = $element;
}
//获取类中的属性
public function __get($name){
return $this->$name;
}
}
class CompleteBinaryTree
{
private $heap;
private $len;
private $arr;
public function __construct($arr)
{
$this->arr = $arr;
$this->len = count($arr);
$headNode = new Node($arr[0]);
$this->heap = $headNode;
$this->buildTree($headNode,0);
return $this->heap;
}
//根据数组建立堆
function buildTree($node,$nodeIndex){
//建立左节点
if(2*$nodeIndex + 1 < $this->len){
$node->left = new Node($this->arr[2*$nodeIndex +1]);
$this->buildTree($node->left,2*$nodeIndex +1);
}
//建立右节点
if(2*$nodeIndex + 2 < $this->len){
$node->right = new Node(2*$nodeIndex +2);
$this->buildTree($node->right,2*$nodeIndex +2);
}
return $node;
}
//获取类中的属性
public function __get($name){
return $this->$name;
}
}
网友评论