CarlosWGama

Arvore de Ordem N

Jun 7th, 2017
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2. /**
  3. * @category Estrutura de Dados
  4. *
  5. */
  6. class ArvoreOrdemN {
  7.    
  8.     /**
  9.     * @var integer
  10.     * @access private
  11.     */
  12.     private $alturaMaxima = 4; //a arvore pode ter no máximo X de altura
  13.  
  14.     /**
  15.     * Só libera o próximo nível (altura) ao preencher todos do nível atual
  16.     * @var integer
  17.     * @access private
  18.     */
  19.     public $nivelMaximaLiberado = 1;
  20.    
  21.     /**
  22.     * Checa quando todos os campos daquele nível foram preenchidos
  23.     * @var integer
  24.     * @access private
  25.     */
  26.     public $mudarContagem = 0;
  27.  
  28.     /**
  29.     * @var integer
  30.     * @access private
  31.     */
  32.     private $ordem = 3; //cada nó pode ter no máximo N dados
  33.  
  34.     /**
  35.     * @var integer
  36.     * @access private
  37.     */
  38.     private $totalInserido = 0; //Quantos dados foram inseridos
  39.  
  40.     /**
  41.     * @var integer
  42.     * @access private
  43.     */
  44.     private $arvore = [];
  45.  
  46.  
  47.     /**
  48.     * Tenta adicionar uma pessoa na raiz. Se não puder tenta na função recursiva com os filhos
  49.     * @access public
  50.     * @uses $arv->addPessoa(['nome' => 'Carlos', 'cod' => 12323]);
  51.     * @param $dados array
  52.     * @return bool | true -> conseguiu inserir e false -> não foi possível inserir
  53.     */
  54.     public function addPessoa($dados = []) {
  55.         $dados['filhos'] = [];
  56.  
  57.         if (empty($this->arvore)) { //no raiz
  58.             $this->arvore[] = $dados;
  59.             $this->totalInserido = 1;
  60.             return true; //inserido com sucesso
  61.         } else {  //no interno ou folha
  62.             //tenta inserir em um no não raiz
  63.             return $this->addNoInterno($this->arvore[0]['filhos'], $dados, 1); 
  64.         }
  65.     }
  66.  
  67.     /**
  68.     * Tenta inserir um valor em um nó existente
  69.     * @access private
  70.     * @param $no | array -> no passado via referencia
  71.     * @param $dados | array
  72.     * @param $altura | integer (altura do nó atual)
  73.     * @return bool | true -> conseguiu inserir e false -> não foi possível inserir
  74.     */
  75.     private function addNoInterno(&$no, $dados, $altura, $inseriFilho = true) {
  76.        
  77.         //Passou da altura
  78.         if ($altura > $this->alturaMaxima)
  79.             return false; //'Não pode inserir além daqui';
  80.  
  81.         //Não poderá inserir em (nivel) maior do que o maior nivel sem filho
  82.         if ($altura - $this->nivelMaximaLiberado > 0)
  83.             return false; //Ainda há nó sem filho, não pode inserir em neto
  84.  
  85.         //Pode inserir no nó atual (Tem menos de 3 valores)
  86.         if (sizeof($no) < $this->ordem) {
  87.             $no[] = $dados;
  88.             $this->totalInserido++;
  89.             $this->mudarContagem++; //Verifica quantos itens foram adicionados naquele nivel
  90.            
  91.             //Verifica se já foi inserido todo mundo naquele nível, liberando o próximo
  92.             if (($this->mudarContagem) % ($this->ordem**$this->nivelMaximaLiberado) == 0) {
  93.                 $this->nivelMaximaLiberado++;
  94.                 $this->mudarContagem = 0;
  95.             }
  96.             return true;   
  97.         } elseif ($inseriFilho)  {
  98.             $altura++;
  99.             for ($i = 0; $i < $this->ordem; $i++) {
  100.                 if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura, false))
  101.                     return true; //conseguiu inserir em um nó abaixo      
  102.             }
  103.  
  104.             for ($i = 0; $i < $this->ordem; $i++) {
  105.                 if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura)) {
  106.                    
  107.                     return true; //conseguiu inserir em mais de um nó abaixo
  108.                 }
  109.             }
  110.         }
  111.         return false; //não conseguiu inserir em nenhum dos valores dos nós
  112.     }
  113.    
  114.     /**
  115.     * Retorna a árvore em forma de array
  116.     * @access public
  117.     * @return array
  118.     */
  119.     public function getArvore() {
  120.         return $this->arvore;
  121.     }
  122.  
  123.     /**
  124.     * Retorna o total de elementos inseridos nessa arvore
  125.     * @access public
  126.     * @return array
  127.     */
  128.     public function getTotal() {
  129.         return $this->totalInserido;
  130.     }
  131. }
RAW Paste Data