树 -（完全二叉树）

完全二叉树是什么？

若设二叉树的深度为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;
    }
}