Pasted

<?php
/**
* @category Estrutura de Dados
*
*/
class ArvoreOrdemN {
    
    /**
    * @var integer
    * @access private
    */
    private $alturaMaxima = 4; //a arvore pode ter no máximo X de altura
 
    /**
    * Só libera o próximo nível (altura) ao preencher todos do nível atual
    * @var integer
    * @access private
    */
    public $nivelMaximaLiberado = 1;
    
    /**
    * Checa quando todos os campos daquele nível foram preenchidos
    * @var integer
    * @access private
    */
    public $mudarContagem = 0;
 
    /**
    * @var integer
    * @access private
    */
    private $ordem = 3; //cada nó pode ter no máximo N dados
 
    /**
    * @var integer
    * @access private
    */
    private $totalInserido = 0; //Quantos dados foram inseridos
 
    /**
    * @var integer
    * @access private
    */
    private $arvore = []; 
 
 
    /**
    * Tenta adicionar uma pessoa na raiz. Se não puder tenta na função recursiva com os filhos
    * @access public
    * @uses $arv->addPessoa(['nome' => 'Carlos', 'cod' => 12323]);
    * @param $dados array
    * @return bool | true -> conseguiu inserir e false -> não foi possível inserir
    */
    public function addPessoa($dados = []) {
        $dados['filhos'] = [];
 
        if (empty($this->arvore)) { //no raiz
            $this->arvore[] = $dados; 
            $this->totalInserido = 1;
            return true; //inserido com sucesso
        } else {  //no interno ou folha
            //tenta inserir em um no não raiz
            return $this->addNoInterno($this->arvore[0]['filhos'], $dados, 1);  
        }
    }
 
    /**
    * Tenta inserir um valor em um nó existente
    * @access private
    * @param $no | array -> no passado via referencia
    * @param $dados | array
    * @param $altura | integer (altura do nó atual)
    * @return bool | true -> conseguiu inserir e false -> não foi possível inserir 
    */
    private function addNoInterno(&$no, $dados, $altura, $inseriFilho = true) {
        
        //Passou da altura
        if ($altura > $this->alturaMaxima)
            return false; //'Não pode inserir além daqui';
 
        //Não poderá inserir em (nivel) maior do que o maior nivel sem filho
        if ($altura - $this->nivelMaximaLiberado > 0) 
            return false; //Ainda há nó sem filho, não pode inserir em neto
 
        //Pode inserir no nó atual (Tem menos de 3 valores)
        if (sizeof($no) < $this->ordem) {
            $no[] = $dados;
            $this->totalInserido++;
            $this->mudarContagem++; //Verifica quantos itens foram adicionados naquele nivel
            
            //Verifica se já foi inserido todo mundo naquele nível, liberando o próximo
            if (($this->mudarContagem) % ($this->ordem**$this->nivelMaximaLiberado) == 0) {
                $this->nivelMaximaLiberado++;
                $this->mudarContagem = 0;
            }
            return true;    
        } elseif ($inseriFilho)  {
            $altura++;
            for ($i = 0; $i < $this->ordem; $i++) {
                if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura, false))
                    return true; //conseguiu inserir em um nó abaixo       
            }
 
            for ($i = 0; $i < $this->ordem; $i++) {
                if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura)) {
                    
                    return true; //conseguiu inserir em mais de um nó abaixo
                }
            }
        }
        return false; //não conseguiu inserir em nenhum dos valores dos nós
    }
    
    /**
    * Retorna a árvore em forma de array
    * @access public
    * @return array 
    */
    public function getArvore() {
        return $this->arvore;
    } 
 
    /**
    * Retorna o total de elementos inseridos nessa arvore
    * @access public
    * @return array 
    */
    public function getTotal() {
        return $this->totalInserido;
    }
}