美文网首页
树 -(完全二叉树)

树 -(完全二叉树)

作者: designer | 来源:发表于2022-01-03 11:35 被阅读0次

    完全二叉树是什么?

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

    相关文章

      网友评论

          本文标题:树 -(完全二叉树)

          本文链接:https://www.haomeiwen.com/subject/nodxcrtx.html