Maison  >  Article  >  développement back-end  >  Explication détaillée de la méthode de définition d'un arbre binaire complet en PHP

Explication détaillée de la méthode de définition d'un arbre binaire complet en PHP

黄舟
黄舟original
2017-10-10 09:26:481713parcourir

Cet article présente principalement la définition et la méthode de mise en œuvre de l'arbre binaire complet en PHP. Il décrit brièvement le concept d'arbre binaire complet et donne la définition de l'arbre binaire complet, la recherche de nœuds, l'ajout, le paramétrage, l'impression et d'autres compétences opérationnelles associées. sous forme d'exemples. C'est obligatoire. Les amis peuvent se référer à

Cet article explique la définition et la méthode d'implémentation de l'arbre binaire complet en PHP avec des exemples. Partagez-le avec tout le monde pour votre référence. Les détails sont les suivants :

Si la profondeur de l'arbre binaire est h, à l'exception de la h-ème couche, le nombre de nœuds dans chaque autre couche (1 ~ h). -1) atteint le nombre maximum Tous les nœuds du niveau h sont continuellement concentrés sur le côté le plus à gauche, qui est un arbre binaire complet.

Implémentation du code PHP (implémenter temporairement l'ajout de nœuds, le parcours hiérarchique des nœuds et la suppression de nœuds pour les mises à jour ultérieures)


<?php
class Node{
  public $value;
  public $leftNode;
  public $rightNode;
}
/* 找到空节点 */
function findEmpytNode($node, $parent = null){
  if(empty($node->value)){
    return $node;
  }else{
    if(empty($node->leftNode->value)){
      return $node->leftNode;
    }else if(empty($node->rightNode->value)){
      return $node->rightNode;
    }else{
      if(empty($parent) || $node->value == $parent->rightNode->value){
        return findEmpytNode($node->leftNode, $node);
      }else{
        return findEmpytNode($parent->rightNode, $node);
      }
    }
  }
}
/* 添加节点 */
function addNode($node, $value){
  $emptyNode = findEmpytNode($node);
  setNode($emptyNode, $value);
}
/* 设置节点 */
function setNode($node, $value){
  $node->value = $value;
  $node->leftNode = new Node();
  $node->rightNode = new Node();
}
/* 打印 */
function printTree($node, $parent = null){
  if(empty($node->value)) return ;
  echo $node->leftNode->value;
  echo $node->rightNode->value;
  if(empty($parent) || $node->value == $parent->rightNode->value){
    printTree($node->leftNode, $node);
  }else{
    printTree($parent->rightNode, $node);
  }
}
$head = new Node();
setNode($head, 1);
addNode($head, 2);
addNode($head, 3);
addNode($head, 4);
addNode($head, 5);
addNode($head, 6);
printTree($head);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn