Maison >développement back-end >tutoriel php >Explication détaillée de la méthode de définition d'un arbre binaire complet en PHP
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!